Improved Rate for Non-Malleable Codes and Time-Lock Puzzles

We are interested in encoding schemes consisting of public, polynomial-time encoding and decoding algorithms $(\mathrm{𝖤𝗇𝖼},\mathrm{𝖣𝖾𝖼})$. While conceptually similar, we compare CCA-hiding and non-malleability explicitly to clarify their differences.

• $\mathrm{■}$

  CCA-hiding requires that, for any pair of messages $m_0,m_1$, any bounded distinguisher $D$ (from a specified class of adversaries that can’t compute $\mathrm{𝖣𝖾𝖼}(\cdot )$) can’t predict $b$ given a code $c\leftarrow \mathrm{𝖤𝗇𝖼}(m_b)$, even given an oracle for $\mathrm{𝖣𝖾𝖼}(\cdot )$ on any input $c^{\prime }\ne c$.

• $\mathrm{■}$

  Non-malleability is modeled via the following “meddler-in-the-middle” (MIM) experiment for a bounded mauling adversary $M$ and message $m$,

  $${\mathrm{𝖬𝖨𝖬}}_M(m):=\mathrm{𝖣𝖾𝖼}(M(\mathrm{𝖤𝗇𝖼}(m))),$$

  where $\mathrm{𝖣𝖾𝖼}(\cdot )$ returns $\perp$ if $M$ simply copies the encoding $c$ it receives as input. Non-malleability requires that, for any pair of messages $m_0,m_1$, any polynomial-time distinguisher $D$ (that can compute $\mathrm{𝖣𝖾𝖼}(\cdot )$) can’t predict $b$ given $\tilde{m}\leftarrow {\mathrm{𝖬𝖨𝖬}}_M(m_b)$.¹¹1We follow the notion of non-malleability from [40] for non-malleable TLPs, which is necessary for their applications to multi-party coin-flipping and auctions. In the NMC literature, this is sometimes referred to as “strong” non-malleability where we additionally protect against attacks that maul the code $c$ to a fresh encoding $c^{\prime }\ne c$ for the same underlying message $m$.

We summarize the above two security games in Figure 1 below.

The above two definitions are similar in that they give the security experiment limited access to a decoding oracle $\mathrm{𝖣𝖾𝖼}(\cdot )$. However, they differ in that CCA-hiding ensures indistinguishability against bounded adversaries that can adaptively query $\mathrm{𝖣𝖾𝖼}(\cdot )$, whereas non-malleability ensures indistinguishability against arbitrary polynomial-time adversaries for the output of one call to $\mathrm{𝖣𝖾𝖼}(\cdot )$. While the classical notion of CCA-security implies non-malleability for encryption or commitments, we will see that this is not the case in the fine-grained setting of codes.²²2In particular, [40] give a construction that is malleable yet satisfies a restricted notion of CCA-hiding for one oracle call to $\mathrm{𝖣𝖾𝖼}(\cdot )$. Still, we will show that CCA-hiding is a useful tool for composition, and in particular, for achieving non-malleability.

In the rest of the section, we give an overview of our main results, summarized as follows:

• $\mathrm{■}$

  We give a generic transformation from any CCA-hiding encoding scheme to a rate-1 CCA-hiding encoding scheme. This transformation relies only on the existence of collision resistant hash functions. We note that this transformation also applies to non-interactive commitments.

• $\mathrm{■}$

  We next give a direct construction of a rate-1 non-malleable code for bounded polynomial-depth tampering. This construction is in the auxiliary-input random oracle model (AI-ROM) of Unruh [81], where the adversary in the security game is allowed to depend arbitrarily on the random oracle.

• $\mathrm{■}$

  Lastly, we give a generic transformation from any CCA-hiding encoding scheme to a rate-1/2 non-malleable encoding scheme in the AI-ROM.

Non-malleable codes were first introduced by [35] and have been constructed for a variety of adversarial tampering classes including split-state tampering [35, 67, 28, 4, 3], algebraic tampering [9], bounded space tampering [37, 14], bounded size tampering [35, 38, 14, 11, 15, 17], or bounded depth tampering [12, 10, 16, 33]. The various works above give constructions in a variety of settings (probabilistic vs. explicit constructions, CRS vs. plain model, inverse polynomial vs. negligible security), but in this work, we are primarily interested in explicit constructions without a CRS that achieve negligible security against either bounded polynomial-size or -depth adversaries. Also, to the best of our knowledge, CCA-hiding has not been explicitly studied in the context of non-malleable codes.

Non-malleable TLPs (and the related notion of non-malleable non-interactive timed commitments) have received significant attention due to their applications to distributed protocols like coin-flipping, fair auctions, and broadcast [23, 40, 21, 79, 80, 36, 8]. While some non-malleable TLP constructions rely on adversary-independent setup [56, 21, 79, 80, 29, 7], we are primarily interested in the fully non-interactive setting in this work following [40] and inspired by the original notion of TLPs from [77]. We note that Katz, Loss, and Xu [56] define a notion of CCA-hiding for non-interactive timed commitments, which was subsequently considered in the works of [79, 29, 7]. [79] show that this notion suffices for “short-lived” applications that only require indistinguishability for a limited amount of time. Following [40], we are primarily concerned with applications that guarantee the standard notion of computational indistinguishability against arbitrary polynomial-time attackers.

Non-malleable and CCA-secure (even interactive) commitments have been extremely useful for building more efficient and secure multi-party computation protocols [19, 82, 27, 64, 61, 48, 65, 24]. This has led to a long sequence of works trying to minimize the round complexity and assumptions needed for constructing such commitments [34, 19, 74, 73, 66, 71, 62, 75, 82, 46, 63, 47, 49, 30, 31, 58, 65, 60, 22, 53, 50, 42, 59, 43]. Despite known black-box barriers for constructing non-interactive non-malleable commitments [72], there has been significant progress recently in the fully non-interactive setting that we consider in this work [71, 65, 22, 53, 42, 59, 43].

Our work is not the first to explore rate-optimizing compilers for non-malleable codes (NMCs). All existing compilers, including ours, follow a similar overarching design inspired by the “hybrid” encryption paradigm: each combines a low-rate non-malleable code with a form of symmetric-key authenticated encryption. However, despite this high-level resemblance, the specific instantiations of these components differ significantly across works, and each setting presents unique challenges.

The most closely related work to ours is [17] as they consider tampering classes that may touch the entire codeword. However, as discussed before, their construction does not achieve negligible security. All other compilers are for settings where the tampering is subject to some form of locality constraint: each tampered output bit is computed by a function that has access only to partial information from the original codeword.

• $\mathrm{■}$

  Local Tampering: The first rate compiler by [6] boosted NMCs for 1-local tampering to rate 1 by combining threshold secret sharing with bit-flipping and error correction. Later, [52] extended these ideas (together with ideas from [13]) to achieving rate 1 NMCs for $c\log n$-local functions.

• $\mathrm{■}$

  Computational Split-State Tampering: [2] showed how to obtain rate 1 NMCs for polynomial-time split-state tampering by encoding a high-rate authenticated encryption key using an augmented split-state NMC, introducing the notion of augmented non-malleability to address joint tampering across components.

• $\mathrm{■}$

  Split-State Tampering: A sequence of works [54, 55, 51, 5] used compilers to improve the rate of NMCs for split-state and $t$-state tampering, culminating in an explicit rate 1/3 NMC for 2-state tampering – the best known to date. These compilers rely on leakage-resilient encodings combined with information-theoretic MACs and use seeded extractors and low-rate NMCs to protect the seeds and keys. The key technical challenge lies in preserving independence between tampering states.

While we eventually argue CCA-hiding of this construction, it will be instructive to present and analyze the security as if it were a non-malleability experiment for a bounded depth distinguisher $D$. For messages $m_0,m_1$, recall that the experiment consists of a bounded depth mauler $M$ that receives a challenge TLP $c\leftarrow \mathrm{𝖤𝗇𝖼}(m_b)$ for a random bit $b$ as input. $M$ tries to maul $c$ to a new TLP $\tilde{c}$, with underlying message $\tilde{m}$. Then, a distinguisher $D$ given $\tilde{m}$ tries to predict the original bit $b$.

We now look at the different ways that $M$ could potentially maul the challenge TLP $c$. Recall that the encoding $c$ consists of two parts: $c^{\prime }\leftarrow {\mathrm{𝖤𝗇𝖼}}^{\prime }(s,\mathrm{𝗁𝗄},\mathrm{𝖽𝗂𝗀})$ for $\mathrm{𝖽𝗂𝗀}=\mathrm{𝖧𝖺𝗌𝗁}(\mathrm{𝗁𝗄},m_b)$, and $\mathrm{𝗉𝖺𝖽}=𝖦(s)\oplus m_b$. $M$ then outputs a new TLP $\tilde{c}=({\tilde{c}}^{\prime },\stackrel{~}{}\mathrm{𝗉𝖺𝖽})$.

• $\mathrm{■}$

  First, if ${\tilde{c}}^{\prime }=c^{\prime }$, meaning that $M$ copied the first input, then it must be the case that $\stackrel{~}{}\mathrm{𝗉𝖺𝖽}\ne \mathrm{𝗉𝖺𝖽}$ (otherwise the whole TLP was copied, which isn’t allowed). Since ${\tilde{c}}^{\prime }$ was copied, it decodes to the same underlying values $(s,\mathrm{𝗁𝗄},\mathrm{𝖽𝗂𝗀})$ as $c^{\prime }$. The candidate message $\widehat{m}=𝖦(s)\oplus \stackrel{~}{}\mathrm{𝗉𝖺𝖽}$ must be different from $m_b$ since $\stackrel{~}{}\mathrm{𝗉𝖺𝖽}\ne \mathrm{𝗉𝖺𝖽}$. But that means that $\mathrm{𝖣𝖾𝖼}(\tilde{c})$ outputs a non-$\perp$ value (that could potentially be useful for $D$) only if $\mathrm{𝖧𝖺𝗌𝗁}(\mathrm{𝗁𝗄},\widehat{m})=\mathrm{𝖽𝗂𝗀}=\mathrm{𝖧𝖺𝗌𝗁}(\mathrm{𝗁𝗄},m_b)$, resulting in a collision!

• $\mathrm{■}$

  If ${\tilde{c}}^{\prime }\ne c^{\prime }$, then the underlying values $(\tilde{s},\stackrel{~}{}\mathrm{𝗁𝗄},\stackrel{~}{}\mathrm{𝖽𝗂𝗀})$ should be “unrelated” to $(s,\mathrm{𝗁𝗄},\mathrm{𝖽𝗂𝗀})$ – and hence $m_b$ – if the underlying TLP is non-malleable. So, we would hope to show that this means $\tilde{m}=𝖦(\tilde{s})\oplus \stackrel{~}{}\mathrm{𝗉𝖺𝖽}$ is also unrelated to $m_b$. Formalizing this intuition is a bit tricky, and it turns out that non-malleability alone will not suffice for the underlying TLP.

To analyze the second case above, let’s examine the non-malleability game in a bit more detail.

• $\mathrm{■}$

  Non-Malleability Experiment for $(\mathrm{𝖤𝗇𝖼},\mathrm{𝖣𝖾𝖼})$:

  1. 1.

     A code $c=(c^{\prime },\mathrm{𝗉𝖺𝖽})\leftarrow \mathrm{𝖤𝗇𝖼}(m_b)$ is sampled for $m_b$.

     • –

       Recall that $c^{\prime }\leftarrow {\mathrm{𝖤𝗇𝖼}}^{\prime }(s,\mathrm{𝗁𝗄},\mathrm{𝖽𝗂𝗀})$ for $\mathrm{𝖽𝗂𝗀}=\mathrm{𝖧𝖺𝗌𝗁}(\mathrm{𝗁𝗄},m_b)$ and $\mathrm{𝗉𝖺𝖽}=𝖦(s)\oplus m_b$.

  2. 2.

     The mauler outputs a tampered codeword $\stackrel{~}{}c=(\stackrel{~}{}{c}^{\prime },\stackrel{~}{}\mathrm{𝗉𝖺𝖽})\leftarrow M(c)$.

  3. 3.

     The MIM experiment outputs $\tilde{m}=\mathrm{𝖣𝖾𝖼}(\tilde{c})$ as long as $\tilde{c}\ne c$.

     • –

       Recall that $\mathrm{𝖣𝖾𝖼}({\tilde{c}}^{\prime },\stackrel{~}{}\mathrm{𝗉𝖺𝖽})$ decodes $(\tilde{s},\stackrel{~}{}\mathrm{𝗁𝗄},\stackrel{~}{}\mathrm{𝖽𝗂𝗀})={\mathrm{𝖣𝖾𝖼}}^{\prime }({\tilde{c}}^{\prime })$, computes a candidate message $\widehat{m}=𝖦(\tilde{s})\oplus \stackrel{~}{}\mathrm{𝗉𝖺𝖽}$, and outputs $\tilde{m}=\widehat{m}$ if $\stackrel{~}{}\mathrm{𝖽𝗂𝗀}=\mathrm{𝖧𝖺𝗌𝗁}(\mathrm{𝗁𝗄},\widehat{m})$.

     • –

       If ${\tilde{c}}^{\prime }=c^{\prime }$, we argued that this results in a collision. So, it must be the case that ${\tilde{c}}^{\prime }\ne c^{\prime }$.

  4. 4.

     The distinguisher predicts a bit $b^{\prime }=D(\tilde{m})$ and wins if $b^{\prime }=b$.

To formalize the intuition that $\tilde{m}$ should be “unrelated” to $(s,\mathrm{𝗁𝗄},\mathrm{𝖽𝗂𝗀})$, we need to argue that the output of the non-malleability experiment doesn’t significantly change in a hybrid experiment where we instead sample the value $c^{\prime }\leftarrow {\mathrm{𝖤𝗇𝖼}}^{\prime }(0^{|s|+|\mathrm{𝗁𝗄}|+|\mathrm{𝖽𝗂𝗀}|})$. This requires that the non-malleability experiment is “hiding” for ${\mathrm{𝖤𝗇𝖼}}^{\prime }$, but this can’t be the case since the experiment has to compute $\mathrm{𝖣𝖾𝖼}(\tilde{c})$! This is where CCA-hiding comes to save the day; it guarantees that hiding of ${\mathrm{𝖤𝗇𝖼}}^{\prime }$ still holds even if you can compute ${\mathrm{𝖣𝖾𝖼}}^{\prime }({\tilde{c}}^{\prime })$ on ${\tilde{c}}^{\prime }\ne c^{\prime }$. Furthermore, we’ve already argued this is the only interesting case based on the collision-resistance of $\mathrm{𝖧𝖺𝗌𝗁}$.

Now, after making $c^{\prime }$ independent of $s$ and $m_b$, we can use the pseudo-randomness of $𝖦$ to move to a hybrid where $\mathrm{𝗉𝖺𝖽}\leftarrow {\{0,1\}}^{|m_b|}$ is uniformly random and independent of $m_b$. The resulting experiment is independent of $b$, so $D$ has no advantage for predicting $b$.

We note that we can extend the above argument to also capture the setting where $M$ might make additional adaptive queries to $\mathrm{𝖣𝖾𝖼}(\cdot )$, but we still require that the distinguisher $D$ is depth bounded. This game corresponds exactly to the CCA-hiding security game, which is why the above construction works for general CCA-hiding.

To encode a message $m$, we first encode a seed $s$ with a hash key $\mathrm{𝗁𝗄}$ and a succinct, hiding commitment to $m$ via $𝒪(\mathrm{𝗁𝗄}\Vert m\Vert \rho )$ using randomness $\rho$. Next, we give out a random string $r\leftarrow {\{0,1\}}^{|m|}$ that is the same length as $m$. Finally, we use $𝒪(s||r)$ to mask the message $m$ along with the commitment randomness $\rho$. Altogether, our new construction is

To decode, you can first decode $(s,\mathrm{𝗁𝗄},\mathrm{𝖼𝗈𝗆})$ from $c^{\prime }$, unmask $\mathrm{𝗉𝖺𝖽}$ to get a candidate message and randomness $(\widehat{m}||\rho )=\mathrm{𝗉𝖺𝖽}\oplus 𝒪(s||r)$, and output $m:=\widehat{m}$ if $\mathrm{𝖼𝗈𝗆}=𝒪(\mathrm{𝗁𝗄}\Vert \widehat{m}\Vert \rho )$. The construction is rate-$1/2$ since it includes $r$ which is roughly the same length as the message $m$, and otherwise the additional overheads depend only on the security parameter $\lambda$ and are independent of $|m|$.

Our goal is to rule out all possible mauling attacks. Let $c=(c^{\prime },r,\mathrm{𝗉𝖺𝖽})$ denote the challenge TLP, and $\tilde{c}=({\tilde{c}}^{\prime },\tilde{r},\stackrel{~}{}\mathrm{𝗉𝖺𝖽})$ denote the mauled TLP. Then every mauling attack must fall into one of the following two cases:

• $\mathrm{■}$

  First, if $({\tilde{c}}^{\prime },\tilde{r})=(c^{\prime },r)$, it again must be the case that $\stackrel{~}{}\mathrm{𝗉𝖺𝖽}\ne \mathrm{𝗉𝖺𝖽}$ if the whole TLP wasn’t copied. But when $c^{\prime }$ and $r$ are unchanged, the mauled TLP must use the same values $s$ and $r$ to unmask $\stackrel{~}{}\mathrm{𝗉𝖺𝖽}\ne \mathrm{𝗉𝖺𝖽}$. So, when decoding $\tilde{c}$, this results in different candidate message and randomness $(\widehat{m}||\tilde{\rho })=𝒪(s||r)\oplus \stackrel{~}{}\mathrm{𝗉𝖺𝖽}$ compared to the $m$ and $\rho$ used to generate the challenge TLP $c$. It follows that if $\tilde{c}$ is a valid encoding, this results in a collision on $𝒪(\mathrm{𝗁𝗄}||\cdot )$ since $𝒪(\mathrm{𝗁𝗄}\Vert m\Vert \rho )=\mathrm{𝖼𝗈𝗆}=𝒪(\mathrm{𝗁𝗄}\Vert \widehat{m}\Vert \tilde{\rho })$, which is unlikely to occur.

• $\mathrm{■}$

  Otherwise, it must be the case that either ${\tilde{c}}^{\prime }\ne c^{\prime }$ or $\tilde{r}\ne r$, meaning the value $𝒪(\tilde{s}||\tilde{r})$ used to mask the mauled message is likely to be different when decoding $\tilde{c}$ compared to the challenge TLP $c$. Our goal in this case is to argue that the original value $𝒪(s||r)$ used to mask $(m_b||\rho )$ can be lazily sampled independent from the rest of the non-malleability experiment. If this were the case, $\mathrm{𝗉𝖺𝖽}=𝒪(s||r)\oplus (m_b||\rho )$ would reveal no information about $m_b$ or $\rho$, meaning that the commitment $\mathrm{𝖼𝗈𝗆}=𝒪(\mathrm{𝗁𝗄}\Vert m_b\Vert \rho )$ also reveals no information about $m_b$, and we’d be done!

As stated above, our goal is to argue that the output of $𝒪(s||r)$ can be sampled lazily and is independent of the rest of the experiment, meaning the rest of the experiment never queries $𝒪$ on $(s||r)$. To help argue this, let’s take a closer look at how the non-malleability experiment queries $𝒪$ on such values.

• $\mathrm{■}$

  Non-Malleability Experiment for $({\mathrm{𝖤𝗇𝖼}}^{𝒪},{\mathrm{𝖣𝖾𝖼}}^{𝒪})$:

  1. 1.

     A code $c\leftarrow {\mathrm{𝖤𝗇𝖼}}^{𝒪}(m_b)$ is sampled for $m_b$.

  2. 2.

     The mauler outputs a tampered codeword $\stackrel{~}{}c=(\stackrel{~}{}{c}^{\prime },\tilde{r},\stackrel{~}{}\mathrm{𝗉𝖺𝖽})\leftarrow M^{𝒪}(c)$.

  3. 3.

     The MIM experiment outputs $\tilde{m}={\mathrm{𝖣𝖾𝖼}}^{𝒪}(\tilde{c})$ as long as $\tilde{c}\ne c$.

     • –

       If ${\tilde{c}}^{\prime }\ne c^{\prime }$, compute $\tilde{m}$ by querying $𝒪(\tilde{s}||\tilde{r})$ for $\tilde{s}$ output by ${\mathrm{𝖣𝖾𝖼}}^{\prime }({\tilde{c}}^{\prime })$.

     • –

       If ${\tilde{c}}^{\prime }=c^{\prime }$ but $\tilde{r}\ne r$, compute $\tilde{m}$ by querying $𝒪(s||\tilde{r})$.

  4. 4.

     The distinguisher predicts a bit $b^{\prime }=D^{𝒪}(\tilde{m})$ and wins if $b^{\prime }=b$.

To argue that the experiment doesn’t query $𝒪(s||r)$ computed by ${\mathrm{𝖤𝗇𝖼}}^{𝒪}(m_b)$, we separately argue that $M^{𝒪}$, ${\mathrm{𝖣𝖾𝖼}}^{𝒪}$, and $D^{𝒪}$ are unlikely to query $𝒪(s||r)$. At a very high level, this is because

• $\mathrm{■}$

  $M^{𝒪}$ and ${\mathrm{𝖣𝖾𝖼}}^{𝒪}$ have incomplete information on $s$, and

• $\mathrm{■}$

  $D^{𝒪}$ has incomplete information on $r$.

To formalize the first point, we rely on the CCA-hiding of $({\mathrm{𝖤𝗇𝖼}}^{\prime },{\mathrm{𝖣𝖾𝖼}}^{\prime })$. Namely, steps 2. and 3. in the case ${\tilde{c}}^{\prime }\ne c^{\prime }$ above can be computed in bounded depth $\ll t$ given the challenge TLP $c$ using $M^{𝒪}$ and given oracle access to ${\mathrm{𝖣𝖾𝖼}}^{\prime }({\tilde{c}}^{\prime })$. So, if $M$ or $\mathrm{𝖣𝖾𝖼}$ in this case ever query $𝒪$ at some value $(s||\cdot )$ for the random $s$ underlying $c_{\mathrm{𝗍𝗅𝗉}}$, this must violate CCA-hiding of $({\mathrm{𝖤𝗇𝖼}}^{\prime },{\mathrm{𝖣𝖾𝖼}}^{\prime })$. For the case ${\tilde{c}}^{\prime }=c^{\prime }$, note that this step only ever queries $𝒪(s||\tilde{r})$ for $\tilde{r}\ne r$, so it also never queries $𝒪(s||r)$.

To formalize the second point, note that $D^{𝒪}$ only receives a string $\tilde{m}$ of length $|m_b|$ as input and makes polynomially many queries to $𝒪$. This means that the set of all possible queries for which $D^{𝒪}$ might have some information on is at most $2^{|m_b|}\cdot \mathrm{𝗉𝗈𝗅𝗒}(\lambda )$. However, since we chose $|r|=|m_b|+\lambda$, $r$ has $|m_b|+\lambda$ bits of entropy, implying that $D^{𝒪}$ is very unlikely to make any query of the form $(\cdot ||r)$. Note that this argument is information theoretic, and only makes use of the fact that the input to $D$ is bounded, limiting the amount of information that can be passed to $D$. Indeed, this argument holds for any polynomial-time $D$ that may run in depth $\ge t$.

As mentioned above, it follows that $𝒪(s||r)$ can be replaced with a uniformly random string in the non-malleability experiment, so $\mathrm{𝗉𝖺𝖽}$ is a uniformly random string independent of the rest of the experiment. Then, since $\mathrm{𝖼𝗈𝗆}=𝒪(\mathrm{𝗁𝗄}\Vert m_b\Vert \rho )$ hides $m$ for random $\rho$, the experiment is independent of $m_b$, so even a polynomial-time distinguisher $D$ has no advantage for predicting $b$.

In Section 5, we additionally show that the construction above satisfies functional non-malleability, where the mauler may output a sequence of codes ${\tilde{c}}_1,\mathrm{\dots },{\tilde{c}}_k$ with underlying messages ${\tilde{m}}_1,\mathrm{\dots },{\tilde{m}}_k$. Then, we show that the output of any function $y=f({\tilde{m}}_1,\mathrm{\dots },{\tilde{m}}_k)$ doesn’t depend on the input message $m$ to the experiment as long as $|r|$ is as long as the length of the functions output $|y|$. Furthermore, the analysis above holds for any (potentially unbounded) function $f$ that doesn’t query $𝒪$, or for bounded depth functions $f$ that may query $𝒪$.

In Section 5.1, we show that if the underlying TLP in the compiler satisfies certain “fully homomorphic” properties, then the resulting TLP is malleable for any concrete instantiation $H$ of the oracle $𝒪$.⁴⁴4Somewhat surprisingly, a TLP can satisfy both CCA-hiding while also being fully homomorphic as we define in Definition 5.14. At a high level, this is because our argument above relies on the extractability of $𝒪$; you have to “know” $s$ to compute $𝒪(s||r)$. However, we show a concrete attack in case you you can homomorphically evaluate $H(s||r)$ under the inner TLP for some concrete instantiation $H$ for $𝒪$. Still, for most natural TLP candidates, the resulting TLP may still be non-malleable, and we also view this is a important first step towards a secure construction in the plain model.

The blueprint of our construction is similar to our previous compilers and relies on a random oracle $𝒪$. Rather than encode the seed $s$, however, we simply give $s$ in the clear. We then use the $t$-fold iteration of $𝒪$ on input $s$, which we denote by ${𝒪}^{(t)}(s)$, to mask the message $m$. We note that an encoding consisting of $s$ and $\mathrm{𝗉𝖺𝖽}={𝒪}^{(t)}(s)\oplus m$ already suffices to hide $m$ against bounded depth attackers, but is clearly malleable by just adding $1$ to $\mathrm{𝗉𝖺𝖽}$.

To avoid this simple attack, we again rely on a succinct, hiding commitment to bind the mauler to the seed $s$ and message $m$. We also mask the commitment randomness $\rho$ and append a commitment $\mathrm{𝖼𝗈𝗆}=𝒪(s\Vert m\Vert \rho )$ to the encoding. In sum, a code consists of the seed $s$, a one-time pad $\mathrm{𝗉𝖺𝖽}={𝒪}^{(t)}(s)\oplus (m||\rho )$, and a commitment $\mathrm{𝖼𝗈𝗆}=𝒪(s\Vert m\Vert \rho )$. Unfortunately, this construction is still malleable; it suffers the same mauling attack from Section 2.1. While it is hard for a depth $\ll t$ mauler $M$ to compute ${𝒪}^{(t)}(s)$ for a random $s$, it can hardcode pairs $(s,{𝒪}^{(t)}(s))$ in its non-uniform advice, letting it generate a valid encoding $\tilde{c}=\mathrm{𝖤𝗇𝖼}(m)$ for any message $m$ of its choice. Combined with the fact that the seed $s$ and first bit of $\mathrm{𝗉𝖺𝖽}$ reveals part of the message to polynomial-time distinguishers, this gives a valid mauling attack.

Our final construction modifies the above approach very slightly but significantly. We add ${𝒪}^{(t)}(m)$ to the commitment, so $\mathrm{𝖼𝗈𝗆}=𝒪(s||m||{𝒪}^{(t)}(m)||\rho )$. This gives our code,

To decode, you use the given seed $s$ to unmask $\mathrm{𝗉𝖺𝖽}$ and get a candidate message and randomness $(\widehat{m}||\rho )={𝒪}^{(t)}(s)\oplus \mathrm{𝗉𝖺𝖽}$. The decoding algorithm then outputs $m:=\widehat{m}$ if $\mathrm{𝖼𝗈𝗆}=𝒪(s||\widehat{m}||{𝒪}^{(t)}(\widehat{m})||\rho ))$. The construction is rate-1 since $s$, $\rho$, and $\mathrm{𝖼𝗈𝗆}$ can all have length independent of $|m|$.

We note that the slight modification above is inspired by the notion of a “hard-to-sample” function from [78] used in the rate-1 non-malleable code of [17]. At a very high level, it ensures that any mauler $M$ can only compute $\mathrm{𝖤𝗇𝖼}(m)$ for a bounded set of messages $m$ where the pair $(m,{𝒪}^{(t)}(m))$ is already hardcoded in its non-uniform advice. This limits the potential messages that can be “passed” to a distinguisher $D$, without relying on a long random string $r$ as in the construction of Section 2.2.

Our high level goal is to argue that the output of ${𝒪}^{(t)}(s)$ can be lazily sampled independent to the rest of the non-malleability experiment for message $m_b$. If we can show this, we can switch to a hybrid experiment where $\mathrm{𝗉𝖺𝖽}$ is uniformly random and independent from $m_b$ and $\rho$. But this implies that $\mathrm{𝖼𝗈𝗆}$ also hides $m_b$, so any distinguisher $D$ would have no advantage at guessing $\mathrm{𝖤𝗇𝖼}(m_b)$ for a random bit $b$. With this in mind, let’s take a closer look at the non-malleability experiment for $({\mathrm{𝖤𝗇𝖼}}^{𝒪},{\mathrm{𝖣𝖾𝖼}}^{𝒪})$.

• $\mathrm{■}$

  Non-Malleability Experiment for $({\mathrm{𝖤𝗇𝖼}}^{𝒪},{\mathrm{𝖣𝖾𝖼}}^{𝒪})$:

  1. 1.

     A code $c=(s,\mathrm{𝗉𝖺𝖽},\mathrm{𝖼𝗈𝗆})\leftarrow {\mathrm{𝖤𝗇𝖼}}^{𝒪}(m_b)$ is sampled for $m_b$.

  2. 2.

     The mauler outputs a tampered codeword $\stackrel{~}{}c=(\tilde{s},\stackrel{~}{}\mathrm{𝗉𝖺𝖽},\stackrel{~}{}\mathrm{𝖼𝗈𝗆})\leftarrow M^{𝒪}(c)$.

  3. 3.

     The MIM experiment outputs $\tilde{m}={\mathrm{𝖣𝖾𝖼}}^{𝒪}(\tilde{c})$ as long as $\tilde{c}\ne c$.

     • –

       Note that $\tilde{m}$ is derived by unmasking $\stackrel{~}{}\mathrm{𝗉𝖺𝖽}$ with ${𝒪}^{(t)}(\tilde{s})$.

  4. 4.

     The distinguisher predicts a bit $b^{\prime }=D^{𝒪}(\tilde{m})$ and wins if $b^{\prime }=b$.

To argue that the experiment doesn’t query the output of ${𝒪}^{(t)}(s)$ computed by ${\mathrm{𝖤𝗇𝖼}}^{𝒪}(m_b)$, we separately argue that $M^{𝒪}$, ${\mathrm{𝖣𝖾𝖼}}^{𝒪}$, and $D^{𝒪}$ are unlikely to compute such a query.

• $\mathrm{■}$

  First, $M^{𝒪}$ runs in depth $\ll t$, so the only way it could possibly compute the output of ${𝒪}^{(t)}(s)$ is if it already had hardcoded advice about $s$. This is very unlikely, however, since $s$ is randomly chosen in the experiment independent of $M^{𝒪}$.

• $\mathrm{■}$

  For ${\mathrm{𝖣𝖾𝖼}}^{𝒪}$, we consider two separate cases:

  • –

    If $\tilde{s}\ne s$, we claim that the path of queries for ${𝒪}^{(t)}(\tilde{s})$ is very unlikely to collide with the path for ${𝒪}^{(t)}(s)$. For starters, we can domain separate the initial query to ensure that $\tilde{s}$ is not already in the path of $s$. It follows that the values on the path queried by ${𝒪}^{(t)}(s)$ are all random and independent of $M^{𝒪}$, so $M^{𝒪}$ is very unlikely to have any hardcoded information on $𝒪$ to come up with such a $\tilde{s}$.

  • –

    If $\tilde{s}=s$, we observe that the experiment can derive the same value for $\tilde{m}$ without computing ${𝒪}^{(t)}(s)$ at all! Formally, we switch to a hybrid where we use the facts that $\mathrm{𝗉𝖺𝖽}={𝒪}^{(t)}(s)\oplus (m_b||\rho )$ and $\stackrel{~}{}\mathrm{𝗉𝖺𝖽}={𝒪}^{(t)}(s)\oplus (\tilde{m}||\tilde{\rho })$ to instead derive $\tilde{m}$ from $\stackrel{~}{}\mathrm{𝗉𝖺𝖽}\oplus \mathrm{𝗉𝖺𝖽}\oplus m_b$ since the ${𝒪}^{(t)}(s)$ terms cancel out. So the experiment doesn’t need to make any such queries to $𝒪$ in this case.

• $\mathrm{■}$

  Finally, for $D^{𝒪}$, we leverage the fact that pairs $(m,{𝒪}^{(t)}(m))$ are “hard-to-sample” by any $M^{𝒪}$ running in depth $\ll t$. Intuitively, this means that $M^{𝒪}$ can only compute such pairs for a bounded, polynomial set of messages $M^{𝒪}$. Since $M^{𝒪}$ must compute $\mathrm{𝖼𝗈𝗆}=𝒪(\tilde{s}||\tilde{m}||{𝒪}^{(t)}(\tilde{m})||\tilde{\rho })$ for any code $\tilde{c}$ it outputs, it must already “know” the underlying message $\tilde{m}$ (using the extractability of $𝒪$). It follows that $M^{𝒪}$ can only “pass” a polynomial-size set of messages to $D^{𝒪}$, who runs in polynomial time. This means there is only a polynomial set of values that $D^{𝒪}$ might have information on, so $D^{𝒪}$ is very unlikely to query the output of ${𝒪}^{(t)}(s)$ for a random $s$.

As such, the output of ${𝒪}^{(t)}(s)$ can be lazily sampled and independent of the rest of the experiment. We argued above that this suffices to guarantee that $D^{𝒪}$ has no advantage at predicting the challenge bit $b$, ruling out all possible mauling attacks.

The new random oracle-based techniques in the construction and analysis above are inspired by the notion of a “hard-to-sample” function from [78] and used by [17]. In their work, they construct and use hard-to-sample functions in a complexity-theoretic setting that only achieves inverse-polynomial security. Here, we implicitly use such functions in our construction based on random oracles. We think it is a fascinating direction for future work to build cryptographically secure hard-to-sample functions in the plain model, and is one possible avenue towards constructing rate-1 non-malleable codes in the plain model with negligible security. However, we note that our proof above additionally relies on the extractability property of the random oracle when computing $\mathrm{𝖼𝗈𝗆}$.

We note that Theorem 5.15 gives sufficient conditions for which the transformation of Theorem 5.11 is malleable for any concrete instantiation of the random oracle. As a result, one could assume that the transformation is secure for “natural” TLP candidates that don’t clearly support homomorphic properties. Indeed, existing candidates of fully homomorphic time-lock puzzles seem to rely on strong tools like fully homomorphic encryption or obfuscation [69] and are only proven secure with setup in the CRS model, so it is potentially a reasonable assumption that the compiler is secure for non-contrived CCA-hiding TLPs. This is similar to real-world applications of the Fiat-Shamir heuristic for arguments [39] or the Fujisaki-Okamoto transform for CCA-secure encryption [41], where we know there are concrete counterexamples [18, 44, 20, 57, 25, 45], yet it is believed to still be secure for many practical applications.

Concretely, we observe that the proof of Theorem 5.11 avoids this attack by the extractability property of a random oracle $𝒪$. Namely, the only way to compute $𝒪(s||r)$ is by “knowing” $s$. However, the attack from Theorem 5.15 shows this is not true if you can homomorphically evaluate $H(s||r)$ without knowing $s$ for any polynomial-size instantiation $H$ for $𝒪$.