Time-Space Tradeoffs of Truncation with Preprocessing

In [2] Baldimtsi, Chalkias, Chatzigiannis and Kelkar suggested truncation as a technique to shorten outputs of cryptographic primitives like hash values, signatures or public keys. The technique applies whenever there’s a part of the input that can be chosen arbitrarily, like the randomness in signing and key generation or parts of the input when hashing. The general idea is to simply try out many different inputs until the output lands in some sparse domain, say it starts with $\mathrm{\Delta }$ zeros, and such an output can be encoded using $\mathrm{\Delta }$ less bits than a general output.

While the applicability of this technique is limited by the fact that finding an output that starts with $\mathrm{\Delta }$ zeros will require around $2^{\mathrm{\Delta }}$ invocations of the primitive (so e.g., compressing by $20$ bits already requires around a million invocations), in [2] interesting applications are identified where this can make a big difference, including in the context of the Ethereum blockchain, where saving a few bits to be stored on-chain can lead to significant savings. We discuss another application to proofs of space as used in the Chia network in the open problems Section 6.

While truncation puts extra burden on the evaluator (say, a signer), there’s no extra cost for the parties that use the output (say, verify the signature). Moreover [2] show that truncation preserves security in the bit security framework of [9]. Informally, a primitive has bit security $\kappa$, if every adversary who breaks the security with advantage $ϵ$ must run in time $2^{\kappa }\cdot ϵ$.

While the preservation of bit security under truncation gives some confidence in this technique, it only considers a setting without precomputation. Unfortunately, truncation can decrease the security of primitives when the adversary is given some auxiliary input. Let us illustrate this considering the one-wayness of a permutation over $n$ bits, which we’ll denote with $f:[N]\to [N]$ where $N=2^n$. A random permutation $f$ does have $n$ bits of bit security, i.e., given a random $y\in [N]$, finding $x,f(x)=y$ will require $N/2$ invocations to $f$ in expectation. But given $S$ bits of advice (that depend on $f$ but not the challenge $y$), it’s possible to invert $f$ using just $T$ invocations whenever

The general idea is to compute and store values $x_0,x_T,x_{2T},\mathrm{\dots }$ where $x_i=f(x_{i-1})$. On challenge $y$ one now applies $f$ until one of the stored $x_{i\cdot T}$ values is hit, and then continues to apply $f$ to $x_{(i-1)T}$ until one hits $y$. For functions the best space-time tradeoff are somewhat worse. For random functions an attack with

is achieved by Hellman tables [7] or rainbow tables [8]. So, any permutation can be inverted with time and space, e.g. $T=S\approx N^{1/2}$ while random functions can be inverted with $T=S\approx N^{2/3}$ (for functions that are not random the existing bounds are somewhat worse [5]).

De, Trevisan and Tulsiani [4] (building on work by Yao [11], Gennaro-Trevisan [6] and Wee [10]) prove that the attack as in eq. (1) is basically optimal as any adversary who inverts a random permutation or function with a range of size $N$ must satisfy

Note that the above is seemingly wrong if $T=0$ or $S=0$ as one can invert with no space but $N$ queries or $N\log N$ space and no queries. The proof of the lower bound assumes adversary must always query $f$ on its output, so $T$ is at least $1$, and $S$ is assumed to be at least $\log N$ which is required to store the challenge.

The same lower bound applies for random functions, though note that in this case it’s not matching the upper bound. The actual lower bound is slightly more general showing that $S\cdot T\in \mathrm{\Omega }(ϵ\cdot N)$ must hold for any adversary who inverts with some probability $ϵ$, but for this introduction we assume $ϵ$ is some constant.

Now consider the truncated setting, where we have a random function or permutation $f:[N]\to [N]$, but must only invert it on outputs sampled from some truncated range, say where the first $\mathrm{\Delta }$ bits are set to zero. We’ll denote this range with $[\delta N]$ where $\delta =2^{-\mathrm{\Delta }}$.

Now one can store the $\delta N$ preimages of $f$ on $[\delta N]$ using $S=\delta N\log N$ bits, and using this advice, it’s possible to find the preimage $x,f(x)=y$ for any $y\in [\delta N]$ without invoking $f$ at all. As outlined above, this means $T=1$, but it still contradicts the lower-bound from eq. (2) as $\delta N\log N\notin \mathrm{\Omega }(N)$ for $\delta \in o(1/\log N)$.

The main result in this work is Theorem 4, which basically states that the issue just described is the only reason for the lower bound to fail: as long as $S$ is too small to basically store the entire function table of the truncated function, the $S\cdot T\in \mathrm{\Omega }(N)$ lower bound applies. While we state and prove the bound for functions, it can easily be adapted to permutations. We discuss other truncated primitive in the open problems Section 6.

The technical result implying Theorem 4 is stated in Lemma 5. It uses a so-called compression argument: it shows how an adversary that inverts a random function $f$ can be turned into an encoding for the function table of $f$, where the length of the encoding depends on the space and time efficiency of the adversary. As the function table of a random function is incompressible, as stated in Fact 1, we can derive a lower bound on the space and time complexity of the adversary.

The starting point for proving the Lemma is a proof of the $S\cdot T\ge N\log N$ lower bound for inverting random functions from [1]. This proof is less elegant than the proof of De et al. from [4], which uses a high level argument about sets, while [1] provide pseudocode of the encoding and argue about the length of its output.

Their encoding is basically Algorithm 1 in this paper for $\delta =1$. It takes as input an adversary $𝒜$ who is guaranteed to invert some function $f:[N]\to [N]$ on an $ϵ$ fraction of the range and making no more than $T$ queries.

$𝒜$ is then invoked on some challenges, and every time $𝒜$ inverts a challenge we get one entry in the function table “for free”. With every invocation, $𝒜$ can make up to $T$ queries to $f$, and those queries can later no longer be used as challenges, i.e., we “spoil” up to $T$ of the $ϵ\cdot N$ challenges with every succesful inversion. Overall we can get $𝒜$ to invert something in the order of $ϵ\cdot N/T$ challenges before running out of unspoiled challenges, and thus get an encoding that is around $ϵ\cdot N/T$ bits shorter than the function table. As a random function is incompressible, this then implies that the advice used by $𝒜$ must be around $S⪆ϵ\cdot N/T$. That’s how the $S\cdot T\in \mathrm{\Omega }(ϵ\cdot N)$ lower bound in [1] is proven.

In the truncated setting when $\delta \ll 1$, $𝒜$ is only guaranteed to invert on an $ϵ$ fraction of the sparse domain $[\delta N]$, and the above argument would only gives us a $S⪆\delta \cdot ϵ\cdot N/T$ bound.

A key observation is the fact that we get a $S⪆ϵ\cdot N/T$ lower bound even in the truncated case if we assume that not much more than a $\delta$ fraction of the queries made by $𝒜$ map to the sparse $[\delta \cdot N]$ domain, as then each compressed entry only spoils around $\delta \cdot T$ of the $[ϵN]$ available challenges.

To prove our lemma we now make a case distinction. If for every compressed value we typically do not spoil more than $T_g\le 12\delta T$ potential challenges, we use the observation above, so in this case we use basically the same argument as in [1].

In the other case the queries made by $𝒜$ fall into the sparse $[\delta N]$ set at least 12 times more often than a random query would. Knowing that the output $f(x)$ on a query $x$ is in $[\delta N]$ means we can encode it using just $\log N-\log 1/\delta$ bits. We will encode the positions of the queries made by $𝒜$ that fall into $[\delta N]$ (there are around $ϵ\delta N$ such queries) and then encode each output using just $\log N-\log 1/\delta$ bits. As the queries that fall into $[\delta N]$ are sufficiently dense (i.e., 12 times denser than a random query would), encoding those positions uses a bit less per entry than the $\log 1/\delta$ bits we save knowing the entry is in $[\delta N]$. So overall we save $ϵ\delta N$ bits, and thus for this case can conclude (again using the incompressibility of a random function table) that the space used by $𝒜$ must be at least $S⪆ϵ\delta N$.

If $T_g\le 12\delta T$, the theorem follows from Lemma 5 using Fact 1 as follows: assume the function table of $f$ in the lemma is chosen uniformly at random (i.e., $x$ in Fact 1 is a uniform $N\log N$ bit string), then the term in eq. (6) can be lower bounded as

Reordering we get

using our assumption that $T_g\le 12\delta T$

So $T\cdot S\in \mathrm{\Omega }(ϵN)$ as claimed (on the rhs of eq. (4) in the Theorem). Note that the extra assumption that $T\le ϵN/40$ in the lemma doesn’t matter, as if it’s not satisfied the theorem is trivially true.

If $T_g>12\delta T$, the theorem again follows from Lemma 5 using Fact 1, i.e., we again assume the function table of $f$ in the lemma is chosen uniformly at random (i.e., $x$ in Fact 1 is a uniform $N\log N$ bit string), and now the term in eq. (7) can be lower bounded as

Note that, as in this case we use eq. (7) rather than eq. (6), we have an extra $-\delta ϵN$ term on the lhs. Reordering we get

and thus $S\in \mathrm{\Omega }(\delta ϵN)$ as claimed.

We will now upper bound the size of the encoding of $G,f(Q^{\prime }),(|q_1|,\mathrm{\dots },|q_{|G|}|),f([N]-\{G^{-1}\cup Q^{\prime }\})$ as output in line (15) of the $\mathrm{𝖤𝗇𝖼}$ algorithm.

Let $T_g:=|B|/|G|$ be the average number of elements we added to the bad set $B$ for every element added to the good set $G$, then

To see this we note that when we leave the while loop (see line (8) of the algorithm $\mathrm{𝖤𝗇𝖼}$) it holds that

$G$:

Instead of $G$ we will actually encode the set ${\pi }^{-1}(G)=\{c_1,\mathrm{\dots },c_{|G|}\}$, from this encoding $\mathrm{𝖣𝖾𝖼}$ (who gets $r$, and thus knows $\pi$) can then reconstruct $G=\pi ({\pi }^{-1}(G))$. We claim that the elements in are whp. at least $ϵ\delta /2$ dense in $[c_{|G|}]$ (equivalently, $c_{|G|}\le 2|G|/ϵ\delta$). By Fact 2 we can thus encode ${\pi }^{-1}(G)$ using $|G|\log (2e/ϵ\delta )+\log N$ bits (the extra $\log N$ bits are used to encode the size of $G$ which is required so decoding later knows how to parse the encoding). To see that the $c_i$’s are $ϵ\delta /2$ dense whp. consider line (9) in $\mathrm{𝖤𝗇𝖼}$ which states $c:=\min \{c^{\prime }>c:y_{c^{\prime }}\in \{J\setminus B\}\}$. If we replace $J\setminus B$ with $J$, then the $c_i$’s would be whp. close to $ϵ\delta$ dense in $[N]$ as $J\subset N$ has size $ϵ\delta N$ and the $y_i$ are uniformly random. As , using $J\setminus B$ instead of $J$ will decrease the density by at most a factor $2$. If we don’t have this density, i.e., $c_{|G|}>2|G|/ϵ\delta$, we consider encoding to have failed.

$(|q_1^{\prime }|,\mathrm{\dots },|q_{|G|}^{\prime }|)$:

Require $|G|\log T$ bits as each $q_i^{\prime }\le q_i\le T$. A more careful argument (using Fact 2 and that the $q_i^{\prime }$ are on average at most $T_g$) requires $|G|\log (e{T}_g)$ bits.

$f([N]-\{G^{-1}\cup Q^{\prime }\})$:

Requires $(N-|G|-|Q^{\prime }|)\log N$ bits (using that $G^{-1}\cap Q^{\prime }=\mathrm{\varnothing }$ and $|G^{-1}|=|G|$).

$\mathrm{𝖺𝗎𝗑}$:

Is $S$ bits long.

$f(Q^{\prime })$:

This is a list of $|Q^{\prime }|$ elements in $[N]$ and can be encoded using $|Q^{\prime }|\log N$ bits, but we’ll encode it with less if $T_g$ is large.

Summing up we get

Using the assumption $T_g\le T\le ϵ\delta N/40$ in the statement of the lemma, which in turn implies $\log (2e^2{T}_g/ϵ\delta )\le \log (N)-1$, we get

Plugging in the bound from eq. (8) for $|G|$ we get

proving eq. (6) in the Lemma.

We’ll now prove a bound on the length of the encoding as stated in eq. (7) in the lemma. Here we assume that $T_g$ is large, i.e., $T_g>12\delta T$. The bound on the length of the encoding improves the expression we got without this assumption, i.e., eq. (6), by $\delta ϵN$ bits. We will achieve this by improving the length of the encoding of $f(Q^{\prime })$ from the trivial $|Q^{\prime }|\log (N)$ to $|Q^{\prime }|\log (N)-\delta ϵN$ by exploiting the fact that now a large fraction of the elements in $f(Q^{\prime })$ falls into the sparse set $[\delta N]$, i.e.,

With this claim we can improve eq. (5.1) to $(N-|Q^{\prime }|)\log N+|Q^{\prime }|\log (N)-|G|+S+\log N$, which now gives eq. (7) from the Lemma.

It remains to prove the claim. By eq. (8) and eq. (9) $|G|\ge \delta ϵN/2T_g$, $|Q^{\prime }|\le T\cdot |G|$ and $|B|\ge \delta ϵN/2$, which implies

I.e., a $12\delta$ fraction of the queries made during decoding falls into $B\subset [\delta N]$. Using this with Fact 2 we can encode which of the $|B|$ queries from $Q^{\prime }$ map into $B$ using $|B|\log (e/12\delta )$ bits. For any $x\in B$, we can encode $f(x)$ using $\log (N)-\log (1/\delta )$ bits as $f(x)\in [\delta N]$.

We can now encode $f(Q^{\prime })$ by first encoding the positions of $B$ in $Q^{\prime }$, and then $f(B)$ and $f(Q^{\prime }\setminus B)$ separately, which requires

bits as claimed.