Composition of Privacy Guarantees: Classical and Quantum

I try to always consider the classical alternative to any quantum computation or quantum information-theoretic primitive. This is a deliberate choice. I am not a pure quantum theorist in the sense of studying quantum models in isolation, nor am I interested in quantum advantage as an article of faith. Rather, my goal is to delineate (as precisely as possible) the boundary between what classical and quantum theories can guarantee, especially when privacy guarantees are composed over time, across mechanisms, or between interacting systems.

In the context of privacy, composition is where theory meets reality: real systems are never single-shot. They involve repeated interactions, adaptive adversaries, and layered mechanisms. Quantum information introduces new phenomena (entanglement, non-commutativity, and measurement disturbance) that complicate classical intuitions about composition. At the same time, classical privacy theory has developed remarkably robust tools that often remain surprisingly competitive, even when quantum resources are allowed.

The guiding question of this post is therefore not “What can quantum systems do that classical ones cannot?” but rather:

When privacy guarantees are composed, what genuinely changes in the transition from classical to quantum. And what does not?

By keeping classical alternatives explicitly in view, we can better understand which privacy phenomena are inherently quantum, which are artifacts of modeling choices, and which reflect deeper structural principles that transcend the classical vs. quantum divide.

Classical Composition of Differential Privacy

Recall the definition of differential privacy:

Approximate Differential Privacy
Let $\mathcal{X}$ denote the data universe and let $\mathcal{D} \subseteq \mathcal{X}^n$ be the set of datasets.
Two datasets $D,D'\in\mathcal{D}$ are called neighbors, denoted $D\sim D'$ , if they differ in the data of exactly one individual.

A (possibly randomized) algorithm $\mathcal{M} : \mathcal{D} \to (\mathcal{Y},\mathcal{F})$ is said to be
$(\varepsilon,\delta)$ -differentially private if for all neighboring datasets $D\sim D'$ and all measurable events
$S \in \mathcal{F}$ ,
$\Pr[\mathcal{M}(D)\in S] \;\le\; e^{\varepsilon}\Pr[\mathcal{M}(D')\in S] + \delta$ .

It has been shown in a few references/textbooks that basic composition holds for differential privacy. We recall the statement:

Theorem (Basic sequential composition for approximate differential privacy)
Fix $k\in\mathbb{N}$ . For each $i\in\{1,\ldots,k\}$ let $\mathcal{M}_i$ be a (possibly randomized) algorithm that, on input a dataset $D$ , outputs a random variable in some measurable output space $(\mathcal{Y}_i,\mathcal{F}_i)$ .
Assume that for every $i$ , $\mathcal{M}_i$ is $(\varepsilon_i,\delta_i)$ -differentially private.

Define the $k$ -round interactive (sequential) mechanism $\mathcal{M}$ as follows: on input $D$ , for $i=1,\ldots,k$ , it outputs $Y_i \leftarrow \mathcal{M}_i (D; Y_1,\ldots,Y_{i-1}),$
where $\mathcal{M}_i(\cdot; y_{<i})$ denotes the $i$ th mechanism possibly chosen adaptively as a (measurable) function of the past transcript $y_{<i}=(y_1,\ldots,y_{i-1})$ .
Let $Y=(Y_1,\ldots,Y_k)$ denote the full transcript in the product space
$(\mathcal{Y},\mathcal{F}) := \prod_{i=1}^k (\mathcal{Y}_i,\mathcal{F}_i)$ .

Then $\mathcal{M}$ is $\left(\sum_{i=1}^k \varepsilon_i,\ \sum_{i=1}^k \delta_i\right)$ -differentially private.

In particular, if $\varepsilon_i=\varepsilon$ and $\delta_i=\delta$ for all $i$ , then $\mathcal{M}$ is $(k\varepsilon, k\delta)$ -differentially private.

What happens in the quantum setting?

Composition of Quantum Differential Privacy

A central “classical DP intuition” we have already set up is: once you have per-step privacy bounds, you can stack them, and in the simplest form the parameters add. e.g., $(\varepsilon, \delta)$ adds across rounds. In the quantum world, however, DP is commonly defined operationally against arbitrary measurements; and this makes the usual classical composition proofs, which rely on a scalar privacy-loss random variable, no longer directly applicable.

In a recent work, Theshani Nuradha and I show two complementary points, one negative (a barrier) and one positive:

Composition can fail in full generality for approximate QDP (POVM-based).
We show that if you allow correlated joint implementations when combining mechanisms/channels, then “classical-style” composition need not hold: even channels that are “individually perfectly private” can lose privacy drastically when composed in this fully general way.
Composition can be restored under explicit structural assumptions.
Then we identify a regime where you can recover clean composition statements: tensor-product channels acting on product neighboring inputs. In that regime, we propose a quantum moments accountant built from an operator-valued notion of privacy loss and a matrix moment-generating function (MGF).
How we get operational guarantees (despite a key obstacle).
A subtlety we highlight: the Rényi-type divergence we consider for the moments accountant does not satisfy a data-processing inequality. Nevertheless, we prove that controlling appropriate moments is still enough to upper bound measured Rényi divergence, which does correspond to operational privacy against arbitrary measurements.
End result: advanced-composition-style behavior (in the right setting).
Under those structural assumptions, the paper obtains advanced-composition-style bounds with the same leading-order behavior as in classical DP. i.e., you can once again reason modularly about long pipelines, but only after carefully stating what “composition” means (i.e., joint, tensor-product, factorized) physically/operationally in the quantum setting.

Check out the paper. Feedback/comments are welcome!

Statistical Zero-Knowledge Proofs

How would you prove you’ve solved a Sudoku puzzle without revealing the solution? You can construct a zero-knowledge proof showing the grid satisfies Sudoku rules (unique numbers per row, column, and box).

This semester, one of my projects involves zero-knowledge proofs. I’ll try to explain what I’ve learned about this amazing concept and its variants (with particular attention to statistical zero-knowledge). Shout out to Boaz’s cryptography class. Zero-knowledge proofs have found profound use in blockchain technology, authentication, privacy, and so on.

Definition

Intuition: Imagine someone wants to prove they know the solution to a complex problem (e.g., a puzzle or how Trump was going to win the election) without revealing the solution. They use a process that convinces the verifier they have the solution without showing it.

A zero-knowledge proof (ZKP) is a method by which one party (the prover) can demonstrate to another party (the verifier) that a specific statement is true without revealing any additional information about the statement itself.

Key Properties of Zero-Knowledge Proofs

There are a few variants of zero-knowledge. Here is one:

Completeness:
If the statement is true, a honest prover can convince the verifier of its truth:
- If $x \in L$ and the prover $P$ knows a valid witness $w$ , then for all $\epsilon > 0$ , the honest verifier $V$ will accept the proof with probability at least $1 - \epsilon$ : $\Pr[V(x) = \text{accept} \mid x \in L, w \text{ valid}] \geq 1 - \epsilon.$
Soundness:
If the statement is false, no dishonest prover can convince the verifier that it is true (except with an extremely small probability).
- If $x \not\in L$ , then no cheating prover $P^*$ can convince the honest verifier $V$ to accept, except with negligible probability: $\Pr[V(x) = \text{accept} \mid x \not\in L] \leq \epsilon$ where $\epsilon$ is a negligible function.,
Zero-Knowledge:
The verifier learns nothing other than the fact that the statement is true. No information about how or why the statement is true is revealed.
- For every polynomial-time verifier $V^*$ , there exists a polynomial-time simulator $S$ such that the output of $S(x)$ is computationally indistinguishable from the interaction between $P$ and $V^*$ on input $x$ : ${S(x)}_{x \in L} \approx {\text{Transcript}(P \leftrightarrow V^*, x)}_{x \in L}.$

Type	Definition	Guarantee
Perfect Zero-Knowledge	Real and simulated distributions are identical.	Holds even against computationally unbounded verifiers.
Statistical Zero-Knowledge	Real and simulated distributions are statistically close (negligible difference).	Holds against computationally unbounded verifiers.
Computational Zero-Knowledge	Real and simulated distributions are computationally indistinguishable for polynomial-time verifiers.	Holds only against computationally bounded verifiers.

Interactive Zero-Knowledge Proofs

These involve a back-and-forth interaction between the prover and the verifier.

Graph Isomorphism:
Prove that two graphs are isomorphic (structurally identical) without revealing the isomorphism itself. Alice proves to Bob that she knows a way to relabel the nodes of graph $A$ to match graph $B$ .
Hamiltonian Cycle Problem:
Prove that a graph contains a Hamiltonian cycle (a path visiting every vertex exactly once) without revealing the actual cycle.

Non-Interactive Zero-Knowledge Proofs (NIZKs)

These eliminate the need for interaction, enabling the prover to generate a single proof that can be verified multiple times.

zk-SNARKs (Succinct Non-Interactive Arguments of Knowledge):
Widely used in blockchain systems like Zcash to validate transactions while keeping them private. Example: Prove that a transaction is valid (inputs equal outputs) without disclosing amounts or participants.
zk-STARKs (Scalable Transparent Arguments of Knowledge):
A transparent alternative to zk-SNARKs that avoids the need for trusted setups and is more scalable. Example: Used in Ethereum Layer-2 solutions like StarkNet to bundle transaction proofs.

The Fiat-Shamir Heuristic technique to convert interactive proofs into non-interactive ones using cryptographic hash functions.

Schnorr Protocol:
A proof that you know a discrete logarithm of a number without revealing the logarithm itself. Example: Prove ownership of a private key without exposing it (used in Schnorr signatures).

Example Use Cases

Zero-knowledge proofs (ZKPs) come in different forms, with specific examples being applied across theoretical and practical scenarios. Below are some notable examples:

1. Commit-and-Prove Protocols

Combine commitments (binding and hiding data) with zero-knowledge proofs (for example Pedersen Commitments). Prove that you committed to a number $x$ without revealing $x$ but can later open the commitment to verify $x$ .

2. Bulletproofs

Efficient range proofs that demonstrate a value lies within a specific range without revealing the value. Example: Used in Monero to ensure transaction amounts are positive without disclosing the actual amounts.

3. Proofs in Cloud Computing

Proof of Retrievability:
Prove a cloud provider stores your data without downloading it. Example: Used in decentralized storage systems like Filecoin.
Proof of Computation:
Demonstrate the correctness of outsourced computation without revealing inputs or outputs.

4. Secure Voting Protocols

Homomorphic Encryption-Based Proofs:
Prove a vote is valid (e.g., within a candidate set) without revealing the voter’s choice.

5. Knowledge of a Password

Example: Authenticate to a server by proving knowledge of a password without transmitting it. SRP Protocol (Secure Remote Password): Verifies a user knows a password without sending the password itself.

Perfect Zero-Knowledge

Perfect Zero-Knowledge is a stronger version of zero-knowledge where the verifier cannot distinguish between the interaction with the actual prover and the simulated interaction, even with unlimited computational power. In other words, the simulator’s output is statistically identical to the real interaction transcript, not just computationally indistinguishable.

Formal Definition

Let $(P, V)$ be a proof system for a language $L$ . The proof system is perfect zero-knowledge if for every polynomial-time verifier $V^*$ , there exists a probabilistic polynomial-time simulator $S$ such that for every $x\in L$ : $\Pr[\text{Transcript}(P\leftrightarrow V^*,x)=t]= \Pr[S(x)=t]\forall t,$

where:

$\text{Transcript}(P\leftrightarrow V^*,x)$ is the transcript of the interaction between $P$ and $V^*$ on input $x$ ,
$S(x)$ is the simulated transcript generated by $S$ for the same input $x$ .

This implies that the probability distributions of the transcripts from the real interaction and the simulated interaction are exactly the same.

Key Features of Perfect Zero-Knowledge

Statistical Indistinguishability:
The output of the simulator is statistically indistinguishable from the real transcript, meaning the difference between the two distributions is exactly zero.
Stronger Privacy Guarantees:
Since the guarantee holds even against verifiers with infinite computational power, it is stronger than computational zero-knowledge, where the indistinguishability only holds for polynomial-time adversaries.

Example of Perfect Zero-Knowledge

The classic Graph Isomorphism Zero-Knowledge Protocol is a perfect zero-knowledge protocol:

A prover shows two graphs are isomorphic without revealing the actual isomorphism.
The verifier cannot distinguish between a genuine interaction and a simulated one, even with infinite computational power, making it perfect zero-knowledge.

Computational Zero-Knowledge

Computational Zero-Knowledge is a type of zero-knowledge proof where the verifier cannot distinguish between the actual interaction with the prover and the output of a simulator, provided the verifier has limited (polynomial-time) computational power.

This means that the zero-knowledge property relies on the computational infeasibility of distinguishing between the two scenarios, often based on cryptographic hardness assumptions (e.g., the difficulty of factoring large numbers or solving discrete logarithms).

Formal Definition

Let $(P,V)$ be a proof system for a language $L$ . The system is computational zero-knowledge if for every probabilistic polynomial-time (PPT) verifier $V^*$ , there exists a PPT simulator $S$ such that for every $x \in L$ , the distributions: $\text{Transcript}(P \leftrightarrow V^*, x)\}_{x \in L}$ and $\{S(x)\}_{x \in L}$ are computationally indistinguishable. That is, no polynomial-time distinguisher can tell apart the real interaction and the simulated interaction with non-negligible probability.

Key Features of Computational Zero-Knowledge

Computational Indistinguishability:
The zero-knowledge property holds against adversaries with limited computational power (polynomial-time distinguishers). If the verifier were computationally unbounded, they might be able to differentiate the two distributions.
Cryptographic Assumptions:
Computational zero-knowledge often relies on assumptions like:
- The infeasibility of factoring large integers.
- The hardness of the discrete logarithm problem.
- Other complexity-theoretic assumptions.
Relaxed Privacy Guarantees:
Unlike perfect zero-knowledge, where the simulated and real distributions are statistically identical, computational zero-knowledge only guarantees privacy against computationally bounded adversaries.

Examples of Computational Zero-Knowledge

zk-SNARKs:
Used in blockchain protocols like Zcash to ensure transaction validity without revealing sensitive details. The zero-knowledge property here relies on computational assumptions.
Interactive Proofs with Commitment Schemes:
Many zero-knowledge protocols use cryptographic commitments (e.g., Pedersen commitments) to hide information during the proof, ensuring the verifier cannot extract more data computationally.

Real-World Importance

Computational zero-knowledge is widely used in practical applications, such as:

Cryptocurrencies (e.g., Zcash, zkRollups).
Authentication protocols.
Privacy-preserving identity verification.

It strikes a balance between strong privacy guarantees and computational efficiency, making it suitable for real-world cryptographic systems.

Statistical Zero-Knowledge

Statistical Zero-Knowledge (SZK) is a type of zero-knowledge proof where the verifier cannot distinguish between the real interaction with the prover and the output of a simulator, even with unlimited computational power. The key difference from perfect zero-knowledge is that the two distributions (real and simulated) are not identical but are statistically close, meaning the difference between them is negligible.

Formal Definition

Let $(P,V)$ be a proof system for a language $L$ . The system is statistical zero-knowledge if for every probabilistic polynomial-time (PPT) verifier $V^*$ , there exists a PPT simulator $S$ such that for every $x \in L$ , the output distributions: $\text{Transcript}(P \leftrightarrow V^*, x)\}_{x \in L}$ and $\{S(x)\}_{x \in L}$ are statistically indistinguishable. This means the statistical distance (or total variation distance) between the two distributions is negligible:

$\Delta(\text{Transcript}(P \leftrightarrow V^*, x), S(x)) = \frac{1}{2} \sum_t \left| \Pr[\text{Transcript} = t] - \Pr[S(x) = t] \right| \leq \epsilon,$

where $\epsilon$ is a negligible function of the input size.

Key Features of Statistical Zero-Knowledge

Statistical Indistinguishability:
The difference between the real and simulated transcripts is negligibly small, even for verifiers with unlimited computational power.
Weaker than Perfect Zero-Knowledge:
Perfect zero-knowledge requires the distributions to be exactly identical, while statistical zero-knowledge allows for a negligible difference.
Stronger than Computational Zero-Knowledge:
Computational zero-knowledge only guarantees indistinguishability for polynomial-time adversaries, whereas statistical zero-knowledge holds against adversaries with unlimited computational power.
No Dependence on Cryptographic Assumptions:
SZK is typically not reliant on computational hardness assumptions, unlike computational zero-knowledge.

Examples of Statistical Zero-Knowledge

Quadratic Residuosity Problem:
Prove that a number $x$ is a quadratic residue modulo $N$ (a composite number) without revealing the factorization of $N$ . The simulator can generate transcripts statistically indistinguishable from those produced during the real interaction.
Graph Isomorphism Problem:
Prove that two graphs $G_1$ and $G_2$ are isomorphic without revealing the isomorphism. The verifier’s view of the interaction can be statistically simulated.

Real-World Applications

While SZK is less common in practical applications compared to computational zero-knowledge, it has theoretical importance in cryptographic protocol design and scenarios where absolute guarantees against powerful adversaries are required.

Some References

[1] Goldreich, Oded (2001). Foundations of Cryptography Volume I. Cambridge University Press.

[2] Murtagh, Jack. https://www.scientificamerican.com/article/wheres-waldo-how-to-prove-you-found-him-without-revealing-where-he-is/

[3] Goldwasser, S.; Micali, S.; Rackoff, C. (1989), “The knowledge complexity of interactive proof systems” (PDF), SIAM Journal on Computing, 18 (1): 186–208, doi:10.1137/0218012, ISSN 1095-7111

Leftover Hash Lemma

Recently, I’ve been investigating computational notions of entropy and had to use the Leftover Hash Lemma. (A variant of this lemma is stated below) I first encountered the Lemma several years ago but didn’t have to use it for anything… until now!

The lemma is attributed to Impagliazzo, Levin, and Luby [1]. A corollary of the lemma is that one can convert a source of (high-enough) Rényi entropy into a distribution that is uniform (or close to uniform). Before stating the Lemma, I’ll discuss a few different notions of entropy, including the classic Shannon Entropy, min-entropy, max-entropy, and so on. See [2] for many different applications for the entropy measures.

Entropy Measures

Consider the random variable $X$ . We use $x\xleftarrow{R} X$ to denote that the element $x$ is randomly drawn from $X$ . Denote its support by Supp( $X$ ). Define the sample entropy of $x$ with respect to $X$ as $H_X(x) = \log\frac{1}{\mathbb{P}[X=x]}$ . The sample entropy measures how much randomness is present in the sample $x$ when generated according to the law/density-function of $X$ . Also, let $H_X(x) = \infty$ when $x\notin$ Supp( $X$ ). Then we can state the entropy measures in terms of the sample entropy:

Shannon Entropy: $H(X) = \mathbb{E}_{x\xleftarrow{R} X}[H_X(x)]$
Min-Entropy: $H_\infty(X) = \min_{x\in\text{Supp}(X)}H_X(x)$
Rényi Entropy: $H_2(X) = -\log\sum_{x\in\text{Supp}(X)}\mathbb{P}_X(x)^2$
Max-Entropy: $H_0(X) = \log(|\text{Supp}(X)|)$

How should we interpret these measures? The min-entropy can be seen as a worst-case measure of how “random” a random variable is. The Rényi entropy measure, intuitively, measures how “collision-resistant” a random variable is (i.e., think hash functions). In my opinion, max-entropy does not give much information, except for how large the support of a random variable is. These entropy measures are related by this inequality:

$H_\infty(X)\leq H_2(X) \leq H(X) \leq H_0(X)$

The inequality above is tight if and only if $X$ is uniformly distributed on its support. The statement of the lemma below uses universal hash functions. Here is a definition:

A function family $\mathcal{H} = \{h:\mathcal{D}\mapsto\mathcal{R}\}$ is two-universal if $\forall x\neq x'\in\mathcal{D}$ , the following holds: $\mathbb{P}_{h\xleftarrow{R}\mathcal{H}}[h(x) = h(x')]\leq 1/|\mathcal{R}|$ .

The Lemma

Statement: Let $X$ be a random variable over $\{0, 1\}^n$ with $H_2(X)\geq k$ . Consider the two-universal function family $\mathcal{H} = \{g:\{0, 1\}^n\mapsto\{0, 1\}^m\}$ . Then for any $H\xleftarrow{R}\mathcal{H}$ , the statistical distance between $(H, H(X))$ and $(H, \mathcal{U}_m)$ is at most $\frac{1}{2}\cdot 2^{(m-k)/2}$ .

One can interpret the statement above as saying that you can convert a random variable with high-enough Rényi entropy into a random variable that is very close to uniform.

References

[1] Impagliazzo, Russell; Levin, Leonid A.; Luby, Michael (1989). Pseudo-random Generation from one-way functions.

[2] Iftach Haitner and Salil Vadhan. The Many Entropies in One-Way Functions, pages 159–217. Springer International Publishing, 2017

Why (and How) Things Work

In Honor of David Blackwell

Tag Archives for probability

Composition of Privacy Guarantees: Classical and Quantum

Classical Composition of Differential Privacy

Composition of Quantum Differential Privacy

Statistical Zero-Knowledge Proofs

Definition

Key Properties of Zero-Knowledge Proofs

Interactive Zero-Knowledge Proofs

Non-Interactive Zero-Knowledge Proofs (NIZKs)

The Fiat-Shamir Heuristic technique to convert interactive proofs into non-interactive ones using cryptographic hash functions.

Example Use Cases

1. Commit-and-Prove Protocols

2. Bulletproofs

3. Proofs in Cloud Computing

4. Secure Voting Protocols

5. Knowledge of a Password

Perfect Zero-Knowledge

Formal Definition

Key Features of Perfect Zero-Knowledge

Example of Perfect Zero-Knowledge

Computational Zero-Knowledge

Formal Definition

Key Features of Computational Zero-Knowledge

Examples of Computational Zero-Knowledge

Real-World Importance

Statistical Zero-Knowledge

Formal Definition

Key Features of Statistical Zero-Knowledge

Examples of Statistical Zero-Knowledge

Real-World Applications

Some References

Leftover Hash Lemma

Entropy Measures

The Lemma