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:

1. Correctness: $(U’,V’)$ is close (in statistical distance) to $(U,V)$.
2. 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$.
3. 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:

1. $D$ has a perfect non-secure non-interactive reduction from $C$, but
2. $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.