---
res:
  bibo_abstract:
  - "Truncation of cryptographic outputs is a technique that was recently introduced
    in Baldimtsi et al. [Foteini Baldimtsi et al., 2022]. The general idea is to try
    out many inputs to some cryptographic algorithm until the output (e.g. a public-key
    or some hash value) falls into some sparse set and thus can be compressed: by
    trying out an expected 2^k different inputs one will find an output that starts
    with k zeros.\r\nUsing such truncation one can for example save substantial gas
    fees on Blockchains where storing values is very expensive. While [Foteini Baldimtsi
    et al., 2022] show that truncation preserves the security of the underlying primitive,
    they only consider a setting without preprocessing. In this work we show that
    lower bounds on the time-space tradeoff for inverting random functions and permutations
    also hold with truncation, except for parameters ranges where the bound fails
    to hold for \"trivial\" reasons.\r\nConcretely, it’s known that any algorithm
    that inverts a random function or permutation with range N making T queries and
    using S bits of auxiliary input must satisfy S⋅ T ≥ Nlog N. This lower bound no
    longer holds in the truncated setting where one must only invert a challenge from
    a range of size N/2^k, as now one can simply save the replies to all N/2^k challenges,
    which requires S = log N⋅ N /2^k bits and allows to invert with T = 1 query.\r\nWe
    show that with truncation, whenever S is somewhat smaller than the log N⋅ N /2^k
    bits required to store the entire truncated function table, the known S⋅ T ≥ Nlog
    N lower bound applies.@eng"
  bibo_authorlist:
  - 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: Pengxiang
      foaf_name: Wang, Pengxiang
      foaf_surname: Wang
  bibo_doi: 10.4230/LIPIcs.ITC.2025.4
  bibo_volume: 343
  dct_date: 2025^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/9783959773850
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_subject:
  - Time-Space Lower Bounds
  - Blockchains
  dct_title: Time-space tradeoffs of truncation with preprocessing@
...