---
OA_place: repository
OA_type: green
_id: '20844'
abstract:
- lang: eng
text: "We introduce and construct a new proof system called Non-interactive Arguments
of Knowledge or Space (NArKoS), where a space-bounded prover can convince a verifier
they know a secret, while having access to sufficient space allows one to forge
indistinguishable proofs without the secret.\r\nAn application of NArKoS are space-deniable
proofs, which are proofs of knowledge (say for authentication in access control)
that are sound when executed by a lightweight device like a smart-card or an RFID
chip that cannot have much storage, but are deniable (in the strong sense of online
deniability) as the verifier, like a card reader, can efficiently forge such proofs.\r\nWe
construct NArKoS in the random oracle model using an OR-proof combining a sigma
protocol (for the proof of knowledge of the secret) with a new proof system called
simulatable Proof of Transient Space (simPoTS). We give two different constructions
of simPoTS, one based on labelling graphs with high pebbling complexity, a technique
used in the construction of memory-hard functions and proofs of space, and a more
practical construction based on the verifiable space-hard functions from TCC’24
where a prover must compute a root of a sparse polynomial. In both cases, the
main challenge is making the proofs efficiently simulatable."
acknowledgement: "Jesko Dujmovic: Funded by the European Union (ERC, LACONIC, 101041207).
Views and opinions expressed are however those of the author(s) only and do not
necessarily reflect those of the European Union or the European Research Council.
Neither the European Union nor the granting authority can be held responsible for
them.\r\nChristoph U. Günther and Krzysztof Pietrzak: This research was funded in
whole or in part by the Austrian Science Fund (FWF) 10.55776/F85. For open access
purposes, the author has applied a CC BY public copyright license to any author-accepted
manuscript version arising from this submission."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Jesko
full_name: Dujmovic, Jesko
last_name: Dujmovic
- first_name: Christoph Ullrich
full_name: Günther, Christoph Ullrich
id: ec98511c-eb8e-11eb-b029-edd25d7271a1
last_name: Günther
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Dujmovic J, Günther CU, Pietrzak KZ. Space-deniable proofs. In: 23rd International
Conference on Theory of Cryptography. Vol 16271. Springer Nature; 2025:171-202.
doi:10.1007/978-3-032-12290-2_6'
apa: 'Dujmovic, J., Günther, C. U., & Pietrzak, K. Z. (2025). Space-deniable
proofs. In 23rd International Conference on Theory of Cryptography (Vol.
16271, pp. 171–202). Aarhus, Denmark: Springer Nature. https://doi.org/10.1007/978-3-032-12290-2_6'
chicago: Dujmovic, Jesko, Christoph Ullrich Günther, and Krzysztof Z Pietrzak. “Space-Deniable
Proofs.” In 23rd International Conference on Theory of Cryptography, 16271:171–202.
Springer Nature, 2025. https://doi.org/10.1007/978-3-032-12290-2_6.
ieee: J. Dujmovic, C. U. Günther, and K. Z. Pietrzak, “Space-deniable proofs,” in
23rd International Conference on Theory of Cryptography, Aarhus, Denmark,
2025, vol. 16271, pp. 171–202.
ista: 'Dujmovic J, Günther CU, Pietrzak KZ. 2025. Space-deniable proofs. 23rd International
Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol.
16271, 171–202.'
mla: Dujmovic, Jesko, et al. “Space-Deniable Proofs.” 23rd International Conference
on Theory of Cryptography, vol. 16271, Springer Nature, 2025, pp. 171–202,
doi:10.1007/978-3-032-12290-2_6.
short: J. Dujmovic, C.U. Günther, K.Z. Pietrzak, in:, 23rd International Conference
on Theory of Cryptography, Springer Nature, 2025, pp. 171–202.
conference:
end_date: 2025-12-05
location: Aarhus, Denmark
name: 'TCC: Theory of Cryptography'
start_date: 2025-12-01
corr_author: '1'
date_created: 2025-12-21T23:01:33Z
date_published: 2025-12-05T00:00:00Z
date_updated: 2025-12-29T11:44:16Z
day: '05'
department:
- _id: KrPi
doi: 10.1007/978-3-032-12290-2_6
intvolume: ' 16271'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/1723
month: '12'
oa: 1
oa_version: Preprint
page: 171-202
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: 23rd International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032122896'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Space-deniable proofs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16271
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '20846'
abstract:
- lang: eng
text: "CVRFs are PRFs that unify the properties of verifiable and constrained PRFs.
Since they were introduced concurrently by Fuchsbauer and Chandran-Raghuraman-Vinayagamurthy
in 2014, it has been an open problem to construct CVRFs without using heavy machinery
such as multilinear maps, obfuscation or functional encryption.\r\nWe solve this
problem by constructing a prefix-constrained verifiable PRF that does not rely
on the aforementioned assumptions. Essentially, our construction is a verifiable
version of the Goldreich-Goldwasser-Micali PRF. To achieve verifiability we leverage
degree-2 algebraic PRGs and bilinear groups. In short, proofs consist of intermediate
values of the Goldreich-Goldwasser-Micali PRF raised to the exponents of group
elements. These outputs can be verified using pairings since the underlying PRG
is of degree 2.\r\nWe prove the selective security of our construction under the
Decisional Square Diffie-Hellman (DSDH) assumption and a new assumption, which
we dub recursive Decisional Diffie-Hellman (recursive DDH).\r\nWe prove the soundness
of recursive DDH in the generic group model assuming the hardness of the Multivariate
Quadratic (MQ) problem and a new variant thereof, which we call MQ+.\r\nLast,
in terms of applications, we observe that our CVRF is also an exponent (C)VRF
in the plain model. Exponent VRFs were recently introduced by Boneh et al. (Eurocrypt’25)
with various applications to threshold cryptography in mind. In addition to that,
we give further applications for prefix-CVRFs in the blockchain setting, namely,
stake-pooling and compressible randomness beacons."
acknowledgement: "We thank Jonas Steinbach and Gertjan De Mulder for helpful discussions
on BIP 32, Dennis Hofheinz and Julia Kastner for helpful discussions on early prototypes
of our CVRF, and Klaus Kraßnitzer for running pairing benchmarks on his MacBook
Pro.\r\nChristoph U. Günther: This research was funded in whole or in part by the
Austrian Science Fund (FWF) 10.55776/F85. For open access purposes, the author has
applied a CC BY public copyright license to any author-accepted manuscript version
arising from this submission."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Nicholas
full_name: Brandt, Nicholas
last_name: Brandt
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Christoph Ullrich
full_name: Günther, Christoph Ullrich
id: ec98511c-eb8e-11eb-b029-edd25d7271a1
last_name: Günther
- first_name: Akin
full_name: Ünal, Akin
id: f6b56fb6-dc63-11ee-9dbf-f6780863a85a
last_name: Ünal
orcid: 0000-0002-8929-0221
- first_name: Stella
full_name: Wohnig, Stella
last_name: Wohnig
citation:
ama: 'Brandt N, Cueto Noval M, Günther CU, Ünal A, Wohnig S. Constrained verifiable
random functions without obfuscation and friends. In: 23rd International Conference
on Theory of Cryptography. Vol 16271. Springer Nature; 2025:478-511. doi:10.1007/978-3-032-12290-2_16'
apa: 'Brandt, N., Cueto Noval, M., Günther, C. U., Ünal, A., & Wohnig, S. (2025).
Constrained verifiable random functions without obfuscation and friends. In 23rd
International Conference on Theory of Cryptography (Vol. 16271, pp. 478–511).
Aarhus, Denmark: Springer Nature. https://doi.org/10.1007/978-3-032-12290-2_16'
chicago: Brandt, Nicholas, Miguel Cueto Noval, Christoph Ullrich Günther, Akin Ünal,
and Stella Wohnig. “Constrained Verifiable Random Functions without Obfuscation
and Friends.” In 23rd International Conference on Theory of Cryptography,
16271:478–511. Springer Nature, 2025. https://doi.org/10.1007/978-3-032-12290-2_16.
ieee: N. Brandt, M. Cueto Noval, C. U. Günther, A. Ünal, and S. Wohnig, “Constrained
verifiable random functions without obfuscation and friends,” in 23rd International
Conference on Theory of Cryptography, Aarhus, Denmark, 2025, vol. 16271, pp.
478–511.
ista: 'Brandt N, Cueto Noval M, Günther CU, Ünal A, Wohnig S. 2025. Constrained
verifiable random functions without obfuscation and friends. 23rd International
Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol.
16271, 478–511.'
mla: Brandt, Nicholas, et al. “Constrained Verifiable Random Functions without Obfuscation
and Friends.” 23rd International Conference on Theory of Cryptography,
vol. 16271, Springer Nature, 2025, pp. 478–511, doi:10.1007/978-3-032-12290-2_16.
short: N. Brandt, M. Cueto Noval, C.U. Günther, A. Ünal, S. Wohnig, in:, 23rd International
Conference on Theory of Cryptography, Springer Nature, 2025, pp. 478–511.
conference:
end_date: 2025-12-05
location: Aarhus, Denmark
name: 'TCC: Theory of Cryptography'
start_date: 2025-12-01
corr_author: '1'
date_created: 2025-12-21T23:01:34Z
date_published: 2025-12-05T00:00:00Z
date_updated: 2025-12-29T11:11:29Z
day: '05'
department:
- _id: KrPi
doi: 10.1007/978-3-032-12290-2_16
intvolume: ' 16271'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/1045
month: '12'
oa: 1
oa_version: Preprint
page: 478-511
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: 23rd International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032122896'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Constrained verifiable random functions without obfuscation and friends
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16271
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '20587'
abstract:
- lang: eng
text: "The blocks in the Bitcoin blockchain \"record\" the amount of work W that
went into creating them through proofs of work. When honest parties control a
majority of the work, consensus is achieved by picking the chain with the highest
recorded weight. Resources other than work have been considered to secure such
longest-chain blockchains. In Chia, blocks record the amount of disk-space S (via
a proof of space) and sequential computational steps V (through a VDF).\r\nIn
this paper, we ask what weight functions Γ(S,V,W) (that assign a weight to a block
as a function of the recorded space, speed, and work) are secure in the sense
that whenever the weight of the resources controlled by honest parties is larger
than the weight of adversarial parties, the blockchain is secure against private
double-spending attacks.\r\nWe completely classify such functions in an idealized
\"continuous\" model: Γ(S,V,W) is secure against private double-spending attacks
if and only if it is homogeneous of degree one in the \"timed\" resources V and
W, i.e., αΓ(S,V,W) = Γ(S,α V, α W). This includes the Bitcoin rule Γ(S,V,W) =
W and the Chia rule Γ(S,V,W) = S ⋅ V. In a more realistic model where blocks are
created at discrete time-points, one additionally needs some mild assumptions
on the dependency on S (basically, the weight should not grow too much if S is
slightly increased, say linear as in Chia).\r\nOur classification is more general
and allows various instantiations of the same resource. It provides a powerful
tool for designing new longest-chain blockchains. E.g., consider combining different
PoWs to counter centralization, say the Bitcoin PoW W₁ and a memory-hard PoW W₂.
Previous work suggested to use W₁+W₂ as weight. Our results show that using e.g.,
√{W₁}⋅ √{W₂} or min{W₁,W₂} are also secure, and we argue that in practice these
are much better choices."
acknowledgement: "This research was funded in whole or in part by the Austrian Science
Fund (FWF)\r\n10.55776/F85. For open access purposes, the author has applied a CC
BY public copyright license\r\nto any author-accepted manuscript version arising
from this submission."
alternative_title:
- LIPIcs
article_number: '16'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Christoph Ullrich
full_name: Günther, Christoph Ullrich
id: ec98511c-eb8e-11eb-b029-edd25d7271a1
last_name: Günther
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Baig MA, Günther CU, Pietrzak KZ. Nakamoto consensus from multiple resources.
In: 7th Conference on Advances in Financial Technologies. Vol 354. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.AFT.2025.16'
apa: 'Baig, M. A., Günther, C. U., & Pietrzak, K. Z. (2025). Nakamoto consensus
from multiple resources. In 7th Conference on Advances in Financial Technologies
(Vol. 354). Pittsburgh, PA, United States: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.AFT.2025.16'
chicago: Baig, Mirza Ahad, Christoph Ullrich Günther, and Krzysztof Z Pietrzak.
“Nakamoto Consensus from Multiple Resources.” In 7th Conference on Advances
in Financial Technologies, Vol. 354. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2025. https://doi.org/10.4230/LIPIcs.AFT.2025.16.
ieee: M. A. Baig, C. U. Günther, and K. Z. Pietrzak, “Nakamoto consensus from multiple
resources,” in 7th Conference on Advances in Financial Technologies, Pittsburgh,
PA, United States, 2025, vol. 354.
ista: 'Baig MA, Günther CU, Pietrzak KZ. 2025. Nakamoto consensus from multiple
resources. 7th Conference on Advances in Financial Technologies. AFT: Conference
on Advances in Financial Technologies, LIPIcs, vol. 354, 16.'
mla: Baig, Mirza Ahad, et al. “Nakamoto Consensus from Multiple Resources.” 7th
Conference on Advances in Financial Technologies, vol. 354, 16, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.AFT.2025.16.
short: M.A. Baig, C.U. Günther, K.Z. Pietrzak, in:, 7th Conference on Advances in
Financial Technologies, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
conference:
end_date: 2025-10-10
location: Pittsburgh, PA, United States
name: 'AFT: Conference on Advances in Financial Technologies'
start_date: 2025-10-08
corr_author: '1'
date_created: 2025-11-02T23:01:34Z
date_published: 2025-10-06T00:00:00Z
date_updated: 2026-04-15T08:45:18Z
day: '06'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.4230/LIPIcs.AFT.2025.16
external_id:
arxiv:
- '2508.01448'
file:
- access_level: open_access
checksum: b638adcd4fbffa77116c35393e165eb7
content_type: application/pdf
creator: dernst
date_created: 2025-11-04T08:19:02Z
date_updated: 2025-11-04T08:19:02Z
file_id: '20598'
file_name: 2025_LIPIcsAFT_Baig.pdf
file_size: 1061847
relation: main_file
success: 1
file_date_updated: 2025-11-04T08:19:02Z
has_accepted_license: '1'
intvolume: ' 354'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/1410
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f
grant_number: F8512
name: Security and Privacy by Design for Complex Systems
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: 7th Conference on Advances in Financial Technologies
publication_identifier:
isbn:
- '9783959774000'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '21651'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Nakamoto consensus from multiple resources
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 354
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '18961'
abstract:
- lang: eng
text: "Automated contact tracing (ACT) emerged as a promising measure to curb the
spread of Covid-19. Users enable ACT on their smartphones to automatically record
contacts with other users. If a user tests positive for the disease, they report
their diagnosis to alert their contacts.\r\nDesigning effective ACT protocols
is challenging since they need to be efficient and secure while also ensuring
users' privacy. As ACT protocols necessarily leak some information by design,
defining privacy is difficult. For example, a user cannot deny having met another
user. Ideally, however, the user can plausibly deny everything else, in particular,
when they met. We call this privacy property contact-time deniability.\r\nWhile
some early works discussed contact-time deniability informally, it has received
little attention since then. We investigate deniability from a rigorous, theoretical
point of view and arrive at the following impossibility result:\r\nA decentralized
protocol with unidirectional communication cannot be contact-time deniable and
replay-secure. This holds even if malicious users treat smartphones as black-boxes.\r\n
Unidirectional protocols are usually very efficient and many proposals are unidirectional,
e.g., the widely-deployed Google-Apple Exposure Notifications. So the impossibility
result considerably constrains the design space of efficient, secure, and private
ACT protocols. However, it can also be used as a guide; we discuss several possibilities
to achieve contact-time deniability in practice."
acknowledgement: "We thank Raluca-Georgia Diugan for her initial contributions and
support afterward.\r\nThis research was funded in whole or in part by the Austrian
Science Fund (FWF) 10.55776/F85."
article_processing_charge: No
article_type: original
author:
- first_name: Christoph Ullrich
full_name: Günther, Christoph Ullrich
id: ec98511c-eb8e-11eb-b029-edd25d7271a1
last_name: Günther
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Günther CU, Pietrzak KZ. Deniability in automated contact tracing: Impossibilities
and possibilities. Proceedings on Privacy Enhancing Technologies. 2024;2024(4):636-648.
doi:10.56553/popets-2024-0134'
apa: 'Günther, C. U., & Pietrzak, K. Z. (2024). Deniability in automated contact
tracing: Impossibilities and possibilities. Proceedings on Privacy Enhancing
Technologies. Bristol, UK/Virtual: Privacy Enhancing Technologies Symposium
Advisory Board. https://doi.org/10.56553/popets-2024-0134'
chicago: 'Günther, Christoph Ullrich, and Krzysztof Z Pietrzak. “Deniability in
Automated Contact Tracing: Impossibilities and Possibilities.” Proceedings
on Privacy Enhancing Technologies. Privacy Enhancing Technologies Symposium
Advisory Board, 2024. https://doi.org/10.56553/popets-2024-0134.'
ieee: 'C. U. Günther and K. Z. Pietrzak, “Deniability in automated contact tracing:
Impossibilities and possibilities,” Proceedings on Privacy Enhancing Technologies,
vol. 2024, no. 4. Privacy Enhancing Technologies Symposium Advisory Board, pp.
636–648, 2024.'
ista: 'Günther CU, Pietrzak KZ. 2024. Deniability in automated contact tracing:
Impossibilities and possibilities. Proceedings on Privacy Enhancing Technologies.
2024(4), 636–648.'
mla: 'Günther, Christoph Ullrich, and Krzysztof Z. Pietrzak. “Deniability in Automated
Contact Tracing: Impossibilities and Possibilities.” Proceedings on Privacy
Enhancing Technologies, vol. 2024, no. 4, Privacy Enhancing Technologies Symposium
Advisory Board, 2024, pp. 636–48, doi:10.56553/popets-2024-0134.'
short: C.U. Günther, K.Z. Pietrzak, Proceedings on Privacy Enhancing Technologies
2024 (2024) 636–648.
conference:
end_date: 2024-07-20
location: Bristol, UK/Virtual
name: 'PETs: Privacy Enhancing Technologies Symposium '
start_date: 2024-07-15
corr_author: '1'
date_created: 2025-01-29T13:39:34Z
date_published: 2024-07-01T00:00:00Z
date_updated: 2025-04-15T08:16:04Z
day: '01'
ddc:
- '000'
department:
- _id: KrPi
- _id: GradSch
doi: 10.56553/popets-2024-0134
file:
- access_level: open_access
checksum: 348ed6adcf6ad2f925227bde1758cae6
content_type: application/pdf
creator: dernst
date_created: 2025-01-29T13:44:47Z
date_updated: 2025-01-29T13:44:47Z
file_id: '18962'
file_name: 2024_ProcPrivacyEnhTech_Guenther.pdf
file_size: 611567
relation: main_file
success: 1
file_date_updated: 2025-01-29T13:44:47Z
has_accepted_license: '1'
intvolume: ' 2024'
issue: '4'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 636-648
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: Proceedings on Privacy Enhancing Technologies
publication_identifier:
issn:
- 2299-0984
publication_status: published
publisher: Privacy Enhancing Technologies Symposium Advisory Board
quality_controlled: '1'
status: public
title: 'Deniability in automated contact tracing: Impossibilities and possibilities'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2024
year: '2024'
...
---
_id: '17051'
abstract:
- lang: eng
text: "Memory-hard functions (MHF) are functions whose evaluation provably requires\r\na
lot of memory. While MHFs are an unkeyed primitive, it is natural to consider
the\r\nnotion of trapdoor MHFs (TMHFs). A TMHF is like an MHF, but when sampling\r\nthe
public parameters one also samples a trapdoor which allows evaluating the\r\nfunction
much cheaper.\r\nBiryukov and Perrin (Asiacrypt’17) were the first to consider
TMHFs and put\r\nforth a candidate TMHF construction called Diodon that is based
on the Scrypt\r\nMHF (Percival, BSDCan’09). To allow for a trapdoor, Scrypt’s
initial hash chain\r\nis replaced by a sequence of squares in a group of unknown
order where the order of\r\nthe group is the trapdoor. For a length n sequence
of squares and a group of order\r\nN, Diodon’s cumulative memory complexity (CMC)
is O(n2log N) without the\r\ntrapdoor and O(n log(n) log(N)2) with knowledge of
it.\r\nWhile Scrypt is proven to be optimally memory-hard in the random oracle\r\nmodel
(Alwen et al., Eurocrypt’17), Diodon’s memory-hardness has not been\r\nproven
so far. In this work, we fill this gap by rigorously analyzing a specific\r\ninstantiation
of Diodon. We show that its CMC is lower bounded by Ω( n2log nlog N)\r\nwhich
almost matches the upper bound. Our proof is based Alwen et al.’s lower\r\nbound
on Scrypt’s CMC but requires non-trivial modifications due to the algebraic\r\nstructure
of Diodon. Most importantly, our analysis involves a more elaborate\r\ncompression
argument and a solvability criterion for certain systems of Diophantine\r\nequations."
acknowledgement: We thank the Eurocrypt reviewers for their thorough review and for
pointing out related works. This research was funded in whole or in part by the
Austrian Science Fund (FWF) 10.55776/F85.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Christoph Ullrich
full_name: Günther, Christoph Ullrich
id: ec98511c-eb8e-11eb-b029-edd25d7271a1
last_name: Günther
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Auerbach B, Günther CU, Pietrzak KZ. Trapdoor memory-hard functions. In: 43rd
Annual International Conference on the Theory and Applications of Cryptographic
Techniques. Vol 14653. Springer Nature; 2024:315-344. doi:10.1007/978-3-031-58734-4_11'
apa: 'Auerbach, B., Günther, C. U., & Pietrzak, K. Z. (2024). Trapdoor memory-hard
functions. In 43rd Annual International Conference on the Theory and Applications
of Cryptographic Techniques (Vol. 14653, pp. 315–344). Zurich, Switzerland:
Springer Nature. https://doi.org/10.1007/978-3-031-58734-4_11'
chicago: Auerbach, Benedikt, Christoph Ullrich Günther, and Krzysztof Z Pietrzak.
“Trapdoor Memory-Hard Functions.” In 43rd Annual International Conference on
the Theory and Applications of Cryptographic Techniques, 14653:315–44. Springer
Nature, 2024. https://doi.org/10.1007/978-3-031-58734-4_11.
ieee: B. Auerbach, C. U. Günther, and K. Z. Pietrzak, “Trapdoor memory-hard functions,”
in 43rd Annual International Conference on the Theory and Applications of Cryptographic
Techniques, Zurich, Switzerland, 2024, vol. 14653, pp. 315–344.
ista: 'Auerbach B, Günther CU, Pietrzak KZ. 2024. Trapdoor memory-hard functions.
43rd Annual International Conference on the Theory and Applications of Cryptographic
Techniques. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS,
vol. 14653, 315–344.'
mla: Auerbach, Benedikt, et al. “Trapdoor Memory-Hard Functions.” 43rd Annual
International Conference on the Theory and Applications of Cryptographic Techniques,
vol. 14653, Springer Nature, 2024, pp. 315–44, doi:10.1007/978-3-031-58734-4_11.
short: B. Auerbach, C.U. Günther, K.Z. Pietrzak, in:, 43rd Annual International
Conference on the Theory and Applications of Cryptographic Techniques, Springer
Nature, 2024, pp. 315–344.
conference:
end_date: 2024-05-30
location: Zurich, Switzerland
name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
start_date: 2024-05-26
corr_author: '1'
date_created: 2024-05-26T22:00:58Z
date_published: 2024-05-01T00:00:00Z
date_updated: 2025-09-08T07:35:40Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-031-58734-4_11
external_id:
isi:
- '001274940200011'
intvolume: ' 14653'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2024/312
month: '05'
oa: 1
oa_version: Preprint
page: 315-344
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: 43rd Annual International Conference on the Theory and Applications of
Cryptographic Techniques
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031587337'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Trapdoor memory-hard functions
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 14653
year: '2024'
...