Paper 2024/312

Trapdoor Memory-Hard Functions

Benedikt Auerbach, Institute of Science and Technology Austria
Christoph U. Günther, Institute of Science and Technology Austria
Krzysztof Pietrzak, Institute of Science and Technology Austria
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(n^2\log 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 $\Omega(\frac{n^2}{\log n} \log 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2024
Keywords
trapdoormemory-hard functionscumulative memory complexityhidden-order groups
Contact author(s)
benedikt auerbach @ ista ac at
cguenthe @ ista ac at
pietrzak @ ista ac at
History
2024-02-26: approved
2024-02-23: received
See all versions
Short URL
https://ia.cr/2024/312
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/312,
      author = {Benedikt Auerbach and Christoph U. Günther and Krzysztof Pietrzak},
      title = {Trapdoor Memory-Hard Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/312},
      year = {2024},
      url = {https://eprint.iacr.org/2024/312}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.