This paper presents a novel hybrid zero-knowledge proof protocol resistant to quantum computer attacks. The protocol combines classical cryptography based on the Learning with Errors problem complexity with quantum state properties. The main objective of the protocol is to enable a prover to convince a verifier of knowledge of a secret parameter alpha without revealing its value, even against adversaries with quantum computational capabilities. A key feature of the protocol is the explicit dependence of quantum operations on the secret parameter through a cryptographic hash function modeled as a quantum random oracle. This ensures an inseparable connection between the quantum and classical phases of protocol execution. The protocol includes a mechanism for regular secret updates between interaction rounds, providing protection against adaptive attacks. Special attention is given to accounting for real physical errors of quantum devices – a difference threshold is introduced that allows for a certain level of noise and decoherence. The paper presents a formal security analysis of the protocol. The properties of honest-verifier zero-knowledge and proof of knowledge against quantum polynomial-time adversaries are proven. Security is justified through constructing a sequence of hybrid games showing that the probability of a successful attack is negligible relative to the security parameter plus the probability of physical implementation error. The protocol is of practical interest for building cryptographic systems in the context of quantum computing development.
This paper presents a novel hybrid zero-knowledge proof protocol resistant to quantum computer attacks. The protocol combines classical cryptography based on the Learning with Errors problem complexity with quantum state properties. The main objective of the protocol is to enable a prover to convince a verifier of knowledge of a secret parameter alpha without revealing its value, even against adversaries with quantum computational capabilities. A key feature of the protocol is the explicit dependence of quantum operations on the secret parameter through a cryptographic hash function modeled as a quantum random oracle. This ensures an inseparable connection between the quantum and classical phases of protocol execution. The protocol includes a mechanism for regular secret updates between interaction rounds, providing protection against adaptive attacks. Special attention is given to accounting for real physical errors of quantum devices – a difference threshold is introduced that allows for a certain level of noise and decoherence. The paper presents a formal security analysis of the protocol. The properties of honest-verifier zero-knowledge and proof of knowledge against quantum polynomial-time adversaries are proven. Security is justified through constructing a sequence of hybrid games showing that the probability of a successful attack is negligible relative to the security parameter plus the probability of physical implementation error. The protocol is of practical interest for building cryptographic systems in the context of quantum computing development.
Zero-knowledge proof (ZKP) is a fundamental cryptographic primitive that allows a prover to convince a verifier of the validity of a statement without leaking any further information. As an efficient variant of ZKP, noninteractive zero-knowledge proof (NIZKP) adopting the Fiat-Shamir heuristic is essential to a wide spectrum of applications, such as federated learning, blockchain, and social networks. However, the heuristic is typically built upon the random oracle model that makes ideal assumptions about hash functions, which does not hold in reality and thus undermines the security of the protocol. Here, we present a quantum solution to the problem. Instead of resorting to a random oracle model, we implement a quantum randomness service. This service generates random numbers certified by the loophole-free Bell test and delivers them with postquantum cryptography (PQC) authentication. By employing this service, we conceive and implement NIZKP of the three-coloring problem. By bridging together three prominent research themes, quantum nonlocality, PQC, and ZKP, we anticipate this work to inspire more innovative applications that combine quantum information science and the cryptography field.
This article investigates methods for ensuring the quantum-adaptive security of hybrid cryptographic protocols in next-generation networks. 5G/6G and IoT networks necessitate the integration of classical and post-quantum algorithms. However, standard protocols combining ECDH with CRYSTALS-Kyber or CRYSTALS-Dilithium require formal security assessments. Current approaches primarily consider non-adaptive quantum adversaries, which limits their practical applicability in multi-session and dynamic environments. The paper proposes a model of a quantum-adaptive adversary. This model integrates the adversary's classical and quantum resources, an adaptive attack strategy, and a quantum-accessible oracle. It allows for the formalization of superposition queries and multi-step interactions with the protocol. A mathematical model of a hybrid handshake protocol is introduced, where the session key is formed by combining classical and post-quantum components via a Key Derivation Function. An upper bound for the adversary's advantage is derived, accounting for both the classical and post-quantum components of the protocol. To enhance resilience, three primary methods are proposed. The first is downgrade-resistant fixation of protocol parameters with cryptographic confirmation. The second is dynamic management of key parameters and cryptographic primitives based on an integrated risk function, which accounts for the adversary's quantum resources, network load, and attack activity. The third is compositional protocol verification considering multi-session and multi-level handshake phases, enabling the formalization of composability and the assessment of multi-level resilience. An integral metric of quantum-adaptive resilience is proposed, accounting for security, complexity, and adaptability. The results provide a scientific foundation for “harvest-now, decrypt-later” risk analysis.
A Zero-Knowledge Proof basically is a protocol between two parties, the Prover and the Verifier, that allows the Prover to convince the Verifier about the truthness of a non trivial statement without revealing any additional information. Zero Knowledge Proofs have found a lot of practical applications covering most of the protocols concerning about data privacy and protocol verification. Examples of that are anonymous cash or electronic voting. The possibility to have real quantum computers with a reasonable size in a near future is forcing the cryptographic community to devise new methods to provide security that resist quantum attacks. Most of the zero-knowledge protocols used nowadays are based on computational problems like the discrete logarithm problem that can no longer be considered hard, since there are known efficient ways to solve them with quantum algorithms. Cryptographic research about the quantum security of zero knowledge proofs started nearly 20 years ago in a very theoretical approach, but not many papers on that topic appeared since then. The goal of this thesis is writing a survey including the main concepts about quantum secure zero-knowledge protocols, the state-of-the-art both from the theoretical and practical approaches, and an exploration of their potential application areas. The survey will be a good starting document for further students willing to do research in this topic.
This paper explores the quantumization of zero-knowledge proofs (ZKPs) and verifiable computation circuits (VCCs), presenting a novel approach to achieving secure and verifiable execution of quantum computation programs. The core idea involves leveraging quantum circuit hashing techniques to construct ZKP protocols that demonstrate the correctness of a VCC without revealing its underlying structure. This approach addresses a critical need within the burgeoning field of quantum computing – the provision of robust and trustworthy execution validation mechanisms. We outline the theoretical framework, detailing the key components of the system including the circuit hashing algorithm, the ZKP protocol design, and the associated mathematical formalization. The work contributes to the development of a new paradigm for quantum program verification, offering a potential pathway towards building more reliable and secure quantum computing systems. The presented methodology aims to bridge the gap between the theoretical promise of quantum computation and the practical challenges of ensuring its trustworthiness. ---
In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation. In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called ε-zero-knowledge. Concretely, we construct the following protocols: - We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box ε-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of ε-zero-knowledge property against quantum adversaries requires novel ideas. - We construct a constant round interactive argument for NP that satisfies computational soundness and black-box ε-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.
In a proof of knowledge (PoK), a verifier becomes convinced that a prover possesses privileged information. In combination with zero-knowledge proof systems, PoKs play an important role in security protocols such as in digital signatures and authentication schemes, as they enable a prover to demonstrate possession of certain information (such as a private key or a credential), without revealing it. A PoK is formally defined via the existence of an extractor, which is capable of reconstructing the key information that makes a verifier accept, given oracle access to any accepting prover. We extend this concept to the setting of a single classical verifier and multiple quantum provers and present the first statistical zero-knowledge (ZK) PoK proof system for problems in QMA. To achieve this, we establish the PoK property for the ZK protocol of Broadbent, Mehta, and Zhao (TQC 2024), which applies to the local Hamiltonian problem. More specifically, we construct an extractor which, given oracle access to a provers' strategy that leads to high acceptance probability, is able to reconstruct the ground state of a local Hamiltonian. Our result can be seen as a new form of self-testing, where, in addition to certifying a pre-shared entangled state, the verifier also certifies that provers have access to a quantum system, in particular, a ground state; this indicates a new level of verification for a proof of quantumness.