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

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.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2024
trapdoormemory-hard functionscumulative memory complexityhidden-order groups
Contact author(s)
benedikt auerbach @ ista ac at
cguenthe @ ista ac at
pietrzak @ ista ac at
2024-02-26: approved
2024-02-23: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.