How Quantum Communication Can Bypass Classical Privacy Limits

tl;dr Emil (my roommate while I was at Harvard) and I recently released work on how to obtain a quantum (accuracy) advantage for two-party differential privacy. Classically, there is a lower bound on how accurate any mechanism can be for two-party differential privacy. It turns out that we can circumvent that lower bound with the use of quantum communication!

Suppose we have two laboratories that hold confidential yes-or-no (i.e., for the presence or absence of a viral infection) test results for the same set of study participants. The labs want to know how often their results disagree, without exchanging everyone’s individual results. Both laboratories should finish with the same estimate.

Study participant	1	2	3	4
Laboratory A	Yes	No	Yes	Yes
Laboratory B	Yes	Yes	No	Yes

In this example, the laboratories disagree on participants 2 and 3, so the disagreement count is two. We can call this count the Hamming distance.

The calculation is fairly straightforward. But the privacy problem is harder: how can the laboratories compute it without exposing the individual entries along the way?

In our new work Quantum Advantage for Two-Party Differential Privacy, Emil T. Khabiboulline and I show that quantum communication can bypass a classical limit on the accuracy of this task. The result applies to a specific model: participants must send exactly the messages specified by the protocol and complete the interaction. Within that model, the expected error can stay constant as the lists grow.

A private answer needs a private conversation

Differential privacy requires that changing one entry in a confidential dataset have only a limited effect on what an observer can learn. Here, each laboratory needs that protection against the other.

Suppose a trusted analyst could receive both lists. Changing one entry changes the disagreement count by at most one, so the analyst can add a calibrated amount of random noise before releasing the answer. For a fixed privacy level, the required noise need not grow with the number of participants.

Without a trusted analyst, the laboratories must exchange messages to compute the answer themselves. Those messages can expose information that never appears in the final result. Sending an entire list and then adding noise to the answer would clearly fail to protect that list from its recipient. Privacy must therefore account for everything a participant is allowed to retain from the interaction, including private notes/randomness and copies of messages.

The classical accuracy barrier

Classical lower bounds show that satisfying differential privacy in the two-party setting has a substantial accuracy cost [1]. Fix a sufficiently strong level of pure differential privacy, and require both parties to receive the same estimate. Even the best classical protocol has (worst-case) inputs for which the average size of its error grows at least proportionally to the square root of the list length. This applies to information-theoretic privacy: protection must hold even against an observer with unlimited computing power [1]. Essentially, a hundredfold increase in list length therefore produces a tenfold increase in the square-root lower-bound scale. This describes how the unavoidable error grows.

Classical cryptography offers another route. Under (suitable) computational assumptions, secure computation can reproduce the accuracy available with a trusted analyst. That protection relies on certain computations being infeasible for the observer. Our main question is whether quantum communication can achieve constant error without relying on computational hardness assumptions.

On copying messages

A classical participant can save a copy of every message and still carry out the protocol correctly. Returning the original message, or deleting a working file, does not erase a copy already made. This ability to retain a transcript is central to the classical lower bounds. Quantum messages are quite different. Our protocol uses quantum states that overlap (in a precise way): the possible messages cannot be perfectly distinguished. Essentially, because of physical constraints, extracting a distinguishing record from such states cannot leave them exactly undisturbed.

Our construction uses a small, input-independent component, called a guard, to create the required overlap. Alice sends her encoded input and private randomness to Bob. Bob performs the prescribed quantum computation and returns the entire resulting state. We prove that returning exactly the prescribed state forces any extra system Bob retains from this round trip to be independent of Alice’s encoded input. He can subsequently learn the permitted noisy statistic, but the round trip cannot leave him an additional input-dependent record. Thus, the same rule has different consequences in the two settings. Classical messages can be copied while sending every prescribed message correctly. The quantum messages used here cannot support that kind of copying. This is how the protocol gets outside the scope of the classical lower bound.

Producing one answer that protects both parties

There is another useful detail: each party supplies independent random noise. If Alice generated all the noise, she would know it and could subtract it from the result. Bob would have the same advantage if he generated all the noise. Including both contributions means each participant faces uncertainty from the other participant’s private randomness. After the quantum round trip, Alice obtains the noisy result and sends the classical release to Bob. Both decode it in the same way and obtain the same estimate. For fixed privacy parameters, the expected absolute error is bounded independently of the list length. Communication grows linearly with that length. The advantage established in our work concerns accuracy under privacy constraints.

The conditions

The privacy guarantee concerns each participant’s complete information at the end of the protocol, subject to exact preservation of the prescribed messages and completion of every round. Participants may keep arbitrary private systems if they satisfy those conditions. A participant who measures a revealing intermediate message and then aborts falls outside this model. In our paper, we explain why such an attack prevents this construction from providing security against arbitrary malicious behavior. Extending the accuracy advantage to stronger adversaries remains open.

Also, the accuracy guarantee is an average over the protocol’s randomness. A rare fallback associated with the guard can produce a larger error; its probability is chosen to keep its contribution to expected error small.

The main takeaway of our work is that the physical nature of communication can affect the price of privacy. For this task of computing the Hamming distance (or inner products), the classical accuracy barrier depends on the ability to copy messages. Quantum communication changes that resource and allows both participants to learn a more accurate shared statistic.

References

[1] A. McGregor, I. Mironov, T. Pitassi, O. Reingold, K. Talwar, and S. Vadhan. The limits of two-party differential privacy. Electronic Colloquium on Computational Complexity, Tech. Rep. TR11-106, 2011. [Online]. Available: https://eccc.weizmann.ac.il/report/2011/106/

[2] Daniel Alabi, Emil T. Khabiboulline. Quantum Advantage for Two-Party Differential Privacy. https://eprint.iacr.org/2026/1669

How Much Can a Zero-Knowledge Proof Leak?

tl;dr Recently, Marshall Ball and I released work on the computational complexity of multiplicative zero-knowledge (MZK), a new definition of zero-knowledge, and its relation to a well-studied definition of zero-knowledge, statistical zero-knowledge (SZK). We show that up to a certain level of leakage, both definitions are equivalent in terms of computational power. That is, allowing (logarithmic) leakage can change how we prove a statement without changing whether the statement belongs to SZK.Then as we allow more leakage, MZK becomes closer in power to IP/PSPACE (i.e., can solve all problems that interactive proof systems can solve). In my class, starting next week, we will begin discussing zero-knowledge definitions and protocols.

Motivations

Suppose a website needs to check that you are over eighteen. One approach is to upload a photograph of your identification. But that may reveal much more than the website needs: your exact birth date, address, photograph, and identification number. However, the question the website needs answered is actually much narrower: Does this person satisfy the age requirement?

Zero-knowledge proofs offer a way to separate that answer from the information used to establish it. A person can prove that an authentic credential satisfies an age requirement without handing over the underlying credential. This is a concrete application of the technology: Google’s digital-identity documentation describes zero-knowledge proofs for verifying claims such as “over eighteen” while minimizing disclosure of credential information.

Here is another example: A service might want aggregate statistics without seeing individual contributions. Yet privacy alone is not enough: malicious participants could submit malformed values that corrupt the result. The system needs to verify that contributions satisfy its rules without exposing them. Prio, for example, combines private aggregation with secret-shared proofs that help protect the computation against malicious clients.

These two applications share a common theme:

How can we verify that someone followed the rules without demanding the private information that makes verification easy?

It turns out that zero knowledge is the right tool! And there are several different definitions that imply a surprisingly rich tradeoff between privacy, efficiency, and computational power.

In a recent work, Marshall Ball and I study whether and how multiplicative relaxation of zero-knowledge (MZK) is related to statistical zero-knowledge (SZK). It turns out MZK can improve efficiency, relative to SZK, without enlarging the class of provable problems but when leakage is at most logarithmic. At larger leakage budgets, we show both conditional and oracle separations, and shows that polynomially bounded leakage eventually recovers the full power of interactive proofs.

Our work was driven by the following questions: Can allowing leakage make a proof cheaper? And can allowing leakage make a fundamentally different kind of statement provable?

First, let’s recall the (high-level) definition of zero-knowledge.

What does “zero knowledge” actually mean?

A proof system has a prover, who tries to prove a public statement, and a verifier, who checks it. A useful system must convince the verifier when the statement is true, while preventing a dishonest prover from successfully proving a false statement (except with a small probability). Zero-knowledge adds a privacy requirement: the interaction should not give the verifier information beyond what it could efficiently generate from the public statement itself.

That last requirement is formalized through a simulator: Imagine a program that receives the public statement but not the prover’s secret evidence (called the witness). The simulator must produce an artificially created record of what the verifier would see during the proof. If that record looks like a real interaction, the verifier has not obtained something that required access to the prover’s secret. Note that the simulator is not discovering the secret nor proving the statement through a genuine interaction. It is manufacturing a record. The difference matters: a real cheating prover must answer challenges as they arrive, while an offline simulator can construct a whole conversation in a different order. A simulator transcript need not be something a prover could generate while interacting with an independently randomized verifier.

Essentially, to prove privacy, we will look at two distributions: $R=$ the verifier’s view in a real proof, $Q=$ the simulator’s output.

Different notions of zero-knowledge impose different requirements on how closely these distributions must agree.

Why statistical zero-knowledge?

In statistical zero-knowledge, or SZK, the real and simulated views must have negligible statistical distance. Recall that statistical distance measures the largest difference in probability that the two distributions assign to any event: $SD(R,Q) = \sup_E |R(E)-Q(E)|.$ Here, by “negligible”, we mean that the difference eventually becomes smaller than every inverse polynomial in the security parameter. The privacy requirement is therefore much stronger than saying that the distributions are merely similar on average. This gives statistical zero-knowledge an operational interpretation. Once the real and simulated views are statistically close, even an observer with unlimited computational power cannot distinguish those two distributions with more than negligible advantage. (This holds regardless of whether the observer is able or unable to solve a difficult computational problem.)

For comparison, computational zero-knowledge requires only that efficient observers/adversaries be unable to distinguish the distributions to gain information. The difference is between information that is statistically absent and information that is computationally inaccessible.

There is also an important difference between privacy and soundness. In complexity theory and cryptography, a proof must remain sound against computationally unbounded cheating provers. On the other hand, an argument only needs to hold against computationally bounded cheating provers. For this blog post, we only consider proofs.

SZK is a class of problems: it is about families of statements that admit proof systems with statistical simulation. Our paper follows the standard formulation, in the literature, using promise problems, where inputs are guaranteed to belong to specified yes- or no-cases.

An example: proving that two networks are different

Two graphs are isomorphic when renaming/relabelling their vertices makes them identical. Now consider the problem of proving that two graphs are not isomorphic. The verifier secretly chooses one graph, randomly renames its vertices, and sends the result to the prover. The prover identifies which original graph was chosen. If the graphs are non-isomorphic, a (powerful) prover can always answer correctly. If they are isomorphic, the challenge has the same distribution whichever graph was chosen, so no prover can guess the hidden choice with probability greater than one half.

For an honest verifier, simulation is straightforward: choose the graph and relabeling, then record the already-known answer. This gives perfect honest-verifier zero-knowledge (which is stronger than statistical distance closeness). Note that this simple protocol does not by itself lead to security against arbitrary cheating verifiers; that requires additional machinery.

A second example: proving that distributions are distinguishable

A more general example is Statistical Difference. The input consists of two efficient randomized programs, with a promise that their output distributions are either close or far apart.

Sahai and Vadhan [4] showed that this problem is complete for SZK: every problem in SZK can be (efficiently) converted into the statistical distance problem. Their work also develops transformations that polarize statistical distance, turning a suitable initial gap into distributions that are almost identical or almost disjoint. In the latter case, a prover can help a verifier identify which distribution generated a challenge sample. In our new paper, we leverage such promise problems to show equivalences (up to logarithmic leakage) between SZK and MZK.

Replacing statistical closeness with multiplicative closeness

Statistical zero-knowledge requires probabilities to agree up to a negligible additive difference. Multiplicative zero-knowledge, or MZK, instead permits a (controlled) multiplicative difference:

For every event $E$ , it requires $R(E)\le e^\varepsilon Q(E)+\delta$ and $Q(E)\le e^\varepsilon R(E)+\delta.$

Here, $\varepsilon$ controls multiplicative leakage, while $\delta$ is an additive simulation error. Both directions actually matter for the definition: neither distribution may assign an event substantially more probability than the other permits. When $\delta=0$ , the probabilities of any event (with positive probability) under either distribution differ by at most a factor of $e^\varepsilon$ . (When $\varepsilon=0$ , the two inequalities reduce to the statistical distance guarantee.)

The definition of MZK is, obviously, inspired by differential privacy. But the objects being compared are different. Differential privacy typically compares outputs on neighboring datasets. Here, the comparison is between a real interaction and a simulated interaction. There need not be any neighboring input relation. The relaxation can be substantial even when $\varepsilon$ is constant. For an elementary illustration, suppose $R(1)=\frac34, Q(1)=\frac14.$ These Bernoulli distributions have statistical distance $1/2$ , yet satisfy pure symmetric multiplicative closeness with $\varepsilon=\ln 3$ . Thus, constant multiplicative leakage does not imply negligible statistical leakage. Nor should $\varepsilon$ be read literally as the number of secret bits disclosed. It is a bound on probability/likelihood ratios.

Why relax zero-knowledge at all? Because of savings in communication

A privacy definition is useful partly because of the protocols it enables. Requiring a stronger simulation guarantee can mean sending more information, performing more computation, or using a more expensive interaction pattern.

PINE provides a concrete example. It verifies a norm bound on a secret-shared vector: a useful task when private contributions must be prevented from having excessive influence on an aggregate. Its statistical and differential variants have different communication costs. Under one parameter setting reported in the paper, the additional communication above basic aggregation is:

Vector dimension	Statistical PINE	Differential PINE
10,000	22%	4.77%
100,000	3.18%	1.46%
1,000,000	0.49%	0.32%
10,000,000	0.13%	12.63%

These results use $\varepsilon=0.1$ , with soundness and additive privacy errors set to $2^{-50}$ . They show the side-by-side results: multiplicative simulation can reduce overhead, but it does not improve every parameter regime. We emphasize that these percentages measure overhead, not total-communication reduction factors.

A separation for the same distributed task

In our recent work, we also give a theoretical explanation for the separation in communication costs.

We fix a randomized functionality. Suppose $m$ parties each hold a private bit $x_i$ . They want a common random output whose probability of being one is $\Pr[O=1] = \frac14+\frac{1}{2m}\sum_{i=1}^{m}x_i.$ The goal is not to reveal the individual bits, but to produce this specified (aggregate-dependent) random outcome. For powers of two $m$ , in our work, we construct a protocol using $(m-1)(\log_2 m+2)=O(m\log m)$ bits with constant multiplicative leakage of $\varepsilon=\ln 3$ and negligible additive error. In contrast, statistical simulation with error at most $1/(100m^2)$ requires $\Omega(m^2)$ communication. This is an unconditional separation for the specific setting we consider in the paper (see appendix A): private channels, independent private randomness, no correlated setup, fixed public communication schedule, and passive coalitions containing fewer than one third of the parties.

Note that this distributed setting is different from the single-prover, public-statement setting used to define SZK and MZK as complexity classes. But this motivates our exploration into MZK: Relaxing simulation can save communication even when the task/function being computed remains the same. But does this always change which problems admit proofs? We provide a negative answer!

A surprise: logarithmic leakage in MZK does not enlarge set of SZK problems

For me, this was surprising! Let $n$ denote the input length. One of our main theorems is that, with negligible completeness, soundness, and additive simulation errors, $\boxed{ \mathrm{HVMZK}[\varepsilon] = \mathrm{MZK}[\varepsilon] = \mathrm{SZK} \qquad \text{for }\varepsilon(n)=O(\log n). }$

The honest-verifier class, HVMZK, requires simulation only for the prescribed/honest verifier. MZK requires simulation against every efficient verifier, including verifiers that deviate from the protocol. At logarithmic leakage, both classes coincide with SZK. This is surprising because multiplicative closeness can be much weaker than statistical closeness. (The earlier Bernoulli example already showed that even constant multiplicative leakage permits constant statistical distance.)

How can these facts coexist? Because the theorem is about the existence of proof systems for a problem, not the privacy of a particular transcript distribution. A problem might have a very efficient multiplicative zero-knowledge protocol whose transcripts are not statistically simulatable. The theorem says that the same problem also has some statistical zero-knowledge proof. That is, the statistical zero-knowledge proof may use a different interaction and have different costs. The theorem does not imply that we will preserve the original protocol’s efficiency or statistically simulate its original transcripts.

Why does a logarithm appear?

For some constant $C$ , consider $\varepsilon(n)=C\log n,$ then $e^{\varepsilon(n)}$ is polynomial in $n$ . But when $\varepsilon(n)$ grows faster than logarithmically, that factor becomes superpolynomial. Consider the event $A$ that a simulated conversation is valid and accepting. On a true statement, the real proof accepts with high probability. Then by definition, we get $Q(A) \ge e^{-\varepsilon}\bigl(R(A)-\delta\bigr)$ , where $Q$ is the distribution over the simulator outputs and $R$ is the view of the (real) prover-verifier interaction. At logarithmic leakage, this guarantees at least inverse-polynomial accepting probability. A polynomial-time procedure can therefore repeatedly run the simulator and obtain an accepting conversation with very high probability.

But an accepting conversation might have been assembled using correlations that a real prover could not create. For example, an early answer correlated with a verifier’s (still-hidden) future randomness. So, finding accepting transcripts therefore does not lead to soundness. We addresses this via a causality constraint using a simulation-based prover and relative entropy. On yes-instances, symmetric multiplicative simulation leads to a logarithmic relative-entropy bound (after suitable regularization). On no-instances, an efficiently sampled distribution that accepts often must be much farther, in relative entropy, from the corresponding genuine online prover’s view, because soundness forces that prover to accept only negligibly often. Then an entropy-chain-rule identity translates this gap into instances of Entropy Difference, while Statistical Difference handles insufficient accepting mass. These are both SZK-complete problems, giving the desired reduction.

Beyond logarithmic leakage

In our paper, we give several ways in which larger leakage budgets permit greater computational power. Some are unconditional class characterizations; some require complexity assumptions; others establish separations in oracle settings.

SAT at linear leakage: an (intentionally) revealing protocol

The SAT problem (which we study in CS/ECE 374 at UIUC!) is about whether a Boolean formula has a satisfying assignment. Let the formula have encoding length $n$ and $m\le n$ variables. Fix a satisfying assignment $w$ . Consider the following prover:

With probability $1-2^{-n}$ , send $w$ . With probability $2^{-n}$ , send a uniformly random $m$ -bit assignment.

The verifier checks whether the received assignment satisfies the formula. The simulator simply sends a uniformly random assignment every time. Writing $\eta=2^{-n}$ , the message distributions are $R_w(y) = (1-\eta)\mathbf 1[y=w]+\eta 2^{-m}, Q(y)=2^{-m}.$ At the satisfying assignment, the ratio $R_w(y)/Q(y)$ is at most $2^m\le 2^n$ . Away from it, the reverse ratio is exactly $1/\eta=2^n$. Consequently, both multiplicative inequalities hold with $\varepsilon=n\ln 2, \delta=0.$

The protocol has perfect soundness and completeness error at most $2^{-n}$ . Because the proof consists of one prover message, the same multiplicative bounds extend to an arbitrary efficient verifier’s entire view by randomized post-processing. Thus, $\mathrm{SAT}\in\mathrm{MZK}[n\ln 2,0].$ It is known that, unless the polynomial hierarchy collapses to its second level, SAT does not belong to SZK. This gives a conditional separation between linear-leakage MZK and SZK.

A remark about privacy: This protocol reveals a satisfying assignment with overwhelming probability. It is clearly not private in the ordinary sense one would want for a credential or confidential computation. It satisfies MZK because the allowed multiplicative factor is enormous! The rare random branch does the following: it gives the real distribution positive probability wherever the simulator has positive probability. Without it, the simulator could output assignments that the real prover never sends, making pure symmetric multiplicative simulation impossible.

Polylogarithmic leakage: conditional separations much closer to the boundary

An interesting regime lies between logarithmic and polynomial leakage.

For fixed integers $j\ge1$ , define $\mathcal M_j = \mathrm{MZK}[O((\log n)^j)].$ We show that $\mathrm{SZK}=\mathcal M_1 \subseteq \mathcal M_2 \subseteq \mathcal M_3 \subseteq\cdots.$ That is, for every $\mathcal M_j$ with $j\ge2$ strictly contains SZK under a specific nonuniform circuit hardness assumption: some fixed-width DNF tautology problem has no subexponential-size nondeterministic circuits. This assumption follows from a nonuniform nondeterministic version of the Strong Exponential Time Hypothesis.

Two things to note: (i) the argument does not use ordinary uniform SETH, and (ii) the result separates each higher level from SZK; it does not prove that successive levels differ from one another.

Oracle separations in a black-box setting

We prove a separation for every polynomial-time computable, polynomially bounded superlogarithmic integer profile $\ell(n)$ . For each such profile, there is an oracle $A$ and a language that belongs to $\mathrm{MZK}^{A}[(\ell(n)-1)\ln 2,0]$ but not even to quantum statistical zero-knowledge relative to that oracle. This covers profiles as close to logarithmic as $\log n\log\log n$ , as well as $(\log n)^2$ . An oracle is an idealized black box available to the algorithms under comparison. Such a separation is not an unconditional separation of the ordinary classes. The implication here is that the equality of SZK to MZK, under logarithmic leakage, cannot be extended to all larger budgets.

The appearance of quantum SZK strengthens the oracle result: even allowing quantum statistical-zero-knowledge (larger than SZK) protocols does not eliminate the separation in the constructed setting.

At polynomial leakage, MZK recovers all interactive proofs

Another result is that $\boxed{ \mathrm{MZK}[\mathrm{poly}] = \mathrm{HVMZK}[\mathrm{poly}] = \mathrm{PSPACE}. }$

Here, “poly” means the union over polynomial leakage bounds. The equality holds even with zero additive simulation error. PSPACE consists of problems solvable using polynomially bounded memory, potentially with much greater running time! A result of Shamir shows that $\mathrm{IP}=\mathrm{PSPACE}$ ; so PSPACE consists of exactly the problems admitting polynomial-time verifier interactive proofs. Our result, therefore, implies that sufficiently large multiplicative leakage removes the language class restriction imposed by statistical zero-knowledge. The construction, for this result, generalizes the SAT example. Take an interactive proof and modify its prover: almost always follow the original strategy, but on a negligible-probability branch send uniformly random replies. The simulator always uses uniform replies.

If the prover sends at most $b(n)$ bits and the rare branch has probability $2^{-h(n)}$ , the resulting leakage is bounded by $\varepsilon(n) = \ln 2\cdot\max\{b(n),h(n)\}.$ Choosing polynomially bounded parameters with negligible branch probability preserves negligible completeness error and leaves soundness unchanged. Once again, this is a characterization of computational power. Do not use polynomial leakage for actual applications.

What remains open?

How sharp is the separation without oracles or computational (nonuniform SETH) assumptions?

Can one prove an unconditional, unrelativized separation at polylogarithmic leakage? Can the conditional results be obtained from weaker or more familiar assumptions? And what is the right characterization of intermediate profiles such as $\log n\log\log n$ in the ordinary, non-oracle setting?

Is there a strict hierarchy of leakage levels?

In our paper, we give an increasing sequence $\mathrm{SZK}=\mathcal M_1 \subseteq\mathcal M_2 \subseteq\mathcal M_3 \subseteq\cdots,$ but we do not give a result for whether each successive inclusion is strict. Perhaps additional leakage repeatedly increases computational power. Perhaps several intermediate levels coincide.

Can intermediate MZK have a natural complete problem?

In my opinion, SZK benefits enormously from Statistical Difference: a complete problem stated simply in terms of two efficiently samplable distributions. Can a similarly clean problem characterize intermediate-leakage MZK?

What are the best efficiency gains within the SZK regime?

For a given task, how much communication can constant or logarithmic multiplicative leakage save? Which savings survive arbitrary redesign of the statistical protocol? Can a conversion to SZK preserve useful bounds on total communication, rounds, or prover computation?

The distributed separation shows that communication savings can be fundamental in an appropriately specific model. Our logarithmic collapse result shows that those savings need not lead to an enlargement of the corresponding public-input proof class. Essentially, can we turn our complexity-theoretic results into useful protocol-design guidance?

References

[1] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive
proof systems. SIAM Journal on Computing, 18(1):186–208, 1989.

[2] Oded Goldreich, Silvio Micali, and Avi Wigderson. How to prove all NP statements in
zero-knowledge and a methodology of cryptographic protocol design (extended abstract). CRYPTO’ 86.

[3] Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity
or all languages in np have zero-knowledge proof systems. J. ACM, 38(3):690–728, July 1991.

[4] Amit Sahai and Salil P. Vadhan. A complete problem for statistical zero knowledge. Journal
of the ACM, 50(2):196–249, March 2003.

[5] Daniel Alabi, Marshall Ball. On the Complexity of Statistical and Multiplicative Zero-Knowledge. Cryptology {ePrint} Archive, Paper 2026/2104. https://eprint.iacr.org/2026/2104

What Does a Diffusion Model Remember?

tl;dr My graduate student (Tue Do) has developed DIME, an efficient membership test based on the theory of the exact optimal denoiser for diffusion models. DIME gives some impressive results: across a range of datasets, DIME consistently outperforms prior attacks at comparable or substantially lower query cost, improving certain metrics by up to 3×; remarkably, its two-query variant can outperform existing 30-query baselines. Check it out!

Diffusion models have become one of the dominant approaches to generative modeling because they can produce remarkably high-quality outputs while remaining relatively stable to train. They underpin many modern image generation and editing systems (e.g., Stable Diffusion, Midjourney, DALL-E, etc.), and related diffusion techniques have also been applied to video, audio, scientific data, inverse problems, and other modalities. Their success comes from a simple but powerful training objective: a model learns to reverse a gradual noising process, transforming corrupted data back toward samples that resemble the training distribution. This denoising formulation scales well to high-dimensional data and gives practitioners considerable control over generation, including conditioning on text, class labels, or other signals.

The widespread use of diffusion models also makes it important to understand what they learn about their training data, not just how good their generated samples look. State-of-the-art models are often trained on enormous collections of images gathered from the web or from sensitive domains such as medicine, biometrics, and personal photography. A model that behaves well at generation may nevertheless retain information about particular training examples. This raises questions about privacy, memorization, copyright, data provenance, and whether a person’s data has actually been removed after a deletion or machine-unlearning request. Membership inference, the problem of determining whether a particular record was used during training, is therefore a useful way to probe the boundary between learning general statistical structure and retaining example-specific information.

Diffusion models are especially interesting from a privacy perspective because their core denoising task is closely related to reconstruction. Given a corrupted input, the model repeatedly estimates information needed to move that input back toward likely clean data. If the model has learned unusually detailed information about a particular training example, its denoising behavior near that example may differ from its behavior near unseen data. Studying these differences helps us understand where memorization lives inside a diffusion model and how it can be detected. This is valuable both offensively, for developing stronger privacy audits, and defensively, for evaluating whether techniques such as differential privacy, deduplication, or regularization actually prevent training examples from leaving detectable traces.

There’s the diffusion model training question: Given a noisy version of an image, what noise was added, or equivalently, what clean image should the model reconstruct? And the membership inference question: Given a candidate image, was this image part of the model’s training set?

In DIME, we exploit the fact that these two questions are, in fact, tightly connected. A perfectly trained diffusion denoiser does not merely learn a generic rule for “what noise looks like.” On a finite training set, its optimal prediction can be written exactly as a posterior-weighted combination of the training examples. The model is therefore carrying out a kind of soft retrieval: given a noisy input, it asks which training points could plausibly have generated it and blends those points according to their posterior responsibilities.

That observation turns membership inference from a search for ad hoc statistics into a derivation. The model’s implicit reconstruction of a candidate has an exact squared error, and that error splits into two terms:

Reconstruction bias: how far the local posterior mean is from the candidate; and
Local crowding: how dispersed the plausible training points are around that mean.

The first signal resembles what earlier norm and reconstruction-based attacks measure. The second is the new ingredient: a non-member can be reconstructed surprisingly well simply because it lies near the center of several training points. Bias alone can therefore be fooled by local geometry, while crowding exposes the ambiguity.

Both signals can be estimated from forward queries to the denoising network. They share the same randomly perturbed queries, so the attack needs only a few model evaluations and its cheapest setting uses just two total queries. In experiments on CIFAR-10, CIFAR-100, STL10-U, CelebA, and ImageNet, DIME improves the low-false-positive detection rate substantially, sometimes beating 30-query baselines with only two queries. We also test the attack against differentially private mechanisms and finds that differentially private training drives DIME and the evaluated baselines back toward chance.

A minimal diffusion refresher

Let the finite training set be

$\displaystyle \mathcal D_{\mathrm{train}}=\{x_1,\ldots,x_n\}\subseteq\mathbb R^d.$

At timestep $t$ , the forward process forms

$\displaystyle g=\sqrt{\bar\alpha_t}\,x+\sigma_t z, \qquad z\sim\mathcal N(0,I_d), \qquad \sigma_t=\sqrt{1-\bar\alpha_t}.$

The noise-prediction network is trained by mean squared error:

$\displaystyle \mathcal L_t(\theta) = \mathbb E_{x\leftarrow\mathcal D_{\mathrm{train}},\,z\sim\mathcal N(0,I_d)} \left[ \left\| \widehat\varepsilon_\theta(\sqrt{\bar\alpha_t}x+\sigma_tz,t)-z \right\|_2^2 \right].$

For squared loss, the population-optimal prediction is a conditional expectation. Here, because the data distribution is the empirical distribution over a finite training set, that conditional expectation can be calculated explicitly.

The first main result: the exact finite-set optimal denoiser

For a query $g$ , define the unnormalized compatibility of training point $x_i$ by

$\displaystyle s_i(g) = \exp\!\left( -\frac{\|g-\sqrt{\bar\alpha_t}x_i\|_2^2}{2\sigma_t^2} \right),$

and normalize these scores into responsibilities

$\displaystyle r_i(g)=\frac{s_i(g)}{\sum_{j=1}^n s_j(g)}.$

We prove that the MSE-optimal denoiser is

$\displaystyle \boxed{ \widehat\varepsilon^*(g,t) = \frac{g}{\sigma_t} - \frac{\sqrt{\bar\alpha_t}}{\sigma_t} \sum_{i=1}^n r_i(g)x_i. }$

This formula has a simple Bayesian derivation. If training point $x_i$ generated $g$ , the corresponding noise would be

$\displaystyle z_i=\frac{g-\sqrt{\bar\alpha_t}x_i}{\sigma_t}.$

Conditioned on seeing $g$ , the posterior probability that the latent training index was $i$ is precisely $r_i(g)$ . The optimal squared-loss estimate is therefore

$\displaystyle \mathbb E[z\mid g] = \sum_i r_i(g)z_i,$

which expands to the boxed expression.

The denoiser is a soft decoder over the training set

The weighted point

$\displaystyle m(g)=\sum_i r_i(g)x_i$

is the model’s implicit reconstruction of the clean training example that could have produced $g$ . Training examples close to $g/\sqrt{\bar\alpha_t}$ receive exponentially larger responsibility. The noise scale $\sigma_t$ acts like a temperature:

at high noise, many records can plausibly explain the query, so responsibilities are diffuse;
at low noise, the posterior sharpens around the closest training record.

As $\sigma_t\to0$ , the soft responsibilities converge almost everywhere to the indicator of the nearest training point’s Voronoi cell. In other words, the ideal denoiser approaches a hard nearest-neighbor decoder.

This explains why membership leakage is strongest in the low-noise regime. For a member $x^*=x_i$ , the nearest point is the record itself, so the posterior can concentrate on $x_i$ . For a non-member, the best the empirical model can do is retrieve or blend nearby training points.

Why reconstruction bias alone is not enough

The obvious attack would compare the model’s implicit reconstruction with the candidate. A member should reconstruct accurately; a non-member should not. This intuition is useful but incomplete.

A non-member can have small reconstruction bias when it lies near the mean of several training points; the dispersion of those points (the crowding term) distinguishes it from an isolated member.

We separate three cases.

Case A: isolated member

The candidate is itself a training point and has no close competitors. Responsibility concentrates on the candidate. The posterior mean is close to $x^*$ , and the responsible neighborhood has almost no spread. Both bias and crowding are small.

Case B: isolated non-member

The closest training point or cluster lies away from the candidate. The posterior mean is displaced from $x^*$ . Bias is large, even if the nearby training points are tightly grouped.

Case C: crowded non-member

The candidate lies near the center of several training points. Their weighted mean can accidentally be close to $x^*$ , producing small bias. But responsibility is divided among separated records, so the local variance is large.

The one-dimensional example $\mathcal D=\{-1,+1\}$ and $x^*=0$ makes the blind spot exact. If the two records have equal responsibility, the posterior mean is zero, so reconstruction bias is zero even though zero is not in the training set. The variance is one, correctly signaling ambiguity.

What the score distributions and timestep plots show

DIME score distributions from the paper.

Member and held-out DIME score distributions are visibly separated across the five checkpoints; dashed lines show calibrated thresholds.

The distribution plots make the aggregate metrics easier to interpret. DIME is not succeeding because of a handful of extreme outliers; the member and non-member score distributions shift relative to one another across every tested checkpoint. The amount of overlap explains why STL10-U permits near-total detection while CelebA remains harder.

The four smaller DDPM checkpoints remain effective across a broad timestep range, whereas ImageNet Guided Diffusion is most vulnerable at early timesteps.

The ideal denoiser theory predicts stronger concentration at lower noise. Guided Diffusion follows that prediction clearly: attack performance is highest at early timesteps and declines as noise increases. The smaller DDPM checkpoints exhibit a broad plateau instead. This suggests that the roughly 550M-parameter Guided Diffusion model may approximate the ideal denoiser more faithfully than the roughly 35M-parameter DDPM models. This is a plausible interpretation of the observed scale difference, not a formal proof that parameter count is the cause.

An additional practical lesson is that exact timestep selection may not be fragile for the smaller checkpoints. A broad plateau gives an attacker or auditor some tolerance to imperfect calibration.

Synthetic experiments isolate the role of crowding

The real-network experiments inevitably mix two phenomena:

properties of the exact finite-set optimal denoiser; and
approximation and optimization behavior of the trained neural network.

The synthetic appendix removes the second factor by evaluating the closed-form denoiser directly on small, known training sets.

Synthetic bias and variance decomposition from the paper.

The crowded non-member can have relatively small bias, but its variance rises much earlier and separates it from the member.

The left panel shows why a bias-only attack can fail: the crowded non-member’s posterior mean can remain close to the candidate. The middle panel shows the missing signal: responsibility spread creates a nonzero variance well before the member’s variance grows. Their sum in the right panel recovers the intended reconstruction error.

Further synthetic experiments compare DIME with SimA-MC while varying dataset size, noise level, and query count. They show that the extra crowding signal makes DIME’s membership performance decay more slowly as noise increases. These experiments are diagnostic rather than a substitute for the neural-network results, but they confirm that the claimed effect exists in the exact theoretical object itself.

Conclusion

DIME’s central insight can be stated as follows:

A finite-set diffusion denoiser implicitly performs soft retrieval over its training examples, and the error of that retrieval contains both a reconstruction signal and a geometric crowding signal.

We turn this insight into an exact formula, decompose the corresponding error, link hidden local covariance to the denoiser’s Jacobian, and estimate both terms with $q+1$ forward queries. The resulting attack is not merely more accurate in aggregate; its largest gains occur at the low-false-positive operating point that matters most for credible membership decisions. It also survives a dramatic jump from small unconditional DDPMs to a large class-conditional ImageNet model.

Moreover, the defenses we apply are reassuring: differential privacy suppresses not only earlier heuristic attacks but also the stronger signal produced by the ideal denoiser derivation. The broader message is therefore balanced: Diffusion models can leak membership through richer local geometry than prior attacks measured, but formal stability remains a meaningful line of defense.

DIME provides both a practical attack and a new lens for future work: privacy leakage in diffusion models can be studied as the geometry of a soft decoder over a finite codebook.

References

Tue Do and Daniel Alabi, “DIME: Query-Efficient Framework for Membership Inference on Diffusion Models”, arXiv:2608.22824, 2026.