🤖 machine learning

Certified in Theory, Broken in Practice: Assumption Gaps in Cryptographic Model Certification

This paper reveals that current cryptographic model certification protocols are vulnerable to attacks where models behave well on fixed audit datasets but fail in practice due to unverified generalization, and it proposes rigorous security definitions and a new protocol template to ensure certified guarantees hold for fresh data from the same distribution.

Original authors: Carter Luck, Olive Franzese-McLaughlin, Elisaweta Masserova, Akira Takahashi, Antigoni Polychroniadou, Nicolas Papernot

Published 2026-07-27

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Carter Luck, Olive Franzese-McLaughlin, Elisaweta Masserova, Akira Takahashi, Antigoni Polychroniadou, Nicolas Papernot

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where we can ask a computer to make important decisions—like approving a loan, diagnosing an illness, or deciding who gets a job—without ever seeing the computer's "brain." This is the promise of Privacy-Preserving Machine Learning. It's like hiring a chef to cook a secret family recipe for you; you want to taste the dish to make sure it's delicious (accurate) and fair (doesn't discriminate), but you don't want to see the recipe or the ingredients because they are the chef's trade secrets.

To solve this, scientists use Zero-Knowledge Proofs (ZKPs). Think of this as a magic trick where the chef proves they followed the recipe perfectly without ever showing you the ingredients. They use complex math to create a "certificate" that says, "I promise this dish is 99% delicious," and the math guarantees they aren't lying. For a long time, everyone assumed that if the math said the certificate was valid, the dish would taste great no matter who ate it. But what if the chef could trick the magic trick? What if they cooked a special version of the dish just for the taste-tester, knowing exactly what the tester would ask for, while serving a completely different (and terrible) meal to everyone else? That is the question this paper asks.

The Great Audit Heist: Certified in Theory, Broken in Practice

This paper, titled "Certified in Theory, Broken in Practice," reveals a sneaky loophole in how we currently check these secret AI models. The authors, a team of researchers from universities and J.P. Morgan, discovered that the "magic certificates" used to verify AI models can be easily faked if the model creator knows what the test will look like beforehand.

The Setup: The Blind Taste Test

In the real world, when a company wants to prove their AI is fair or accurate, they usually hire an auditor. The auditor picks a list of test questions (a dataset) and asks the AI to answer them. The AI owner then uses a Zero-Knowledge Proof to say, "Look, I answered 99% of these correctly, and I didn't cheat!"

The problem is that in many current systems, the AI owner gets to see the test questions before they lock in their final model. It's like a student getting the exact exam questions a week before the test, memorizing the answers, and then handing in a blank sheet of paper that magically proves they knew the answers.

The Attack: Cooking for the Judge

The authors show that a malicious model owner can "forge" their training data to pass the audit while failing in the real world. They call this a Data Forging Attack.

Here is how the trick works, using the analogy of a Decision Tree (a flowchart that makes decisions):

The Setup: The auditor gives the model owner a specific list of 1,000 test questions (the audit dataset).
The Trick: The model owner takes those 1,000 questions and creates thousands of "neighbor" points around them. They add these new points to their training data, but they flip the answers (labels) on these neighbors. They also add a rule to their model: "If the question looks exactly like one of the 1,000 test questions, give the right answer. If it looks even a tiny bit different (like our new neighbor points), give the wrong answer."
The Result: When the auditor runs the test, the model gets 99% or even 100% correct because it has memorized the test. The Zero-Knowledge Proof checks out, and the model gets certified as "High Accuracy."
The Betrayal: But as soon as the model is deployed to the real world and sees new data (even data that looks very similar to the test data), it fails miserably. In the paper's experiments, models that passed with 99% accuracy on the test dropped to less than 30% accuracy on new, fresh data.

The authors tested this on fairness audits too. They showed a model could look perfectly fair on the test list (giving equal approval rates to different groups) but be wildly unfair in the real world, denying loans to specific groups almost 100% of the time.

Why Simple Checks Don't Work

You might think, "Wait, couldn't the auditor just check if the training data looks like the test data?" The paper shows that the attackers are smart enough to fool even standard statistical tests. By adding extra copies of the test data into the training set, the attacker makes the two datasets look statistically identical. Tests like Welch's t-test (a common way to see if two groups of numbers come from the same source) would look at the data and say, "Yep, these look the same!" even though the model is secretly rigged.

The authors ran simulations on six different real-world datasets (like credit card defaults and employment records) and found that this attack works reliably. They even showed that the attack works on more complex models like XGBoost and Neural Networks, not just simple decision trees.

The Solution: The Surprise Test

So, how do we fix this? The paper proposes a new way to run these audits, which they call a Secure Cryptographic Model Certification (CMC).

The key idea is simple but powerful: The model owner must lock in their model before they see the test questions.

Imagine a game where:

The student (model owner) writes their answers on a piece of paper and seals it in a locked box (a cryptographic commitment).
Only after the box is sealed does the teacher (auditor) hand them the exam questions.
The student then uses the magic proof to show they answered the questions correctly based on what's inside the box.

Because the student couldn't see the questions when they locked the box, they couldn't rig the answers. The paper proves mathematically that if you follow this "Commit-Sample-Prove" order, the model must actually be good at the task, not just good at passing the test.

What This Means

The authors are careful to say they aren't saying the old math is "broken" or that the Zero-Knowledge Proofs themselves are wrong. The math works perfectly; it's just that the rules of the game were flawed. The old rules allowed the model owner to cheat by knowing the test in advance.

This paper serves as a wake-up call. It shows that for privacy-preserving AI to be truly trustworthy, we can't just rely on a one-time test with a known dataset. We need to ensure the test is a surprise, or we need to keep checking the model continuously with fresh data. Without these changes, we risk deploying AI systems that are certified as "perfect" but are actually broken in the real world.

Technical Summary: Certified in Theory, Broken in Practice

Problem Statement

The paper addresses a critical vulnerability in Cryptographic Model Certification (CMC) protocols used for privacy-preserving machine learning auditing. While existing CMC frameworks utilize zero-knowledge proofs (ZKPs) and cryptographic commitments to verify model properties (e.g., accuracy, fairness, differential privacy) without revealing model internals or training data, they suffer from a fundamental assumption gap.

Current security definitions typically certify that a model satisfies a property $f$ on a fixed audit dataset $S_{audit}$ . However, they fail to guarantee that this property generalizes to the underlying data distribution $D$ from which $S_{audit}$ is drawn. The authors argue that if the model provider (prover) knows the audit dataset prior to committing to their model, they can engage in data forging attacks. By carefully engineering the training data, a malicious provider can produce a model that passes the cryptographic audit (exhibiting "benign" behavior on $S_{audit}$ ) while exhibiting "pathological" behavior on fresh samples from the same distribution $D$ . This creates a false sense of security, allowing models to be deployed that fail to meet their intended guarantees in real-world scenarios.

Methodology

1. Threat Model and Attack Game

The authors formalize a threat model involving a malicious model provider (prover) and an honest-but-curious auditor (verifier). They introduce an Adaptive Training with Known Auditing Data game (Definition 3) to demonstrate the vulnerability:

Setup: The adversary receives an audit dataset $S_{audit} \sim D^\ell$ .
Goal: The adversary outputs a hypothesis $h$ $h$ and training data $S_{train}$ $S_{t r ain}$ such that:
1. The model passes the audit: $f(h, S_{train}, S_{audit}) = 1$ .
2. The model fails the true security property on the distribution: $F(h, S_{train}) = 0$ .
3. The model satisfies a utility predicate $L$ (e.g., maximizing claim denials for an insurance provider).

2. Data Forging Attacks

The paper presents three concrete data forging strategies that bypass standard cryptographic defenses (ZKPs and commitments) without altering the training process itself, but rather by manipulating the input data:

Attacking Accuracy: Using Algorithm 1, the attacker constructs a training set $S'_{train}$ containing the audit points with correct labels, augmented by $\epsilon$ -perturbed neighbors labeled with the opposite class. When trained on this data (e.g., using Decision Trees until leaf homogeneity), the model achieves perfect accuracy on $S_{audit}$ but predicts the opposite label for any point outside the $\epsilon$ -neighborhood of the audit data, resulting in near-zero accuracy on the rest of the distribution.
Attacking Fairness: Using Algorithm 2, the attacker manipulates sensitive attributes and labels. On the audit set, labels are randomized to ensure demographic parity (appearing fair). On the rest of the distribution, the model learns to predict based on sensitive attributes, resulting in maximal unfairness.
Attacking Differential Privacy (DP): Using Algorithm 3, the attacker duplicates specific data points in the training set. Since DP sensitivity depends on the change in output when a single record is modified, duplicating records breaks the sensitivity assumptions, allowing the attacker to train a model with significantly worse privacy guarantees than claimed, while still passing a ZK proof of "correct DP training procedure."

3. Statistical Evasion

The authors demonstrate that these forged datasets are indistinguishable from honest datasets under standard statistical tests. By adding sufficient copies of the audit data to the training set, the attacker ensures that the training data and audit data pass Welch's t-test and Levene's test (checking for mean and variance equality) with high probability, rendering statistical detection ineffective.

4. Secure CMC Template

To mitigate these attacks, the paper proposes a Commit-Sample-Prove protocol template ( $\Pi_{csp}$ ):

Commit: The model provider first commits to their model $h$ (and optionally training data) using a cryptographic commitment scheme.
Sample: Only after the commitment is received, the auditor samples the audit dataset $S_{audit}$ from the distribution $D$ .
Prove: The provider and auditor execute a ZKP to verify that the committed model satisfies the empirical predicate $f$ on the newly sampled $S_{audit}$ .

This ordering ensures $S_{audit}$ is independent of the model $h$ and the training data, preventing the provider from tailoring the data to the audit set. The authors provide formal definitions for $\tilde{F}$ -relaxed knowledge soundness, ensuring that if a model passes the audit, it satisfies the desired property $F$ on the distribution (up to a small, quantifiable error bound derived from concentration inequalities).

Key Contributions

Identification of Data-Dependent Vulnerabilities: The paper identifies that existing CMC schemes are vulnerable to data forging when the audit dataset is known to the provider prior to model commitment. This gap allows for the certification of models that are "broken in practice" despite passing theoretical audits.
Empirical Demonstration of Attacks: Through experiments on six benchmark datasets (e.g., Adult, COMPAS, German Credit) using Decision Trees, XGBoost, and Neural Networks, the authors show that:
- Models can achieve >99% accuracy on audit data while dropping to <30% on fresh samples.
- Models can appear perfectly fair on audit data while being maximally unfair in deployment.
- These attacks evade detection by standard statistical tests (Welch's t-test).
Systematic Case Study: The authors analyzed nine recent works in security and machine learning (including zkCNN, Confidential-DPproof, and OATH). They found that six of these works are at least partially vulnerable because they either utilize public datasets for auditing or fail to enforce commitment before dataset revelation.
Formal Security Framework: The paper introduces rigorous security definitions tailored to CMC, distinguishing between dataset-specific guarantees and distributional guarantees. It provides a generic protocol template ( $\Pi_{csp}$ ) and proves its security under standard cryptographic assumptions, ensuring that certified properties generalize to the underlying distribution.

Results

Vulnerability: In the attack game, adversaries successfully passed audits requiring 99% accuracy while achieving only ~30% accuracy on test data. Similarly, models passed fairness audits with near-zero disparity gaps but exhibited near-maximal disparity on test data.
Undetectability: The forged training datasets passed Welch's t-tests and Levene's tests against the audit dataset with significance levels of $\alpha=0.05$ , demonstrating that statistical checks cannot reliably distinguish malicious training data from honest data in this context.
Restoration of Security: The proposed $\Pi_{csp}$ template was shown to be compatible with existing ZKP constructions (e.g., for decision trees and CNNs). By applying the "commit-then-sample" order, the security of these protocols is restored, preventing the data forging attacks.

Significance and Claims

The paper claims that its findings serve as cautionary evidence rather than a declaration that prior cryptographic works are technically broken. The core assertion is that the security guarantees provided by existing CMC frameworks do not align with the practical requirements of auditing, which demand that certified properties hold on fresh data from the same distribution, not just on a specific audit set.

The authors emphasize that:

Secure audit solutions utilizing known public datasets or reusing test datasets (where the provider learns the data) are unlikely to provide robust guarantees.
The importance of continuous sampling of fresh data or cryptographic mechanisms that hide the audit data until the model is committed is paramount for a successful audit infrastructure.
Future designs for cryptographically secure ML auditing must explicitly address the gap between dataset-specific certification and distributional generalization, requiring close communication between cryptography, security, and machine learning communities.

The work does not claim to solve all privacy-preserving auditing challenges (e.g., efficient DP certification remains difficult due to the need for trusted training data generation) but provides a foundational framework and a specific protocol template to mitigate the identified data-forging vulnerabilities.