Non-malleable Codes with Optimal Rate for Poly-Size Circuits

Marshall Ball, Ronen Shaltiel, Jad Silbak

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 [9] which achieves a rate smaller than 1n. Our codes are based on the same hardness assumption used by Ball, Dachman-Soled and Loss, namely, that there exists a problem in E=DTIME(2O(n)) that requires nondeterministic circuits of size 2Ω(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 EXP⊈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 [12, 26] 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 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 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 [55]. 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 [54]) 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
EditorsMarc Joye, Gregor Leander
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages22
ISBN (Print)9783031587368
StatePublished - 2024
Event43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2024 - Zurich, Switzerland
Duration: May 26 2024May 30 2024

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14654 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2024

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Non-malleable Codes with Optimal Rate for Poly-Size Circuits'. Together they form a unique fingerprint.

Cite this