Zero-Knowledge Proof

If the statement is true and both the prover and verifier follow the protocol honestly, the verifier will always be convinced of the statement's validity.

• Mechanism: An honest prover possessing a valid witness can successfully answer all of the verifier's challenges.
• Practical meaning: A legitimate model owner can always generate a proof that their inference was computed correctly.
• Failure mode: A protocol lacking completeness would reject valid proofs, making it useless for real-world deployment.

This property ensures the proof system is functional for honest participants.

If the statement is false, no cheating prover can convince the verifier otherwise, except with some negligible probability.

• Computational soundness: Security holds against provers with bounded computational resources, relying on cryptographic hardness assumptions.
• Statistical soundness: Security holds against computationally unbounded provers, offering stronger guarantees.
• Knowledge soundness: A stronger variant where a cheating prover cannot succeed unless they actually possess a valid witness.

Soundness prevents a malicious client from falsely claiming their model update satisfies aggregation rules.

The verifier learns nothing beyond the validity of the statement itself. No information about the witness is leaked during the interaction.

• Perfect zero-knowledge: The verifier's view can be simulated exactly without access to the witness, proving absolutely no information leakage.
• Computational zero-knowledge: The simulated view is computationally indistinguishable from the real interaction.
• Formal definition: For every possible verifier strategy, there exists an efficient simulator that produces an indistinguishable transcript without the witness.

This property ensures a server can verify a model's correctness without learning the proprietary weights.

An additional property often bundled with soundness, requiring that a prover who convinces the verifier must actually know the witness, not merely that one exists.

• Extractor: A theoretical algorithm that, given special access to the prover, can extract the witness, proving the prover's knowledge.
• Relevance to ML: In verifiable inference, this guarantees the prover actually executed the model rather than guessing a plausible output.
• Distinction: A proof can be sound without being a proof of knowledge if it only demonstrates existence.

This property is essential for accountability in delegated computation scenarios.

A practical property of modern ZK-SNARKs and ZK-STARKs where the proof size and verification time are dramatically smaller than the computation being proved.

• Constant size: Proof size remains small regardless of the complexity of the statement being proven.
• Sub-linear verification: The verifier checks the proof in time logarithmic or constant relative to the computation size.
• ML application: A succinct proof of a large transformer inference can be verified in milliseconds on a smartphone.

Succinctness transforms ZKPs from a theoretical curiosity into a scalable tool for on-chain and edge verification.

A single message from prover to verifier suffices, eliminating the need for back-and-forth communication. This is achieved through the Fiat-Shamir heuristic.

• Fiat-Shamir transform: Replaces the verifier's random challenges with the output of a cryptographic hash function applied to the protocol transcript.
• Random oracle model: Security is proven assuming the hash function behaves like a truly random function.
• Practical benefit: Proofs can be generated offline, stored, and verified asynchronously by anyone.

Non-interactivity enables publicly verifiable proofs where a single proof can convince an unlimited number of verifiers.

A cryptographic primitive that allows a prover to commit to a chosen value while keeping it hidden from a verifier. The prover cannot change the value after committing, but can later reveal it. In ZKP systems, commitments bind a prover to a specific witness before the proof interaction begins, preventing them from adaptively choosing responses based on the verifier's challenges. Common constructions include Pedersen commitments (based on discrete log) and hash-based commitments using collision-resistant hash functions.

A method for distributing a secret among a group of participants where each holds a share, and only a qualified subset can reconstruct the original secret. In the context of ZKPs for secure aggregation, secret sharing enables distributed proof generation where multiple parties collectively prove a statement without any single party holding the complete witness. This is foundational for Verifiable Secret Sharing (VSS), which ensures shares are consistent and prevents malicious dealers from distributing invalid shares.

A cryptographic mechanism for verifying the authenticity and integrity of a digital message. In ZKP-based ML systems, digital signatures authenticate the identity of clients submitting model updates. When combined with ZKPs, aggregate signature schemes can compress multiple signatures into a single short proof, dramatically reducing verification overhead. This ensures that only authorized participants contribute to federated learning rounds while maintaining the privacy guarantees of the underlying ZKP protocol.

A foundational computational problem in lattice-based cryptography conjectured to be hard even for quantum computers. LWE underpins many post-quantum secure ZKP constructions. The problem involves solving a system of noisy linear equations, where the noise prevents efficient extraction of the secret. ZKP systems built on LWE provide post-quantum security guarantees, ensuring that proofs of correct model training or inference remain sound even against adversaries with access to large-scale quantum computers.

A form of encryption that allows the direct computation of the sum of plaintexts by operating on their corresponding ciphertexts. When combined with ZKPs, AHE enables a server to aggregate encrypted model updates while clients generate zero-knowledge proofs that their individual contributions are well-formed and within expected bounds. This hybrid approach provides both input privacy (via encryption) and computational integrity (via ZKPs), preventing malicious clients from poisoning the global model with crafted updates.

The resilience of a distributed system to arbitrary or malicious failures. In ZKP-augmented secure aggregation, Byzantine fault tolerance ensures correct computation even when some nodes exhibit adversarial behavior. ZKPs enforce honest behavior by requiring each participant to prove their update is correctly computed without revealing the update itself. This transforms a malicious security model into a verifiable one, where any deviation from the protocol is cryptographically detectable and the offending party can be excluded from the aggregation round.