---
_id: '559'
abstract:
- lang: eng
  text: '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).'
alternative_title:
- LNCS
author:
- first_name: Hamza M
  full_name: Abusalah, Hamza M
  id: 40297222-F248-11E8-B48F-1D18A9856A87
  last_name: Abusalah
- first_name: Joel F
  full_name: Alwen, Joel F
  id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
  last_name: Alwen
- first_name: Bram
  full_name: Cohen, Bram
  last_name: Cohen
- first_name: Danylo
  full_name: Khilko, Danylo
  last_name: Khilko
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
- first_name: Leonid
  full_name: Reyzin, Leonid
  last_name: Reyzin
citation:
  ama: '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: Vol 10625. Springer;
    2017:357-379. doi:<a href="https://doi.org/10.1007/978-3-319-70697-9_13">10.1007/978-3-319-70697-9_13</a>'
  apa: 'Abusalah, H. M., Alwen, J. F., Cohen, B., Khilko, D., Pietrzak, K. Z., &#38;
    Reyzin, L. (2017). Beyond Hellman’s time-memory trade-offs with applications to
    proofs of space (Vol. 10625, pp. 357–379). Presented at the ASIACRYPT: Theory
    and Applications of Cryptology and Information Security, Hong Kong, China: Springer.
    <a href="https://doi.org/10.1007/978-3-319-70697-9_13">https://doi.org/10.1007/978-3-319-70697-9_13</a>'
  chicago: 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,” 10625:357–79. Springer, 2017. <a href="https://doi.org/10.1007/978-3-319-70697-9_13">https://doi.org/10.1007/978-3-319-70697-9_13</a>.
  ieee: '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,” presented at the ASIACRYPT: Theory and Applications of Cryptology and
    Information Security, Hong Kong, China, 2017, vol. 10625, pp. 357–379.'
  ista: '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. ASIACRYPT:
    Theory and Applications of Cryptology and Information Security, LNCS, vol. 10625,
    357–379.'
  mla: Abusalah, Hamza M., et al. <i>Beyond Hellman’s Time-Memory Trade-Offs with
    Applications to Proofs of Space</i>. Vol. 10625, Springer, 2017, pp. 357–79, doi:<a
    href="https://doi.org/10.1007/978-3-319-70697-9_13">10.1007/978-3-319-70697-9_13</a>.
  short: H.M. Abusalah, J.F. Alwen, B. Cohen, D. Khilko, K.Z. Pietrzak, L. Reyzin,
    in:, Springer, 2017, pp. 357–379.
conference:
  end_date: 2017-12-07
  location: Hong Kong, China
  name: 'ASIACRYPT: Theory and Applications of Cryptology and Information Security'
  start_date: 2017-12-03
date_created: 2018-12-11T11:47:10Z
date_published: 2017-11-18T00:00:00Z
date_updated: 2023-09-07T12:30:22Z
day: '18'
department:
- _id: KrPi
doi: 10.1007/978-3-319-70697-9_13
ec_funded: 1
intvolume: '     10625'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2017/893.pdf
month: '11'
oa: 1
oa_version: Submitted Version
page: 357 - 379
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '682815'
  name: Teaching Old Crypto New Tricks
publication_identifier:
  isbn:
  - 978-331970696-2
publication_status: published
publisher: Springer
publist_id: '7257'
quality_controlled: '1'
related_material:
  record:
  - id: '83'
    relation: dissertation_contains
    status: public
scopus_import: 1
status: public
title: Beyond Hellman’s time-memory trade-offs with applications to proofs of space
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10625
year: '2017'
...