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 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.
14653
315-344
315-344
Springer Nature