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.
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. ---
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.
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.
The advent of quantum computing poses substantial risks to conventional cryptographic mechanisms, particularly hash-based authentication and zero-knowledge identification (ZKI) protocols, which are susceptible to quantum algorithms such as Grover's and Shor's. This study presents a comprehensive benchmarking framework for evaluating the quantum resistance of cryptographic hash functions through performance metrics (execution time, memory utilization), statistical characteristics (entropy, bit-level randomness, avalanche effect), and security attributes (collision and preimage resistance) across diverse input sizes and edge conditions. A novel hybrid hashing strategy, integrating SHA-512 and BLAKE3 in a defense-in-depth configuration, is introduced to enhance post-quantum resilience. Its efficacy is validated via Grover's algorithm simulations, demonstrating a methodology for evaluating the increased computational workload for quantum search algorithms relative to conventional hash functions. The framework incorporates visualization utilities and structured reporting modules, enabling systematic assessment and practical implementation of quantum-resistant cryptographic solutions within ZKI systems. Findings indicate that while classical hashes such as SHA-256 and SHA-512 exhibit theoretically diminished security in quantum threat scenarios, the proposed hybrid method acts as a practical risk mitigation strategy with acceptable computational overhead, providing a viable pathway for safeguarding authentication systems against quantum-capable adversaries.