#proofsofquantumness

Quantum Zero Knowledge Proofs

Quantum Zero Knowledge Proofs Resist Superposition Attacks with Learning With Errors: A Key Post-Quantum Security Step.

Quantum News covers cryptography developments that address the ongoing issue of safe information sharing. This is crucial given the rapid rise in computing capacity and the threat of quantum computing. Researchers are perfecting methods to ensure data authenticity and privacy even against quantum-capable adversaries.

Zero-knowledge proofs are key to this accomplishment. These advanced cryptographic methods let one party prove a statement without further information. This is needed for internet privacy.

Superposition assaults are a major shortcoming that the current study solves instantly. In such attacks, a malicious verifier may try to acquire a quantum superposition of potential protocol transcripts. They could retrieve crucial quantum prover data that should be kept private.

Andrea Coladangelo, Ruta Jawale, Dakshita Khurana, Giulio Malavolta, and Hendrik Waldner meticulously summarised the work, “MPC in the Quantum Head (or: Superposition-Secure (Quantum) Zero-Knowledge)”. Ishai et al. introduced “MPC-in-the-head” (multi-party computing in the head), which they extended. Effective zero-knowledge protocols are created by embedding a calculation inside the cryptographic evidence. This research strengthens the protocol against quantum threats by expanding this to complex multi-party compute settings.

Addressing Malicious Verifiers: Zero-Knowledge Proofs of Quantumness at Dawn

Proofs of quantumness (PoQ) methods used to ensure that an honest quantum prover might persuade a verifier (quantum completeness) and that a classical prover could not misrepresent quantum capabilities. However, the classical verifier acting maliciously was crucial but unexplored.

A factoring-based PoQ technique, like Shor's approach for factoring big integers, may have a rogue verifier. Malicious verifiers (V) may replace a purposefully selected ‘N‘ (such as an RSA public key) for a randomly generated very large integer. This could allow V* to gather factors p and q beyond only proving quantumness by using the quantum prover (P) to factor ‘N*’. The need of preventing malicious verifiers from accessing valuable quantum prover data is highlighted.

The unique concept of Zero-Knowledge Proofs of Quantumness (ZKPoQ) applies here. ZKPoQ's intuitive zero-knowledge property states that the classical verifier's knowledge from the quantum prover shouldn't be more than what a classical prover could reproduce with the same verifier. The interactive proving technique should only prove “the prover possesses quantum capabilities”. The quantum server's processing capability is no longer “swindled by classical users” during verification, preventing the verifier from misusing the quantum prover's capabilities.

Learning With Errors (LWE): Post-Quantum Security's New Foundation

Learning With Errors (LWE) is key to the new protocols. LWE, a computationally difficult mathematical issue, underpins several post-quantum cryptography methods. It boosts confidence in the protocols' security.

Damgard et al. showed that superposition-resistant zero-knowledge protocols often employed “perfectly hiding and unconditionally binding dual-mode commitments” and other specialised promises. Cryptographic approaches sometimes lacked computational presumptions. However, the current solution deliberately builds its protocols on the well-known LWE problem to overcome this restriction.

Additionally, LWE provides LWE-based PoQ, an essential family of PoQ approaches. Interactive cryptography between a quantum prover and a classical verifier is used in these systems. Quantum prover responds to verifier challenges. Compared to factoring-based PoQ, LWE-based PoQ requires fewer quantum resources to implement. Unlike sampling-based PoQ, which is computationally intensive to verify, LWE- and factoring-based PoQ approaches enable classical verification.

Key New ZKPoQ Protocol Innovations:

Within the ‘common reference string’ (CRS) model, researchers propose two new three-round techniques. The prover and verifier share a public random string under this cryptographic paradigm. Validating calculations while protecting data is possible using these methods.

Resistance to Superposition Attacks: Verifiers try to acquire a quantum superposition of potential protocol transcripts, but the protocols are designed to withstand this. This talent is crucial for post-quantum security.

Diverse Complexity Class Support:

The first protocol provides a zero-knowledge argument for NP (nondeterministic polynomial time) problems. The direct reduction of its security to LWE difficulty provides a strong guarantee.

With the second protocol, QMA (quantum nondeterministic polynomial time), the quantum equivalent of NP, is also resistant. This shows the framework's adaptability by offering a LWE-based zero-knowledge argument for quantum difficulties.

Security Mechanism via Extractable NIZK: By carefully managing information flow, the protocols prevent the verifier's superposition state from revealing the secret being confirmed. Preventing quantum superposition attacks requires this. The verifier's extractable Non-Interactive Zero-Knowledge (NIZK) proof is a technological advance.

In the factoring-based ZKPoQ scheme, the verifier must provide an extractable-NIZK proof of ‘N’s factors (p, q). Preventing a malicious verifier from producing a valid proof without comprehending the elements limits their attitude.

For the LWE-based ZKPoQ approach, the verifier offers an extractable-NIZK proof of the LWE secret. This NIZK's “extractability” allows a classical simulator to duplicate the quantum prover's communication without a genuine quantum resource by extracting secret information from the verifier's evidence, such as p, q, or the LWE secret “s”. Simulation legally defines zero-knowledge. Even if a classically secure extractable-NIZK proof is sufficient for this transformation, post-quantum secure proofs (based on LWE) are needed for certifiable randomness from quantum devices or key leasing.