---
res:
  bibo_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).@eng'
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Hamza M
      foaf_name: Abusalah, Hamza M
      foaf_surname: Abusalah
      foaf_workInfoHomepage: http://www.librecat.org/personId=40297222-F248-11E8-B48F-1D18A9856A87
  - foaf_Person:
      foaf_givenName: Joel F
      foaf_name: Alwen, Joel F
      foaf_surname: Alwen
      foaf_workInfoHomepage: http://www.librecat.org/personId=2A8DFA8C-F248-11E8-B48F-1D18A9856A87
  - foaf_Person:
      foaf_givenName: Bram
      foaf_name: Cohen, Bram
      foaf_surname: Cohen
  - foaf_Person:
      foaf_givenName: Danylo
      foaf_name: Khilko, Danylo
      foaf_surname: Khilko
  - foaf_Person:
      foaf_givenName: Krzysztof Z
      foaf_name: Pietrzak, Krzysztof Z
      foaf_surname: Pietrzak
      foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-9139-1654
  - foaf_Person:
      foaf_givenName: Leonid
      foaf_name: Reyzin, Leonid
      foaf_surname: Reyzin
  bibo_doi: 10.1007/978-3-319-70697-9_13
  bibo_volume: 10625
  dct_date: 2017^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/978-331970696-2
  dct_language: eng
  dct_publisher: Springer@
  dct_title: Beyond Hellman’s time-memory trade-offs with applications to proofs of
    space@
...