The notion of non-malleable codes was introduced as a relaxation of standard error-correction and error-detection. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. In the information theoretic setting, although existence of such codes for various rich classes of tampering functions is known, explicit constructions exist only for highly structured family of tampering functions. Prior explicit constructions of non-malleable codes rely on the “compartmentalized” structure of the tampering function, i.e. the codeword is partitioned into a priori fixed blocks and each block can only be tampered independently. The prominent examples of this model are the family of bit-wise independent tampering functions and the split-state model. We consider an infinitely large natural class of non-compartmentalized tampering functions. In our model, the tampering function can permute the bits of the encoding and (optionally) perturb them. In the information theoretic setting, we provide an explicit and efficient, rate-1 non-malleable code for multi-bit messages. Lack of explicit constructions of non-malleable codes for non-compartmentalized tampering functions severely inhibits their utility in cryptographic protocols. As a motivation for our construction, we show an application of non-malleable codes to cryptographic protocols. In an idealized setting, we show how string commitments can be based on one-bit commitments, if non-malleable codes exist. Further, as an example of a non-trivial use of non-malleable codes in standard cryptographic protocols (not in an idealized model), we show that if explicit nonmalleable codes are obtained for a slightly larger class of tampering functions than we currently handle, one can obtain a very simple non-malleable commitment scheme, under somewhat strong assumptions.
The notion of non-malleable codes was introduced as a relaxation of standard error-correction and error-detection. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. In the information theoretic setting, although existence of such codes for various rich classes of tampering functions is known, explicit constructions exist only for highly structured family of tampering functions. Prior explicit constructions of non-malleable codes rely on the “compartmentalized” structure of the tampering function, i.e. the codeword is partitioned into a priori fixed blocks and each block can only be tampered independently. The prominent examples of this model are the family of bit-wise independent tampering functions and the split-state model. We consider an infinitely large natural class of non-compartmentalized tampering functions. In our model, the tampering function can permute the bits of the encoding and (optionally) perturb them. In the information theoretic setting, we provide an explicit and efficient, rate-1 non-malleable code for multi-bit messages. Lack of explicit constructions of non-malleable codes for non-compartmentalized tampering functions severely inhibits their utility in cryptographic protocols. As a motivation for our construction, we show an application of non-malleable codes to cryptographic protocols. In an idealized setting, we show how string commitments can be based on one-bit commitments, if non-malleable codes exist. Further, as an example of a non-trivial use of non-malleable codes in standard cryptographic protocols (not in an idealized model), we show that if explicit nonmalleable codes are obtained for a slightly larger class of tampering functions than we currently handle, one can obtain a very simple non-malleable commitment scheme, under somewhat strong assumptions.
A non-malleable code protects messages against various classes of tampering. Informally, a code is non-malleable if the message contained in a tampered codeword is either the original message, or a completely unrelated one. Although existence of such codes for various rich classes of tampering functions is known, explicit constructions exist only for “compartmentalized” tampering functions: i.e. the codeword is partitioned into a priori fixed blocks and each block can only be tampered independently. The prominent examples of this model are the family of bit-wise independent tampering functions and the split-state model. In this paper, for the first time we construct explicit non-malleable codes against a natural class of non-compartmentalized tampering functions. We allow the tampering functions to permute the bits of the codeword and (optionally) perturb them by flipping or setting them to 0 or 1. We construct an explicit, efficient non-malleable code for arbitrarily long messages in this model (unconditionally). We give an application of our construction to non-malleable commitments, as one of the first direct applications of non-malleable codes to computational cryptography. We show that nonmalleable string commitments can be “entirely based on” non-malleable bit commitments. More precisely, we show that simply encoding a string using our code, and then committing to each bit of the encoding using a CCA-secure bit commitment scheme results in a non-malleable string commitment scheme. This reduction is unconditional, does not require any extra properties from the bit-commitment such as “tag-based” non-malleability, and works even with physical implementations (which may not imply standard one-way functions). Further, even given a partially malleable bit commitment scheme which allows toggling the committed bit (instantiated, for illustration, using a variant of the Naor commitment scheme under a non-standard assumption on the PRG involved), this transformation gives a fully non-malleable string commitment scheme. This application relies on the non-malleable code being explicit.
Non-malleable codes introduced by Dziembowski, Pietrzak and Wichs [1] encode a classical messageSin a manner such that the tampered codeword either decodes to the original messageSor a message that is unrelated/independent ofS. Constructing non-malleable codes for various tampering function families has received significant attention in the recent years. We consider the well studied (2-part)split-statemodel, in which the messageSis encoded into two partsXandY, and the adversary is allowed to arbitrarily tamper with eachXandYindividually. Non-malleable codes in the split-state model have found applications in other important security notions likenon-malleable commitmentsandnon-malleable secret sharing. Thus, it is vital to understand if such non-malleable codes are secure against quantum adversaries. We consider the security of non-malleable codes in the split-state model when the adversary is allowed to make use of arbitrary entanglement to tamper the partsXandY. We construct explicit quantum secure non-malleable codes in the split-state model. Our construction of quantum secure non-malleable codes is based on the recent construction of quantum secure 2-source non-malleable extractorsby Boddu, Jain and Kapshikar [2]. • We extend the connection of Cheraghchi and Guruswami [3] between 2-source non-malleable extractors and non-malleable codes in the split-state model in the classical setting to the quantum setting, i.e. we show that explicit quantum secure 2-source non-malleable extractors in (k1,k2)-qpa-state framework of [2] give rise to explicit quantum secure non-malleable codes in the split-state model. • We construct the first quantum secure non-malleable code with efficient encoding and decoding procedures for message lengthm=nΩ(1), error ε = 2-nΩ(1)and codeword of size 2n. Prior to this work, it remained open to provide such quantum secure non-malleable code even for a single bit message in the split-state model. • We also study its natural extension when the tampering of the codeword is performedt-times. We construct quantum secure one-many non-malleable code with efficient encoding and decoding procedures fort=nΩ(1), message lengthm=nΩ(1), error ε = 2-nΩ(1)and codeword of size 2n. • As an application, we also construct the first quantum secure 2-out-of-2 non-malleable secret sharing scheme for message/secret lengthm=nΩ(1), error ε = 2-nΩ(1)and share of sizen.
Non-malleable codes are fundamental objects at the intersection of cryptography and coding theory. These codes provide security guarantees even in settings where error correction and detection are impossible, and have found applications to several other cryptographic tasks. One of the strongest and most well-studied adversarial tampering models is 2-split-state tampering. Here, a codeword is split into two parts which are stored in physically distant servers, and the adversary can then independently tamper with each part using arbitrary functions. This model can be naturally extended to the secret sharing setting with several parties by having the adversary independently tamper with each share. Previous works on non-malleable coding and secret sharing in the split-state tampering model only considered the encoding of classical messages. Furthermore, until recent work by Aggarwal, Boddu, and Jain (IEEE Trans. Inf. Theory 2024 & arXiv 2022), adversaries with quantum capabilities and shared entanglement had not been considered, and it is a priori not clear whether previous schemes remain secure in this model. In this work, we introduce the notions of split-state non-malleable codes and secret sharing schemes for quantum messages secure against quantum adversaries with shared entanglement. Then, we present explicit constructions of such schemes that achieve low-error non-malleability. More precisely, for some constantc>0, we construct efficiently encodable and decodable split-state non-malleable codes and secret sharing schemes for quantum messages preserving entanglement with external systems and achieving security against quantum adversaries having shared entanglement with codeword length n, any message length at mostnc, and errorε=2−nc. In the easier setting of average-case non-malleability, we achieve efficient non-malleable coding with rate close to1/11.
We construct efficient information-theoretic non-malleable codes for classical messages that are secure against two noncommunicating local quantum tampering operations with arbitrary pre-shared entanglement. For every sufficiently small fixed ξ>0 and all sufficiently large first-share lengths n, the codes have rate at least 1/5−ξ, perfect correctness, and error 2−nΩ(1). Security holds for every message, with a single message-independent simulator for each attack. This resolves the constant-rate question for worst-case classical messages in the entangled two-split-state model.
Our construction builds on the permutation-based two-split construction of Batra, Boddu, and Jain, which achieves rate approaching 1/5 for uniformly random messages. We retain their architecture but replace the uniform message input to the permutation with a prescribed message concatenated with fresh uniform padding. Our main contribution is a worst-case security reduction for this modification.
Non-malleable codes are fundamental objects at the intersection of cryptography and coding theory. These codes provide security guarantees even in settings where error correction and detection are impossible, and have found applications to several other cryptographic tasks. One of the strongest and most well-studied adversarial tampering models is 2-split-state tampering. Here, a codeword is split into two parts and the adversary can then independently tamper with each part using arbitrary functions. This model can be naturally extended to the secret sharing setting with several parties by having the adversary independently tamper with each share. Previous works on non-malleable coding and secret sharing in the split-state tampering model only considered the encoding of \emph{classical} messages. Furthermore, until recent work by Aggarwal, Boddu, and Jain (IEEE Trans.\ Inf.\ Theory 2024), adversaries with quantum capabilities and \emph{shared entanglement} had not been considered, and it is a priori not clear whether previous schemes remain secure in this model. In this work, we introduce the notions of split-state non-malleable codes and secret sharing schemes for quantum messages secure against quantum adversaries with shared entanglement. Then, we present explicit constructions of such schemes that achieve low-error non-malleability. More precisely, we construct efficiently encodable and decodable split-state non-malleable codes and secret sharing schemes for quantum messages preserving entanglement with external systems and achieving security against quantum adversaries having shared entanglement with codeword length n, any message length at most nΩ(1), and error ε=2−nΩ(1). In the easier setting of \emph{average-case} non-malleability, we achieve efficient non-malleable coding with rate close to 1/11.
We propose the first black-box construction of non-malleable commitments according to the standard notion of non-malleability with respect to commitment. Our construction additionally only requires a constant number of rounds and is based only on (black-box use of) one-way functions. Prior to our work, no black-box construction of non-malleable commitments was known (except for relaxed notions of security) in any (polynomial) number of rounds based on any cryptographic assumption. This closes the wide gap existent between black-box and non-black-box constructions for the problem of non-malleable commitments. Our construction relies on (and can be seen as a generalization of) the recent non-malleable commitment scheme of Goyal (STOC 2011). We also show how to get black-box constructions for a host of other cryptographic primitives. We extend our construction to get constant-round concurrent non-malleable commitments, constant-round multi-party coin tossing, and non-malleable statistically hiding commitments (satisfying the notion of non-malleability with respect to opening). All of the mentioned results make only a black-box use of one-way functions. Our primary technical contribution is a novel way of implementing the proof of consistency typically required in the constructions of non-malleable commitments (and other related primitives). We do this by relying on ideas from the ``zero-knowledge from secure multi-party computation" paradigm of Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC 2007). We extend in a novel way this ``computation in the head" paradigm (which can be though of as bringing powerful error-correcting codes into purely computational setting). To construct a non-malleable commitment scheme, we apply our computation in the head techniques to the recent (constant-round) construction of Goyal. Along the way, we also present a simplification of the construction of Goyal where a part of the protocol is implemented in an information theoretic manner. Such a simplification is crucial for getting a black-box construction. This is done by making use of pair wise-independent hash functions and strong randomness extractors. We show that our techniques have multiple applications, as elaborated in the paper. Hence, we believe our techniques might be useful in other settings in future.