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

• URL: http://arxiv.org/abs/2308.06466v2
• Date: Tue, 27 Feb 2024 08:05:45 GMT
• Title: Split-State Non-Malleable Codes and Secret Sharing Schemes for Quantum Messages
• Authors: Naresh Goud Boddu, Vipul Goyal, Rahul Jain, Jo\~ao Ribeiro
• Abstract summary: We introduce the notions of split-state non-malleable codes and secret sharing schemes for quantum messages secure against quantum adversaries with shared entanglement. 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.
• Score: 14.150289683819759
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 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^{\Omega(1)}$, and error $\epsilon=2^{-{n^{\Omega(1)}}}$. In the easier setting of \emph{average-case} non-malleability, we achieve efficient non-malleable coding with rate close to $1/11$.

Related papers

• Revocable Encryption, Programs, and More: The Case of Multi-Copy Security [48.53070281993869]
  We show the feasibility of revocable primitives, such as revocable encryption and revocable programs. This suggests that the stronger notion of multi-copy security is within reach in unclonable cryptography.
  arXiv  Detail & Related papers  (2024-10-17T02:37:40Z)
• SSIP: automated surgery with quantum LDPC codes [55.2480439325792]
  We present Safe Surgery by Identifying Pushouts (SSIP), an open-source lightweight Python package for automating surgery between qubit CSS codes. Under the hood, it performs linear algebra over $mathbbF$ governed by universal constructions in the category of chain complexes. We show that various logical measurements can be performed cheaply by surgery without sacrificing the high code distance.
  arXiv  Detail & Related papers  (2024-07-12T16:50:01Z)
• Unclonable Secret Sharing [18.564937506648622]
  Unclonable cryptography utilizes the principles of quantum mechanics to addresses cryptographic tasks that are impossible classically. We introduce a novel unclonable primitive in the context of secret sharing, called unclonable secret sharing (USS)
  arXiv  Detail & Related papers  (2024-06-16T16:50:15Z)
• On Split-State Quantum Tamper Detection and Non-Malleability [0.08702432681310403]
  We study quantum analogs of one of the most well-studied adversarial tampering models: the split-state tampering model. We present applications to designing secret sharing schemes, which inherit similar non-malleable and tamper-detection guarantees.
  arXiv  Detail & Related papers  (2023-11-27T17:09:02Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
  arXiv  Detail & Related papers  (2023-02-28T18:58:11Z)
• Powerful Primitives in the Bounded Quantum Storage Model [0.38073142980732994]
  The bounded quantum storage model aims to achieve security against computationally adversaries that are restricted only with respect to their quantum memories. We provide information-theoretic secure constructions in this model for the following powerful primitives.
  arXiv  Detail & Related papers  (2023-02-11T15:38:52Z)
• Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
  We construct the first fully homomorphic encryption scheme with certified deletion. Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors distribution in the form of a quantum state was deleted.
  arXiv  Detail & Related papers  (2022-03-03T10:07:32Z)
• Quantum secure non-malleable codes in the split-state model [10.018311966441027]
  Non-malleable-codes introduced by Dziembowski, Pietrzak and Wichs [DPW18] encode a classical message $S$. We construct explicit quantum secure non-malleable-codes in the split-state model.
  arXiv  Detail & Related papers  (2022-02-27T12:56:34Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.