---
OA_place: publisher
OA_type: gold
_id: '22007'
abstract:
- lang: eng
  text: "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."
alternative_title:
- LIPIcs
article_number: 4:1-4:10
article_processing_charge: Yes
author:
- 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: Pengxiang
  full_name: Wang, Pengxiang
  last_name: Wang
citation:
  ama: 'Pietrzak KZ, Wang P. Time-space tradeoffs of truncation with preprocessing.
    In: <i>6th Conference on Information-Theoretic Cryptography</i>. Vol 343. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href="https://doi.org/10.4230/LIPIcs.ITC.2025.4">10.4230/LIPIcs.ITC.2025.4</a>'
  apa: 'Pietrzak, K. Z., &#38; Wang, P. (2025). Time-space tradeoffs of truncation
    with preprocessing. In <i>6th Conference on Information-Theoretic Cryptography</i>
    (Vol. 343). Santa Barbara, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPIcs.ITC.2025.4">https://doi.org/10.4230/LIPIcs.ITC.2025.4</a>'
  chicago: Pietrzak, Krzysztof Z, and Pengxiang Wang. “Time-Space Tradeoffs of Truncation
    with Preprocessing.” In <i>6th Conference on Information-Theoretic Cryptography</i>,
    Vol. 343. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href="https://doi.org/10.4230/LIPIcs.ITC.2025.4">https://doi.org/10.4230/LIPIcs.ITC.2025.4</a>.
  ieee: K. Z. Pietrzak and P. Wang, “Time-space tradeoffs of truncation with preprocessing,”
    in <i>6th Conference on Information-Theoretic Cryptography</i>, Santa Barbara,
    CA, United States, 2025, vol. 343.
  ista: 'Pietrzak KZ, Wang P. 2025. Time-space tradeoffs of truncation with preprocessing.
    6th Conference on Information-Theoretic Cryptography. ITC: Information Theoretic
    Cryptography, LIPIcs, vol. 343, 4:1-4:10.'
  mla: Pietrzak, Krzysztof Z., and Pengxiang Wang. “Time-Space Tradeoffs of Truncation
    with Preprocessing.” <i>6th Conference on Information-Theoretic Cryptography</i>,
    vol. 343, 4:1-4:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a
    href="https://doi.org/10.4230/LIPIcs.ITC.2025.4">10.4230/LIPIcs.ITC.2025.4</a>.
  short: K.Z. Pietrzak, P. Wang, in:, 6th Conference on Information-Theoretic Cryptography,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
conference:
  end_date: 2025-08-17
  location: Santa Barbara, CA, United States
  name: 'ITC: Information Theoretic Cryptography'
  start_date: 2025-08-16
corr_author: '1'
cryptoeprintid: 1
das_tickbox: '0'
date_created: 2026-06-14T22:01:45Z
date_published: 2025-09-08T00:00:00Z
date_updated: 2026-06-22T08:57:41Z
day: '08'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.4230/LIPIcs.ITC.2025.4
external_id:
  cryptoeprintid:
  - 2025/723
file:
- access_level: open_access
  checksum: 3f791b03df26853342855a9d9581cb58
  content_type: application/pdf
  creator: dernst
  date_created: 2026-06-22T08:54:32Z
  date_updated: 2026-06-22T08:54:32Z
  file_id: '22118'
  file_name: 2025_LIPIcs_Pietrzak.pdf
  file_size: 772046
  relation: main_file
  success: 1
file_date_updated: 2026-06-22T08:54:32Z
has_accepted_license: '1'
intvolume: '       343'
keyword:
- Time-Space Lower Bounds
- Blockchains
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
publication: 6th Conference on Information-Theoretic Cryptography
publication_identifier:
  eissn:
  - 1868-8969
  isbn:
  - '9783959773850'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Time-space tradeoffs of truncation with preprocessing
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 343
year: '2025'
...