Time-space tradeoffs of truncation with preprocessing

conference paper Time-space tradeoffs of truncation with preprocessing LIPIcs published yes Krzysztof Z Pietrzak author 3E04A7AA-F248-11E8-B48F-1D18A9856A870000-0002-9139-1654 Pengxiang Wang author KrPi department ITC: Information Theoretic Cryptography 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. Using 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. Concretely, 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. We 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. https://research-explorer.ista.ac.at/download/22007/22118/2025_LIPIcs_Pietrzak.pdf application/pdfno Schloss Dagstuhl - Leibniz-Zentrum für Informatik2025Santa Barbara, CA, United States eng Time-Space Lower BoundsBlockchains 6th Conference on Information-Theoretic Cryptography 1868-8969 978395977385010.4230/LIPIcs.ITC.2025.4 343 K. Z. Pietrzak and P. Wang, “Time-space tradeoffs of truncation with preprocessing,” in 6th Conference on Information-Theoretic Cryptography, Santa Barbara, CA, United States, 2025, vol. 343. Pietrzak, Krzysztof Z, and Pengxiang Wang. “Time-Space Tradeoffs of Truncation with Preprocessing.” In 6th Conference on Information-Theoretic Cryptography, 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>. Pietrzak KZ, Wang P. Time-space tradeoffs of truncation with preprocessing. In: 6th Conference on Information-Theoretic Cryptography. 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> 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. K.Z. Pietrzak, P. Wang, in:, 6th Conference on Information-Theoretic Cryptography, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. Pietrzak, K. Z., & Wang, P. (2025). Time-space tradeoffs of truncation with preprocessing. In 6th Conference on Information-Theoretic Cryptography (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> Pietrzak, Krzysztof Z., and Pengxiang Wang. “Time-Space Tradeoffs of Truncation with Preprocessing.” 6th Conference on Information-Theoretic Cryptography, 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>. 220072026-06-14T22:01:45Z2026-06-22T08:57:41Z