Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

National Conference on Communications

Non-Malleable Coding under Cost Constraints

Eshita Chandwani, Amitalok J. Budkuley

Published Mar 6, 2025• 0 citations
Publisher

Abstract

We consider a communication problem where sender, say Alice, sends a message to receiver, say Bob, in the presence of an active adversary, James, who tampers Alice's transmission using a function from a known class of tampering functions. The goal is two-fold: First, the decoder should always decode Alice's message correctly in the absence of tampering. Second, when tampering occurs, the decoder should attempt to detect errors and, when that fails, limit the adversary's control over the decoding error outcome. In particular, the decoded message should be statistically independent of Alice's original message, making the coding scheme non-malleable (with respect to tampering). This setup is motivated by scenarios like tampered-proof sealed-bid auctions, where an adversary might attempt to alter the decoded bid to manipulate the outcome. In this work, we focus on binary non-malleable coding with input constraints, which limit the set of possible transmit vectors. We fully characterize the maximum throughput, or non-malleable capacity, for any given tampering family of bounded size (up to doubly-exponential in block length), extending the classic result for unconstrained inputs by Cheragchi and Guruswami (Trans. IT, 2016)

DOI
10.1109/ncc63735.2025.10983288

Related papers

Explicit Non-Malleable Codes Resistant to Permutations.

Shashank Agrawal, Divya Gupta, Hemanta K. Maji +2 more

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.

Electronic colloquium on computational complexity•Jan 1, 2014•15 citations

Split-State Non-Malleable Codes and Secret Sharing Schemes for Quantum Messages

Naresh Goud Boddu, Vipul Goyal, Rahul Jain +1 more

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 constant$c\gt 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 most$n^{c}$, and error$\varepsilon =2^{-{n^{c}}}$. In the easier setting of average-case non-malleability, we achieve efficient non-malleable coding with rate close to$1/11$.

IEEE Transactions on Information Theory•Jan 15, 2025•2 citations

Split-State Non-Malleable Codes and Secret Sharing Schemes for Quantum Messages

Naresh Goud Boddu, Vipul Goyal, Rahul Jain +1 more

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$.

arXiv:2308.06466•Aug 12, 2023•1 citation

Quantum Secure Non-Malleable Codes in the Split-State Model

Divesh Aggarwal, Naresh Goud Boddu, Rahul Jain

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.

IEEE Transactions on Information Theory•Oct 31, 2023•7 citations

Keyless secrecy against bounded adversaries

Anne Broadbent, Upendra Kapshikar, Denis Rochette

We introduce a keyless coding/cryptographic primitive that asks for two guarantees at once: the receiver is never fooled into accepting a message other than the one sent, and the adversary learns nothing about the message unless the receiver aborts. Neither the sender nor the receiver holds a secret key, and no computational hardness is assumed. The only restriction is on the adversary's online computation: the receiver aborts if nothing arrives by a fixed deadline, so the adversary must forward something before it, and her map in that window is computed by a circuit of size (or depth) at most $p$; before and after, she is unbounded. For every polynomial $p$ we construct such an efficient quantum scheme, encoding $k$-bit messages into $n = O(k)$ qubits with circuits of size $\mathrm{poly}(n,p)$. No classical scheme achieves this type of everlasting security, at any choice of parameters. Our techniques also resolve open questions about universal tamper detection against families restricted in cardinality rather than in circuit size. We settle a question of Broadbent, Kapshikar and Rochette on relaxed tamper detection. As a corollary, we obtain the first efficient non-malleable code secure against global quantum tampering, with no split-state restriction, whereas the current constructions in the literature require the codeword to be split into non-communicating shares.

quant-pharXiv:2609.12251•Sep 14, 2026•0 citations

Explicit Non-malleable Codes Resistant to Permutations and Perturbations.

Shashank Agrawal, Divya Gupta, Hemanta K. Maji +2 more

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.

•Jan 1, 2014•20 citations
We consider a communication problem where sender, say Alice, sends a message to receiver, say Bob, in the presence of an active adversary, James, who tampers Alice's transmission using a function from a known class of tampering functions. The goal is two-fold: First, the decoder should always decode Alice's message correctly in the absence of tampering. Second, when tampering occurs, the decoder should attempt to detect errors and, when that fails, limit the adversary's control over the decoding error outcome. In particular, the decoded message should be statistically independent of Alice's original message, making the coding scheme non-malleable (with respect to tampering). This setup is motivated by scenarios like tampered-proof sealed-bid auctions, where an adversary might attempt to alter the decoded bid to manipulate the outcome. In this work, we focus on binary non-malleable coding with input constraints, which limit the set of possible transmit vectors. We fully characterize the maximum throughput, or non-malleable capacity, for any given tampering family of bounded size (up to doubly-exponential in block length), extending the classic result for unconstrained inputs by Cheragchi and Guruswami (Trans. IT, 2016)
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.
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>0c\gt 0c>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 mostncn^{c}nc, and errorε=2−nc\varepsilon =2^{-{n^{c}}}ε=2−nc. In the easier setting of average-case non-malleability, we achieve efficient non-malleable coding with rate close to1/111/111/11.
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 222-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 nnn, any message length at most nΩ(1)n^{Ω(1)}nΩ(1), and error ε=2−nΩ(1)ε=2^{-{n^{Ω(1)}}}ε=2−nΩ(1). In the easier setting of \emph{average-case} non-malleability, we achieve efficient non-malleable coding with rate close to 1/111/111/11.
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.
We introduce a keyless coding/cryptographic primitive that asks for two guarantees at once: the receiver is never fooled into accepting a message other than the one sent, and the adversary learns nothing about the message unless the receiver aborts. Neither the sender nor the receiver holds a secret key, and no computational hardness is assumed. The only restriction is on the adversary's online computation: the receiver aborts if nothing arrives by a fixed deadline, so the adversary must forward something before it, and her map in that window is computed by a circuit of size (or depth) at most ppp; before and after, she is unbounded. For every polynomial ppp we construct such an efficient quantum scheme, encoding kkk-bit messages into n=O(k)n = O(k)n=O(k) qubits with circuits of size poly(n,p)\mathrm{poly}(n,p)poly(n,p). No classical scheme achieves this type of everlasting security, at any choice of parameters. Our techniques also resolve open questions about universal tamper detection against families restricted in cardinality rather than in circuit size. We settle a question of Broadbent, Kapshikar and Rochette on relaxed tamper detection. As a corollary, we obtain the first efficient non-malleable code secure against global quantum tampering, with no split-state restriction, whereas the current constructions in the literature require the codeword to be split into non-communicating shares.
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.