Contributed Talks 4d: Theory

Abstract: We consider the security of Quantum Key Distribution (QKD) protocols consisting of a finite number of rounds. We provide a security proof that is both and provides tight finite-size correction terms. In particular, when expanded in the block length $n$, the rate of randomness generation has the optimal asymptotic rate and optimal leading-order finite-size correction term. The proof is also general, applying to generic randomness generation and QKD protocols that have fully characterized devices and consist of a finite number of rounds.

Abstract: “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.

Abstract: 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)}}$. .