Zero-Knowledge Proof

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

• Honest Verifier: A verifier that follows the protocol specification without deviation.
• Deterministic Acceptance: The probability of acceptance for a true statement is 1 (or negligibly close to 1 in statistical ZKPs).
• Example: A prover who actually knows the pre-image of a hash will always succeed in convincing the verifier.

If the statement is false, no cheating prover can convince the honest verifier that it is true, except with some negligible probability.

• Computational Soundness: Security holds against provers with bounded computational power (standard for most practical ZKPs like zk-SNARKs).
• Statistical Soundness: Security holds against computationally unbounded provers (achieved by zk-STARKs).
• Knowledge Soundness: A stronger variant where an extractor algorithm can recover the witness from any successful prover, proving the prover actually 'knows' the secret.

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

• Simulation Paradigm: The standard definition requires a simulator that can produce transcripts indistinguishable from real interactions without access to the secret.
• Perfect ZK: The simulated and real distributions are identical.
• Computational ZK: The distributions are computationally indistinguishable.
• Example: In a ZKP of a Sudoku solution, the verifier learns the puzzle is solved but gains no hints about the filled-in numbers.

A highly desirable but non-mandatory property where the proof size is very small and verification is exponentially faster than re-executing the computation.

• zk-SNARK: Zero-Knowledge Succinct Non-Interactive Argument of Knowledge. Proofs are constant-sized (often < 1 KB) and verified in milliseconds.
• Scalability: Enables a weak verifier (like a blockchain node) to check complex computations without re-running them.
• Trade-off: Succinctness usually requires a trusted setup phase, unlike non-succinct STARKs.

The proof consists of a single message from prover to verifier, eliminating back-and-forth communication. Essential for asynchronous systems.

• Fiat-Shamir Heuristic: Transforms interactive protocols into non-interactive ones by replacing the verifier's random challenges with the output of a cryptographic hash function.
• Common Reference String (CRS): A shared public string generated during a trusted setup that enables non-interactive proofs.
• Practical Impact: Allows a prover to generate a proof offline and broadcast it to many verifiers independently, critical for blockchain applications.

ZKPs enable a model provider to cryptographically prove that specific data was unlearned without revealing the data itself or the model weights.

• Verifiable Unlearning: The prover generates a ZKP attesting that the current model weights are statistically indistinguishable from weights trained without the target data.
• Privacy Preservation: The auditor verifies compliance with deletion requests without accessing the underlying training data or proprietary model architecture.
• Regulatory Alignment: Directly satisfies the audit requirements of GDPR's 'Right to be Forgotten' without exposing trade secrets.

A mathematical framework that provides provable privacy guarantees by injecting calibrated noise into computations, ensuring the output does not reveal the presence or absence of any single individual in the dataset. When combined with zero-knowledge proofs, it enables verifiable claims about the statistical indistinguishability of a model trained with and without specific data points, forming the backbone of certified removal guarantees.

A formal guarantee, often based on differential privacy, that a machine unlearning algorithm has bounded the influence of deleted data points within a provable mathematical threshold. This mechanism relies on cryptographic principles similar to zero-knowledge proofs to provide an auditable, mathematically sound assertion that unlearning has occurred to a specified degree without requiring full model transparency.

A privacy attack that determines whether a specific data record was used to train a machine learning model. In the context of zero-knowledge proof systems for unlearning, these attacks serve as the primary auditing tool. A successful unlearning procedure should render the model unable to distinguish between members and non-members of the deleted set, providing empirical verification of the proof claim.

The empirical process of auditing a model post-unlearning using membership inference attacks, backdoor triggers, or statistical tests to ensure target data influence has been sufficiently removed. This verification layer is where zero-knowledge proof protocols are implemented, allowing a third-party auditor to confirm deletion efficacy without accessing the underlying training data or model internals.

The tracking of data's origin, movement, and transformation throughout its lifecycle, providing the necessary provenance to identify and isolate specific data shards for targeted unlearning. Robust data lineage is a prerequisite for constructing a valid zero-knowledge proof of removal, as the prover must cryptographically demonstrate they are referencing the correct data without revealing the data itself.