CryptoDB
Non-malleable codes with optimal rate for poly-size circuits
| Authors: |
|
|---|---|
| Download: | |
| Conference: | EUROCRYPT 2024 |
| Abstract: | 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. |
BibTeX
@inproceedings{eurocrypt-2024-33947,
title={Non-malleable codes with optimal rate for poly-size circuits},
publisher={Springer-Verlag},
author={Marshall Ball and Ronen Shaltiel and Jad Silbak},
year=2024
}