2026-07-23T17:34:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24354 2025-12-12T14:53:38Z ddc:004 open_access

Time-Space Tradeoffs of Truncation with Preprocessing Pietrzak, Krzysztof Wang, Pengxiang Time-Space Lower Bounds Blockchains 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Krzysztof Pietrzak and Pengxiang Wang 2025 Is Part Of LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2025.4 urn:nbn:de:0030-drops-243544 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.4 eng https://creativecommons.org/licenses/by/4.0/legalcode