Naresh Goud Boddu

“Non-Malleable Randomness Encoder” (NMRE) was introduced by Kanukurthi, Obbattu, and Sekar [KOS18] as a useful cryptographic primitive helpful in the construction of non- malleable codes. To the best of our knowledge, their construction is not known to be quantum secure. We provide a construction of a first rate-$1/2$, $2$-split, quantum secure NMRE and use this in a black-box manner, to construct for the first time the following: 1. rate $1/11$, $3$-split, quantum non-malleable code, 2. rate $1/3$, $3$-split, quantum secure non-malleable code, 3. rate $1/5$, $2$-split, quantum secure non-malleable code.

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. Roughly speaking, a non-malleable code for a family of tampering functions guarantees that no adversary can tamper (using functions from this family) the encoding of a given message into the encoding of a related distinct message. We focus on the split-state tampering model, one of the strongest and most well-studied adversarial tampering models. In this model, 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. Previous works on non-malleable codes in the split-state tampering model only considered the encoding of classical messages. Furthermore, until the recent work by Aggarwal, Boddu, and Jain (arXiv 2022), adversaries with quantum capabilities and shared entanglement had not been considered, and it is a priori not clear whether previous coding schemes remain secure in this model. In this work, we introduce the notion of split-state non-malleable codes for quantum messages secure against quantum adversaries with shared entanglement. We construct explicit codes in this model by relying on a recent quantum-secure 2-source non-malleable randomness encoder by Batra, Boddu, and Jain [BBJ23], arguments from Aggarwal, Boddu and Jain [ABJ22] and with use of unitary 2-designs. 1) More precisely, we construct the first efficiently encodable and decodable split-state non- malleable code for quantum messages (while preserving entanglement with external sys- tems) achieving security against quantum adversaries having shared entanglement with codeword length n, any message length at most $n^\Omega(1)$, and error $2^{-n^{\Omega(1)}}$. 2) For the case of uniform quantum message, we provide the first constant rate (rate 1/11) non-malleable code (while preserving entanglement with external systems) achieving code- word length n and error $2^{-n^{\Omega(1)}}$. .

We consider (Enc, Dec) schemes which are used to encode a classical/quantum message m and derive an n-qubit quantum codeword ψ_m. The quantum codeword ψ_m can adversarially tamper via a unitary U∈F_u from some known tampering unitary family F_u, resulting in Uψ_mU†. Firstly, we initiate the general study of quantum tamper detection codes, which must detect that tampering occurred with high probability. In case there was no tampering, we would like to output the message m with a probability of 1. We show that quantum tamper detection codes exist for both classical messages and quantum messages for any family F_u of unitary operators, such that |F_u|<2^{2^{αn}} for some known constant α∈(0,1) and all the unitary operators satisfy one additional condition : Far from Identity : For each U∈F_u, we require that its modulus of trace value isn't too much i.e. $ |Trace(U)| \leq \phi N$, where N=2^n. Quantum tamper-detection codes are quantum generalizations of classical tamper detection codes studied by Jafargholi et al. Additionally for classical message m, if we must either output message m or detect that tampering occurred and output ⊥ with high probability, we show that it is possible without the restriction of Far from Identity condition for any family of unitary operators F_u, such that |F_u|<2^{2^αn}. We also provide efficient (Enc, Dec) schemes when the family of tampering unitary operators are from Pauli group Pn, which can be thought of as a quantum version of the algebraic manipulation detection (AMD) codes of Cramer et al.

Multi-source-extractors are functions that extract uniform randomness from multiple (weak) sources of randomness. With the advent of quantum computers, it is natural to investigate the security of multi-source-extractors against adversaries with quantum side-information on the sources of randomness (potentially generated using quantum entanglement). Quantum multi- source-extractors were considered by Kasher and Kempe (for the quantum-independent- adversary and the quantum-bounded-storage-adversary), Chung, Li, and Wu (for the general- entangled-adversary), and Arnon-Friedman, Portmann, and Scholz (for the quantum-Markov- adversary). In this work, we propose two new models of adversaries, the quantum-measurement-adversary (qm-adv) and the quantum-communication-adversary (qc-adv). qm-adv generates side-information post-measurement outcomes and qc-adv generates side-information using a communication protocol. We show that: 1. qm-adv is the strongest adversary among all the known adversaries, in the sense that the side-information of all other adversaries can be generated by qm-adv. 2. The (generalized) inner-product function (in fact a general class of two-wise independent functions) continue to work as a good extractor against qm-adv (with matching parameters as that of Chor and Goldreich against classical-adversaries). 3. A non-malleable extractor proposed by Li (against classical-adversaries) continues to be secure against quantum side-information. A non-malleable extractor (nm-ext) for two sources (X, Y) is an extractor such that nm-ext(X, Y) is uniform and independent of nm-ext(X, Y')YY', where Y' is not equal to Y and Y' is generated by the adversary using Y and the side-information on X. 4. A modification (not needing any local uniform randomness) of the Dodis and Wich's protocol for privacy-amplification is secure against active quantum adversaries. This strengthens on a recent result due to Aggarwal, Chung, Lin, and Vidick which uses local uniform randomness. 5. As a byproduct, we reproduce the quantum communication complexity lower bound for the (generalized) inner-product function via different proof techniques.