Welcome to the resource topic for 2024/1644
Title:
A Tight Lower Bound on the TdScrypt Trapdoor Memory-Hard Function
Authors: Jeremiah Blocki, Seunghoon Lee
Abstract:A trapdoor Memory-Hard Function is a function that is memory-hard to evaluate for any party who does not have a trapdoor, but is substantially less expensive to evaluate with the trapdoor. Biryukov and Perin (ASIACRYPT 2017) introduced the first candidate trapdoor Memory-Hard Function called \textsc{Diodon} which modifies a Memory-Hard Function called \textsc{Scrypt} by replacing a hash chain with repeated squaring modulo a composite number N=pq. The trapdoor, which consists of the prime factors p and q, allows one to compute the function with significantly reduced cumulative memory cost (CMC) O( n \log n \log^2 N ) where n denotes the running time parameter, e.g., the length of the hash chain or repeated squaring chain. By contrast, the best-known algorithm to compute \textsc{Diodon} without the trapdoor has the CMC O(n^2\log N). Auerbach et al. (EUROCRYPT 2024) provided the first provable lower bound on the CMC of \textsc{TdScrypt} — a specific instantiation of \textsc{Diodon}. In particular, in idealized models, they proved that the CMC of \textsc{TdScrypt} is \Omega(\frac{n^2}{\log n}\log N) which almost matches the upper bound O(n^2\log N) but is off by a multiplicative \log n factor. In this work, we show how to tighten the analysis of Auerbach et al. (EUROCRYPT 2024) and eliminate the gap. In particular, our results imply that \textsc{TdScrypt} has the CMC at least \Omega(n^2\log N).
ePrint: https://eprint.iacr.org/2024/1644
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .