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

The Existence of Error-Correcting Codes Implies Privacy Lower Bounds

Excited to share this recent IEEE BITS article in the Special Issue on Error-Correcting Codes [1].

Abstract

We discuss how the lens of error-correcting codes yields lower bounds on the privacy-utility tradeoff in differential privacy (DP). Reconstruction attacks, packing and covering arguments, and fingerprinting codes can all be interpreted as coding-theoretic tools: they allow for analysis of families of datasets whose query-answer patterns form (possibly randomized) codewords with large pairwise distance. Any DP mechanism answering these queries too accurately reveals enough structure to enable “decoding”; that is, identifying a user or reconstructing large parts of the dataset. By presenting each lower-bound technique through an explicit coding viewpoint, this survey unifies classical results on counting queries with recent advances in statistical estimation and high-dimensional learning, including Gaussian covariance estimation. We conclude with open problems at the intersection of coding theory and differential privacy.

[1] https://ieeexplore.ieee.org/document/11481645

Secure Non-Interactive Reductions

A recurring theme in cryptography is that correlation is a resource. Alice and Bob may start with a source correlation $C$ , say noisy copies of a bit or erasures. The hope is to convert it into a more useful target correlation $D$ . What changes dramatically is whether they are allowed to talk, and whether we only care about correctness or also about security. The recent SNIR/SNIS line of work makes that distinction precise and surprisingly rigid.

This post explains that landscape in a way I hope is useful. The main message/tl;dr is:

ordinary non-secure non-interactive reductions ask only whether local maps can reproduce the right joint law;
secure non-interactive reductions ask for that plus privacy against each party;
interactive reductions are much more powerful because communication can reshape the parties’ views before the final local-output step.

Recently, I have also been working with colleagues in ECE and Physics on quantum secure non-interactive reductions, which aim to understand when one quantum correlation resource can be transformed into another quantum (or classical) resource without communication and while preserving the appropriate notion of security against each party. In the quantum setting, the picture is even more delicate: the relevant resources may be shared quantum states, measurements may disturb systems, side information may be entangled, and the right privacy conditions must account for quantum adversaries and quantum views rather than just classical random variables. Our framework for thinking about that problem relies heavily on the formalization of the classical or non-quantum version, which is the subject of this post. Put differently, before asking what secure non-interactive reducibility should mean for shared entangled states or quantum correlations, it is essential to first understand the classical theory: what ordinary non-interactive reductions allow, what secure non-interactive reductions forbid, and why interaction fundamentally changes the reducibility landscape. I will also prove a simple lemma showing that secure non-interactive reducibility is strictly stronger than ordinary non-interactive reducibility.

The three models

Fix a source correlation $C=(X,Y)$ and a target correlation $D=(U,V)$ .

Non-secure non-interactive reduction (NIR / NIS)

Alice gets $X^n$ , Bob gets $Y^n$ , they do no communication, and output $U’ = f(X^n), V’ = g(Y^n)$ , or randomized versions using local coins. The goal is for $(U, V)$ to be close in statistical distance (or total variation distance) to $(U’, V’)$ .

That is the classical non-interactive simulation perspective: only correctness of the output law matters. The SNIS paper explicitly contrasts this with SNIS, noting that NIS “only considers correctness (not security).”

Secure non-interactive reduction (SNIR / SNIS)

Now Alice and Bob still do not communicate, but in addition to correctness, the reduction must hide whatever the target correlation is supposed to hide. In the formulation used in the SNIS paper, a reduction from $(U,V)$ to $(X,Y)^{\otimes n}$ must satisfy:

Correctness: $(U’,V’)$ is close (in statistical distance) to $(U,V)$ .
Security against corrupt Alice: conditioned on the final outputs $(u,v)$ , Alice’s view should be close to depending only on $u$ , not on the extra value $v$ .
Security against corrupt Bob: symmetrically, Bob’s view should be close to depending only on $v$ , not on the extra value $u$ .

This is the key strengthening. In NIR, a party may silently carry “too much knowledge” about the other party’s output, as long as the final joint distribution looks right. In SNIR, that is disallowed.

Interactive secure reductions

Here Alice and Bob may exchange messages before producing outputs. An interactive secure reduction can be seen as having two phases. First, an interaction phase transforms the parties’ views. Second, a local derivation phase maps those final views to outputs, and the security condition applies to this derivation step.

That decomposition is conceptually important: SNIR isolates the “final local secure derivation” part while forbidding the interaction that might create the right intermediate views in the first place. This is why interactive reductions can be much stronger.

Why SNIR is the right cryptographic strengthening

NIR asks “can I simulate the right distribution?”
SNIR asks “can I simulate the right distribution without the wrong leakage?”

The SNIS paper states this very plainly: in NIS, “erasing information from parties’ views… is permissible,” but that may not be cryptographically secure. SNIS was introduced precisely to capture non-interactive secure conversion of one correlation into another. This matters because many correlations that are “equivalent enough” from a purely distributional viewpoint stop being interchangeable once one insists on simulation-based privacy.

SNIR is strictly stronger than non-secure NIR

Here is a simple lemma/example that captures the basic separation.

Lemma/example

There exist correlations $C$ and $D$ such that:

$D$ has a perfect non-secure non-interactive reduction from $C$ , but
$D$ has no perfect secure non-interactive reduction from $C$ .

Proof

Let $S,T$ be independent uniform bits.

Define the source correlation $C = ((S,T),\, T).$

So Alice receives the pair $(S,T)$ , while Bob receives only $T$ .

Define the target correlation $D = (S,T).$

Step 1: There is a perfect non-secure non-interactive reduction

Alice outputs $U’ := S,$

and Bob outputs $V’ := T.$

No communication is used. Since $S,T$ are independent uniform bits, the joint distribution of $(U’,V’)$ is exactly $(S,T)$ , which is exactly the target correlation $D$ .

So $D$ has a perfect NIR from $C$ .

Step 2: There is no perfect secure non-interactive reduction

Assume for contradiction that the above source-to-target conversion were a perfect SNIR.

In the target correlation $D=(S,T)$ , Alice’s output is $U=S$ and Bob’s output is $V=T$ . Since $S$ and $T$ are independent, a correct secure realization of $D$ should not let Alice’s view reveal Bob’s output $T$ beyond what is implied by her own output $S$ .

But in the source $C$ , Alice’s view is $X=(S,T).$

Conditioned on the target outputs $(U,V)=(s,t)$ , Alice’s view is deterministically $X=(s,t).$

Hence the conditional law of Alice’s view depends on $t$ . i.e., on Bob’s output $V$ , not merely on Alice’s own output $U=s$ .

This violates the security-against-Alice requirement for SNIR.

Therefore no perfect SNIR from $C$ to $D$ exists.

What this lemma implies

This toy example is simple, but it isolates the exact distinction.

In NIR, it is fine that Alice initially knows both $S$ and $T$ ; all we asked for was the right final law.
In SNIR, that extra knowledge is fatal, because Alice learns Bob’s target output in a way the target correlation itself does not permit.

Ordinary non-interactive reduction

“Can I locally compress, discard, relabel, or threshold my view so that the joint output law matches the target?”

This is fundamentally an information-theoretic simulation question.

Secure non-interactive reduction

“Can I do that without retaining forbidden side information about the other party’s target output?”

This is a simulation-based-privacy question.

Interactive reduction

“Can I first reengineer the two views using communication, and only then derive the target securely?”

This is why interaction is stronger.

References

[1] Agarwal, Narayanan, Pathak, Prabhakaran, Prabhakaran, Rehan, “Secure Non-Interactive Reduction and Spectral Analysis of Correlations” (Eurocrypt 2022 / ePrint 2022/262), especially the spectral criterion, mirroring perspective, and incompleteness results.

[2] Bhushan, Misra, Narayanan, Prabhakaran, “Secure Non-Interactive Reducibility is Decidable” (TCC 2022 / ePrint 2022/1457), for decidability of SNIR feasibility.

[3] Khorasgani, Maji, Nguyen, “Secure Non-interactive Simulation: Feasibility and Rate” (Eurocrypt 2022), for the simulation-based definition, comparison with NIS and OWSC, and exact rate/feasibility characterizations for BSS/BES families.