CryptoDB
Trapdoor Memory-Hard Functions
| Authors: |
|
|---|---|
| Download: | |
| Conference: | EUROCRYPT 2024 |
| 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 Ω((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. |
BibTeX
@inproceedings{eurocrypt-2024-33857,
title={Trapdoor Memory-Hard Functions},
publisher={Springer-Verlag},
author={Benedikt Auerbach and Christoph U. Günther and Krzysztof Pietrzak},
year=2024
}