Paper 2024/335

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

Naresh Goud Boddu, NTT Research
Vipul Goyal, Carnegie Mellon University and NTT Research
Rahul Jain, Centre for Quantum Technologies and Department of Computer Science, National University of Singapore and MajuLab
João Ribeiro, NOVA LINCS and NOVA School of Science and Technology
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. 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, 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^{\Omega(1)}$, and error $\varepsilon=2^{-{n^{\Omega(1)}}}$. In the easier setting of average-case non-malleability, we achieve efficient non-malleable coding with rate close to $1/11$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Non-malleable codesSecret sharingQuantum messages
Contact author(s)
naresh boddu @ ntt-research com
vipul @ vipulgoyal org
rahul @ comp nus edu sg
joao ribeiro @ fct unl pt
History
2024-02-27: approved
2024-02-26: received
See all versions
Short URL
https://ia.cr/2024/335
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/335,
      author = {Naresh Goud Boddu and Vipul Goyal and Rahul Jain and João Ribeiro},
      title = {Split-State Non-Malleable Codes and Secret Sharing Schemes for Quantum Messages},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/335},
      year = {2024},
      url = {https://eprint.iacr.org/2024/335}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.