Paper 2017/893
Beyond Hellman's TimeMemory TradeOffs with Applications to Proofs of Space
Hamza Abusalah, Joël Alwen, Bram Cohen, Danylo Khilko, Krzysztof Pietrzak, and Leonid Reyzin
Abstract
Proofs of space (PoS) were suggested as more ecological and economical alternative to proofs of work, which are currently used in blockchain designs like Bitcoin. The existing PoS are based on rather sophisticated graph pebbling lower bounds. Much simpler and in several aspects more efficient schemes based on inverting random functions have been suggested, but they don't give meaningful security guarantees due to existing timememory tradeoffs. In particular, Hellman showed that any permutation over a domain of size $N$ can be inverted in time $T$ by an algorithm that is given $S$ bits of auxiliary information whenever $S\cdot T \approx N$ (e.g. $S=T\approx N^{1/2}$). For functions Hellman gives a weaker attack with $S^2\cdot T\approx N^2$ (e.g., $S=T \approx N^{2/3}$). To prove lower bounds, one considers an adversary who has access to an oracle $f:[N]\rightarrow [N]$ and can make $T$ oracle queries. The best known lower bound is $S\cdot T\in \Omega(N)$ and holds for random functions and permutations. We construct functions that provably require more time and/or space to invert. Specifically, for any constant $k$ we construct a function $[N]\rightarrow [N]$ that cannot be inverted unless $S^k\cdot T \in \Omega(N^k)$ (in particular, $S=T\approx N^{k/(k+1)}$). Our construction does not contradict Hellman's timememory tradeoff, because it cannot be efficiently evaluated in forward direction. However, its entire function table can be computed in time quasilinear in $N$, which is sufficient for the PoS application. Our simplest construction is built from a random function oracle $g:[N]\times[N]\rightarrow [N]$ and a random permutation oracle $f:[N]\rightarrow [N]$ and is defined as $h(x)=g(x,x')$ where $f(x)=\pi(f(x'))$ with $\pi$ being any involution without a fixed point, e.g. flipping all the bits. For this function we prove that any adversary who gets $S$ bits of auxiliary information, makes at most $T$ oracle queries, and inverts $h$ on an $\epsilon$ fraction of outputs must satisfy $S^2\cdot T\in \Omega(\epsilon^2N^2)$.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published by the IACR in ASIACRYPT 2017
 Keywords
 TimeMemory TradeOffsProofs of SpaceProofs of WorkSpacemintBitcoin.
 Contact author(s)
 habusalah @ ist ac at
 History
 20170917: received
 Short URL
 https://ia.cr/2017/893
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/893, author = {Hamza Abusalah and Joël Alwen and Bram Cohen and Danylo Khilko and Krzysztof Pietrzak and Leonid Reyzin}, title = {Beyond Hellman's TimeMemory TradeOffs with Applications to Proofs of Space}, howpublished = {Cryptology {ePrint} Archive, Paper 2017/893}, year = {2017}, url = {https://eprint.iacr.org/2017/893} }