Paper 2024/312
Trapdoor MemoryHard Functions
Abstract
Memoryhard 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 memoryhard in the random oracle model (Alwen et al., Eurocrypt'17), Diodon's memoryhardness 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 nontrivial 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)
 Category
 Publickey cryptography
 Publication info
 A major revision of an IACR publication in EUROCRYPT 2024
 Keywords
 trapdoormemoryhard functionscumulative memory complexityhiddenorder groups
 Contact author(s)

benedikt auerbach @ ista ac at
cguenthe @ ista ac at
pietrzak @ ista ac at  History
 20240226: approved
 20240223: received
 See all versions
 Short URL
 https://ia.cr/2024/312
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/312, author = {Benedikt Auerbach and Christoph U. Günther and Krzysztof Pietrzak}, title = {Trapdoor MemoryHard Functions}, howpublished = {Cryptology ePrint Archive, Paper 2024/312}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/312}}, url = {https://eprint.iacr.org/2024/312} }