Trapdoor memory-hard functions

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: International Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol. 14653, 315–344.

Download (ext.)

Conference Paper | Published | English

Scopus indexed

Corresponding author has ISTA affiliation

Department
Series Title
LNCS
Abstract
Memory-hard functions (MHF) are functions whose evaluation provably requires a lot of memory. While MHFs are an unkeyed primitive, it is natural to consider the notion of trapdoor MHFs (TMHFs). A TMHF is like an MHF, but when sampling the public parameters one also samples a trapdoor which allows evaluating the function much cheaper. Biryukov and Perrin (Asiacrypt’17) were the first to consider TMHFs and put forth a candidate TMHF construction called Diodon that is based on the Scrypt MHF (Percival, BSDCan’09). To allow for a trapdoor, Scrypt’s initial hash chain is replaced by a sequence of squares in a group of unknown order where the order of the group is the trapdoor. For a length n sequence of squares and a group of order N, Diodon’s cumulative memory complexity (CMC) is O(n2log N) without the trapdoor and O(n log(n) log(N)2) with knowledge of it. While Scrypt is proven to be optimally memory-hard in the random oracle model (Alwen et al., Eurocrypt’17), Diodon’s memory-hardness has not been proven so far. In this work, we fill this gap by rigorously analyzing a specific instantiation of Diodon. We show that its CMC is lower bounded by Ω( n2log nlog N) which almost matches the upper bound. Our proof is based Alwen et al.’s lower bound on Scrypt’s CMC but requires non-trivial modifications due to the algebraic structure of Diodon. Most importantly, our analysis involves a more elaborate compression argument and a solvability criterion for certain systems of Diophantine equations.
Publishing Year
Date Published
2024-05-01
Proceedings Title
43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques
Publisher
Springer Nature
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.
Volume
14653
Page
315-344
Conference
EUROCRYPT: International Conference on the Theory and Applications of Cryptographic Techniques
Conference Location
Zurich, Switzerland
Conference Date
2024-05-26 – 2024-05-30
ISSN
eISSN
IST-REx-ID

Cite this

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
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
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.
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.
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: International Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol. 14653, 315–344.
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.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search