Paper 2024/1644

A Tight Lower Bound on the TdScrypt Trapdoor Memory-Hard Function

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)$.