International Association
for Cryptologic Research

We give an explicit construction of non-malleable codes with rate $1-o(1)$ for the tampering class of poly-size circuits. This rate is optimal, and improves upon the previous explicit construction of Ball, Dachman-Soled and Loss \cite{BDL22} which achieves a rate smaller than $\frac{1}{n}$. Our codes are based on the same hardness assumption used by Ball, Dachman-Soled and Loss, namely, that there exists a problem in $\text{E}=\text{DTIME}(2^{O(n)})$ that requires nondeterministic circuits of size $2^{\Omega(n)}$. This is a standard complexity theoretic assumption that was used in many papers in complexity theory and cryptography, and can be viewed as a scaled, nonuniform version of the widely believed assumption that $\text{EXP} \not \subseteq \text{NP}$. Our result is incomparable to that of Ball, Dachman-Soled and Loss, as we only achieve computational (rather than statistical) security. Non-malleable codes with Computational security (with lower error than what we get) were obtained by \cite{BDKLM19,DKP21} under strong cryptographic assumptions. We show that our approach can potentially yield statistical security if certain explicit constructions of pseudorandom objects can be improved. By composing our new non-malleable codes with standard (information theoretic) error-correcting codes (that recover from a $p$ fraction of errors) we achieve the \emph{best of both worlds}. Namely, we achieve explicit codes that recover from a $p$-fraction of errors and have the same rate as the best known explicit information theoretic codes, while \emph{also} being non-malleable for poly-size circuits. Moreover, if we restrict our attention to errors that are introduced by poly-size circuits, we can achieve best of both worlds codes with rate $1-H(p)$. This is superior to the rate achieved by standard (information theoretic) error-correcting codes, and this result is obtained by composing our new non-malleable codes with the recent codes of Shaltiel and Silbak \cite{SS23}. Our technique combines ideas from non-malleable codes and pseudorandomness. We show how to take a low rate ``small set non-malleable code (this is a variant of non-malleable codes with a different notion of security that was introduced by Shaltiel and Silbak \cite{SS22}) and compile it into a (standard) high-rate non-malleable code. Using small set non-malleable codes (as well as seed-extending PRGs) bypasses difficulties that arise when analysing standard non-malleable codes, and allows us to use a simple construction.

Consider a ppt two-party protocol $$\varPi = (\mathsf {A} ,\mathsf {B} )$$ in which the parties get no private inputs and obtain outputs $$O^{\mathsf {A} },O^{\mathsf {B} }\in \left\{ 0,1\right\} $$, and let $$V^\mathsf {A} $$ and $$V^\mathsf {B} $$ denote the parties’ individual views. Protocol $$\varPi $$ has $$\alpha $$-agreement if $$\Pr [O^{\mathsf {A} }=O^{\mathsf {B} }] = \tfrac{1}{2}+\alpha $$. The leakage of $$\varPi $$ is the amount of information a party obtains about the event $$\left\{ O^{\mathsf {A} }=O^{\mathsf {B} }\right\} $$; that is, the leakage$$\epsilon $$ is the maximum, over $$\mathsf {P} \in \left\{ \mathsf {A} ,\mathsf {B} \right\} $$, of the distance between $$V^\mathsf {P} |_{O^{\mathsf {A} }= O^{\mathsf {B} }}$$ and $$V^\mathsf {P} |_{O^{\mathsf {A} }\ne O^{\mathsf {B} }}$$. Typically, this distance is measured in statistical distance, or, in the computational setting, in computational indistinguishability. For this choice, Wullschleger [TCC ’09] showed that if $$\epsilon \ll \alpha $$ then the protocol can be transformed into an OT protocol.We consider measuring the protocol leakage by the log-ratio distance (which was popularized by its use in the differential privacy framework). The log-ratio distance between X, Y over domain $$\varOmega $$ is the minimal $$\epsilon \ge 0$$ for which, for every $$v \in \varOmega $$, $$\log \frac{\Pr [X=v]}{\Pr [Y=v]} \in [-\epsilon ,\epsilon ]$$. In the computational setting, we use computational indistinguishability from having log-ratio distance $$\epsilon $$. We show that a protocol with (noticeable) accuracy $$\alpha \in \varOmega (\epsilon ^2)$$ can be transformed into an OT protocol (note that this allows $$\epsilon \gg \alpha $$). We complete the picture, in this respect, showing that a protocol with $$\alpha \in o(\epsilon ^2)$$ does not necessarily imply OT. Our results hold for both the information theoretic and the computational settings, and can be viewed as a “fine grained” approach to “weak OT amplification”.We then use the above result to fully characterize the complexity of differentially private two-party computation for the XOR function, answering the open question put by Goyal, Khurana, Mironov, Pandey, and Sahai, [ICALP ’16] and Haitner, Nissim, Omri, Shaltiel, and Silbak [22] [FOCS ’18]. Specifically, we show that for any (noticeable) $$\alpha \in \varOmega (\epsilon ^2)$$, a two-party protocol that computes the XOR function with $$\alpha $$-accuracy and $$\epsilon $$-differential privacy can be transformed into an OT protocol. This improves upon Goyal et al. that only handle $$\alpha \in \varOmega (\epsilon )$$, and upon Haitner et al. who showed that such a protocol implies (infinitely-often) key agreement (and not OT). Our characterization is tight since OT does not follow from protocols in which $$\alpha \in o( \epsilon ^2)$$, and extends to functions (over many bits) that “contain” an “embedded copy” of the XOR function.