Beyond Hellman’s time-memory trade-offs with applications to proofs of space

H.M. Abusalah, J.F. Alwen, B. Cohen, D. Khilko, K.Z. Pietrzak, L. Reyzin, in:, T. Takagi, T. Peyrin (Eds.), Lecture Notes in Computer Science, Springer, 2017, pp. 357–379.


Conference Paper | Published | English
Author
Editor
;
Department
Series Title
LNCS
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 time-memory trade-offs. 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 (Formula presented). For functions Hellman gives a weaker attack with S2· T≈ N2 (e.g., S= T≈ N2/3). To prove lower bounds, one considers an adversary who has access to an oracle f: [ N] → [N] and can make T oracle queries. The best known lower bound is S· T∈ Ω(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] → [N] that cannot be inverted unless Sk· T∈ Ω(Nk) (in particular, S= T≈ (Formula presented). Our construction does not contradict Hellman’s time-memory trade-off, 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] × [N] → [ N] and a random permutation oracle f: [N] → N] and is defined as h(x) = g(x, x′) where f(x) = π(f(x′)) with π 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 ϵ fraction of outputs must satisfy S2· T∈ Ω(ϵ2N2).
Publishing Year
Date Published
2017-11-18
Proceedings Title
Lecture Notes in Computer Science
Volume
10625
Page
357 - 379
Conference
ASIACRYPT: Theory and Applications of Cryptology and Information Security
Conference Location
Hong Kong, China
Conference Date
2017-12-03 – 2017-12-07
IST-REx-ID

Cite this

Abusalah HM, Alwen JF, Cohen B, Khilko D, Pietrzak KZ, Reyzin L. Beyond Hellman’s time-memory trade-offs with applications to proofs of space. In: Takagi T, Peyrin T, eds. Lecture Notes in Computer Science. Vol 10625. Springer; 2017:357-379. doi:10.1007/978-3-319-70697-9_13
Abusalah, H. M., Alwen, J. F., Cohen, B., Khilko, D., Pietrzak, K. Z., & Reyzin, L. (2017). Beyond Hellman’s time-memory trade-offs with applications to proofs of space. In T. Takagi & T. Peyrin (Eds.), Lecture Notes in Computer Science (Vol. 10625, pp. 357–379). Hong Kong, China: Springer. https://doi.org/10.1007/978-3-319-70697-9_13
Abusalah, Hamza M, Joel F Alwen, Bram Cohen, Danylo Khilko, Krzysztof Z Pietrzak, and Leonid Reyzin. “Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space.” In Lecture Notes in Computer Science, edited by Tsuyoshi Takagi and Thomas Peyrin, 10625:357–79. Springer, 2017. https://doi.org/10.1007/978-3-319-70697-9_13.
H. M. Abusalah, J. F. Alwen, B. Cohen, D. Khilko, K. Z. Pietrzak, and L. Reyzin, “Beyond Hellman’s time-memory trade-offs with applications to proofs of space,” in Lecture Notes in Computer Science, Hong Kong, China, 2017, vol. 10625, pp. 357–379.
Abusalah HM, Alwen JF, Cohen B, Khilko D, Pietrzak KZ, Reyzin L. 2017. Beyond Hellman’s time-memory trade-offs with applications to proofs of space. Lecture Notes in Computer Science. ASIACRYPT: Theory and Applications of Cryptology and Information Security, LNCS, vol. 10625. 357–379.
Abusalah, Hamza M., et al. “Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space.” Lecture Notes in Computer Science, edited by Tsuyoshi Takagi and Thomas Peyrin, vol. 10625, Springer, 2017, pp. 357–79, doi:10.1007/978-3-319-70697-9_13.

Link(s) to Main File(s)
Access Level
OA Open Access
Material in IST:
Dissertation containing IST record

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search