Security of a storage device against a tampering adversary has been a well-studied topic in classical cryptography. Such models give black-box access to an adversary, and the aim is to protect the stored message or abort the protocol if there is any tampering.In this work, we extend the scope of the theory of tamper detection codes against an adversary with quantum capabilities. We consider encoding and decoding schemes that are used to encode a k -qubit quantum message |m⟩ to obtain an n -qubit quantum codeword |ψm⟩ . A quantum codeword |ψm⟩ can be adversarially tampered via a unitary U from some known tampering unitary family UAdv (acting on C2n ).Firstly, we initiate the general study of quantum tamper detection codes , which detect if there is any tampering caused by the action of a unitary operator. In case there was no tampering, we would like to output the original message. We show that quantum tamper detection codes exist for any family of unitary operators UAdv , such that |UAdv|<22αn for some constant α∈(0,1/6) ; provided that unitary operators are not too close to the identity operator. Quantum tamper detection codes that we construct can be considered to be quantum variants of classical tamper detection codes studied by Jafargholi and Wichs ['15], which are also known to exist under similar restrictions.Additionally, we show that when the message set M is classical, such a construction can be realized as a non-malleable code against any UAdv of size up to 22αn .
Security of a storage device against a tampering adversary has been a well-studied topic in classical cryptography. Such models give black-box access to an adversary, and the aim is to protect the stored message or abort the protocol if there is any tampering.In this work, we extend the scope of the theory of tamper detection codes against an adversary with quantum capabilities. We consider encoding and decoding schemes that are used to encode a k -qubit quantum message |m⟩ to obtain an n -qubit quantum codeword |ψm⟩ . A quantum codeword |ψm⟩ can be adversarially tampered via a unitary U from some known tampering unitary family UAdv (acting on C2n ).Firstly, we initiate the general study of quantum tamper detection codes , which detect if there is any tampering caused by the action of a unitary operator. In case there was no tampering, we would like to output the original message. We show that quantum tamper detection codes exist for any family of unitary operators UAdv , such that |UAdv|<22αn for some constant α∈(0,1/6) ; provided that unitary operators are not too close to the identity operator. Quantum tamper detection codes that we construct can be considered to be quantum variants of classical tamper detection codes studied by Jafargholi and Wichs ['15], which are also known to exist under similar restrictions.Additionally, we show that when the message set M is classical, such a construction can be realized as a non-malleable code against any UAdv of size up to 22αn .
Tamper-resilient cryptography studies how to protect data against adversaries who can physically manipulate codewords before they are decoded. The notion of tamper detection codes formalizes this goal, requiring that any unauthorized modification be detected with high probability. Classical results, starting from Jafargholi and Wichs (TCC 2015), established the existence of such codes against very large families of tampering functions, subject to structural restrictions ruling out identity and constant maps. Recent works of Boddu and Kapshikar (Quantum, 7) and Bergamaschi (Eurocrypt 2024) have extended these ideas to quantum adversaries, but only consider unitary tampering families. In this work, we give the first general treatment of tamper detection against arbitrary quantum maps. We show that Haar-random encoding schemes achieve exponentially small soundness error against any adversarial family whose size, Kraus rank, and entanglement fidelity obey natural constraints, which are direct quantum analogues of restrictions in the classical setting. Our results unify and extend previous works. Beyond this, we demonstrate a fundamental separation between classical and quantum tamper detection. Classically, relaxed tamper detection which allows either rejection or recovery of the original message cannot protect even against the family of constant functions. This family is of size 2n. In contrast, we show that quantum encodings can handle this obstruction, and we conjecture and provide evidence that they may in fact provide relaxed tamper detection and non-malleable security against any family of quantum maps of size up to 22αn for any constant α<21, leading to a conjecture on the existence of universal quantum tamper detection. Our results provide the first evidence that quantum tamper detection is strictly more powerful than its classical counterpart.
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.
Tamper-detection codes (TDCs) are fundamental objects at the intersection of cryptography and coding theory. A TDC encodes messages in such a manner that tampering the codeword causes the decoder to either output the original message, or reject it. In this work, we study quantum analogs of one of the most well-studied adversarial tampering models: the so-called t-split-state tampering model, where the codeword is divided into t shares, and each share is tampered with "locally". It is impossible to achieve tamper detection in the split-state model using classical codewords. Nevertheless, we demonstrate that the situation changes significantly if the message can be encoded into a multipartite quantum state, entangled across the t shares. Concretely, we define a family of quantum TDCs defined on any t≥3 shares, which can detect arbitrary split-state tampering so long as the adversaries are unentangled, or even limited to a finite amount of pre-shared entanglement. Previously, this was only known in the limit of asymptotically large t. As our flagship application, we show how to augment threshold secret sharing schemes with similar tamper-detecting guarantees. We complement our results by establishing connections between quantum TDCs and quantum encryption schemes.
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 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 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 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.