Trapdoor Memory-Hard Functions

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 \(\textsc {Diodon}\) that is based on the \(\textsc {Scrypt}\) MHF (Percival, BSDCan’09). To allow for a trapdoor, \(\textsc {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, \(\textsc {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 \(\textsc {Scrypt}\) is proven to be optimally memory-hard in the random oracle model (Alwen et al., Eurocrypt’17), \(\textsc {Diodon}\) ’s memory-hardness has not been proven so far. In this work, we fill this gap by rigorously analyzing a specific instantiation of \(\textsc {Diodon}\) . We show that its CMC is lower bounded by \(\varOmega (\frac{n^2}{\log n} \log N)\) which almost matches the upper bound. Our proof is based Alwen et al.’s lower bound on \(\textsc {Scrypt}\) ’s CMC but requires non-trivial modifications due to the algebraic structure of \(\textsc {Diodon}\) . Most importantly, our analysis involves a more elaborate compression argument and a solvability criterion for certain systems of Diophantine equations.