Relativistic zero-knowledge protocol for NP over the internet unconditionally secure against quantum adversaries

• URL: http://arxiv.org/abs/2112.01386v1
• Date: Thu, 2 Dec 2021 16:18:09 GMT
• Title: Relativistic zero-knowledge protocol for NP over the internet unconditionally secure against quantum adversaries
• Authors: Andr\'e Chailloux and Yann Barsamian
• Abstract summary: We present a new relativistic protocol for NP which is secure against quantum adversaries. We use Stern's zero-knowledge scheme for the Syndrome Decoding problem, which was used before in post-quantum cryptography.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Relativistic cryptography is a proposal for achieving unconditional security that exploits the fact that no information carrier can travel faster than the speed of light. It is based on space-time constraints but doesn't require quantum hardware. Nevertheless, it was unclear whether this proposal is realistic or not. Recently, Alikhani et al. [ABC+21] performed an implementation of a relativistic zero-knowledge for NP. Their implemented scheme shows the feasibility of relativistic cryptography but it is only secure against classical adversaries. In this work, we present a new relativistic protocol for NP which is secure against quantum adversaries and which is efficient enough so that it can be implemented on everyday laptops and internet connections. We use Stern's zero-knowledge scheme for the Syndrome Decoding problem, which was used before in post-quantum cryptography. The main technical contribution is a generalization of the consecutive measurement framework of [CL17] to prove the security of our scheme against quantum adversaries, and we perform an implementation that demonstrates the feasibility and efficiency of our proposed scheme.

Related papers

• MPC in the Quantum Head (or: Superposition-Secure (Quantum) Zero-Knowledge) [19.71357898702801]
  We present a generalization of the MPC-in-the-head paradigm to the quantum setting.<n>We propose a new approach to build zero-knowledge protocols where security holds even against a verifier that can obtain a superposition of transcripts.
  arXiv  Detail & Related papers  (2025-06-28T17:43:32Z)
• Pseudorandom quantum authentication [0.8204952610951527]
  We introduce the pseudorandom quantum authentication scheme (PQAS) It is an efficient method for quantum states that relies solely on the existence of pseudorandom unitaries (PRUs)
  arXiv  Detail & Related papers  (2025-01-01T20:46:37Z)
• Secret extraction attacks against obfuscated IQP circuits [0.92463347238923]
  In 2008, Shepherd and Bremner proposed a protocol in which a verifier constructs a unitary from the comparatively easy-to-implement family of IQP circuits. The challenge problem is designed to contain an obfuscated secret, which can be turned into a statistical test. Kahanamoku-Meyer found an efficient classical secret extraction attack. Bremner, Cheng, and Ji very recently followed up by constructing a wide-ranging generalization of the original protocol.
  arXiv  Detail & Related papers  (2023-12-15T19:08:35Z)
• Encryption with Quantum Public Keys [1.7725414095035827]
  We study the question of building quantum public-key encryption schemes from one-way functions and even weaker assumptions. We propose three schemes for quantum public-key encryption from one-way functions, pseudorandom function-like states with proof of deletion and pseudorandom function-like states, respectively.
  arXiv  Detail & Related papers  (2023-03-09T16:17:19Z)
• Oblivious Transfer from Zero-Knowledge Proofs, or How to Achieve Round-Optimal Quantum Oblivious Transfer and Zero-Knowledge Proofs on Quantum States [0.0]
  We turn any classical Zero-Knowledge (ZK) protocol into a composable (quantum) oblivious transfer (OT) protocol. We provide the first round-optimal (2-message) quantum OT protocol secure in the random oracle model. At the heart of our construction lies a new method that allows us to prove properties on a received quantum state without revealing additional information.
  arXiv  Detail & Related papers  (2023-03-02T18:38:15Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• 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)
• On Zero-Knowledge Proofs over the Quantum Internet [0.0]
  This paper presents a new method for quantum identity authentication (QIA) protocols. The logic of classical zero-knowledge proofs (ZKPs) due to Schnorr is applied in quantum circuits and algorithms.
  arXiv  Detail & Related papers  (2022-12-06T14:57:00Z)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  We propose a variational quantum attack algorithm (VQAA) for classical AES-like symmetric cryptography. In the VQAA, the known ciphertext is encoded as the ground state of a Hamiltonian that is constructed through a regular graph.
  arXiv  Detail & Related papers  (2022-05-07T03:15:15Z)
• 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)
• Direct Quantum Communications in the Presence of Realistic Noisy Entanglement [69.25543534545538]
  We propose a novel quantum communication scheme relying on realistic noisy pre-shared entanglement. Our performance analysis shows that the proposed scheme offers competitive QBER, yield, and goodput.
  arXiv  Detail & Related papers  (2020-12-22T13:06:12Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• 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)
• Asymptotic security analysis of teleportation based quantum cryptography [0.0]
  We prove that the teleportation based quantum cryptography protocol presented in [Opt. Commun 283, 184] is secure against all types of individual and collective attacks. We then investigate modifications to that protocol leading to greater secret-key rates and to security against coherent attacks.
  arXiv  Detail & Related papers  (2020-02-10T17:54:15Z)

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.