Quantum Statistical Witness Indistinguishability

Ronak Ramachandran; Shafik Nassar

REVIEW 3 major objections 4 minor 1 cited by

Quantum Statistical Witness Indistinguishability

T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper defines quantum statistical witness indistinguishability (QSWI) and proves that its honest-verifier, malicious-verifier, and public-coin variants coincide: every honest-verifier QSWI proof can be made a 3-message public-coin proo

desk verdict Fresh definition and plausible equivalences for QSWI, but the written proofs have two gaps—the view-qubit count in the batch-to-QSWI step and the malicious-verifier simulation—that need real work before the results are fully established. read the letter →

arxiv 2509.01945 v1 pith:CD4WRU4P submitted 2025-09-02 quant-ph cs.CCcs.CR

Shafik Nassar , Ronak Ramachandran This is my paper · ORCID

classification quant-phcs.CCcs.CR MSC 68Q1268Q1581P68 PACS 03.67.-a

keywords QSWIstatisticalwitnessindistinguishabilityquantuminteractiveproofsbatchpublic-coinprotocolsrewindingdistributionalstabilityzero-knowledge

topics P versus NP

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces QSWI, the quantum analogue of statistical witness indistinguishability (SWI), and asks which relations admit interactive proofs whose transcript hides which valid witness the prover used. Its main claim is that the three natural definitions coincide: any problem with an honest-verifier QSWI proof has a 3-message public-coin QSWI proof secure against malicious quantum verifiers, so pubQSWI = QSWI = hvQSWI, with the witness-indistinguishability error inflated by at most a polynomial factor. Since classical SWI proofs are a special case, the equivalence yields SWI ⊆ QSWI. The paper further proves that any ρ-compressing quantum batch proof compiles into a QSWI proof with O(√ρ) witness-indistinguishability error using a non-uniform honest prover, extending the classical batch-proof-to-WI conversion of Bitansky et al. If true, this makes QSWI structurally tractable in ways SWI is not, and makes quantum batching of NP a concrete route to weak QSWI for all of NP.

What carries the argument

The load-bearing machinery is twofold. First, the unbounded-simulator characterization of witness indistinguishability: a protocol is QSWI exactly when an (unbounded) simulator can reproduce the verifier's view at every round, and this lets the paper carry over Kobayashi's three QSZK transformations — Kitaev-Watrous round compression, Marriott-Watrous private-coin to public-coin conversion, and Watrous rewinding — while preserving prover efficiency and tracking the WI error. Second, for the batch-to-QSWI theorem, the quantum distributional stability lemma: any map from t classical bits to ρt qubits is O(√ρ)-sensitive to a random input bit, which forces a ρ-compressing batch proof to lose the

What would settle it

Build a ρ-compressing quantum batch proof whose honest verifier keeps a private register of Ω(t) qubits and measure the compiled protocol's witness-indistinguishability error: if the error grows with the private register size, the O(√ρ) bound fails as written. For the collapse theorem, exhibit a language in hvQSWI and a malicious quantum verifier that distinguishes two witnesses in every 3-message public-coin protocol for it.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that quantum statistical witness indistinguishability is robust across all reasonable definitions of the class: hvQSWI, QSWI, and pubQSWI are equal, and every honest-verifier QSWI proof can be transformed into a 3-message proof in which the verifier sends only random bits and cannot distinguish between any two valid witnesses even when malicious. The transformation chain — round compression following Kitaev and Watrous, private-coin to public-coin conversion following Marriott and Watrous, and malicious-verifier security via Watrous-style rewinding, all adapted from Kobayashi's QSZK framework — preserves the honest prover's efficiency and in

Load-bearing premise

In the batch-proof argument, the proof implicitly assumes that the verifier's full view of the interaction fits in O(ρt) qubits, even though the ρ-compressing condition only bounds the message communication and says nothing about the verifier's private workspace; if the private workspace is much larger, the stated O(√ρ) witness-indistinguishability error does not follow from the written argument.

Editorial extensions

If this is right

Because SWI ⊆ QSWI, any structural property proved for QSWI — the paper singles out closure under complement — would immediately constrain SWI, and would separate SWI from NP unless the polynomial hierarchy collapses.
The class QSWI can be studied through 3-message public-coin protocols only, matching the structural simplicity that made QSZK tractable.
Any language with a sufficiently compressing quantum batch proof, with no privacy requirement on the batch proof, inherits a malicious-verifier QSWI proof with inverse-polynomial witness-indistinguishability error.
A quantum batch proof for all of NP would place NP in QSWI (with weak, inverse-polynomial WI error), giving a new conditional attack on the conjecture that NP is outside statistical WI.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The Achilles heel of the batch-proof argument is that ρ-compressing constrains message qubits, not the verifier's private workspace, while the distributional-stability argument is applied to the full verifier view; a batch proof whose verifier keeps a large private register may need an extra workspace-dependent term in the WI error — this is my reading of the written proof, not a claim the paper m
The same simulator-based lens might extend the round-compression and public-coin machinery to QMA-style witness indistinguishability with quantum witnesses, which the paper mentions as future work but does not attempt.
The failed Grover-based batch protocol points to a concrete obstruction — a cheating prover's private register can suppress interference and break soundness — suggesting that quantum batching for NP, if achievable, needs a technique that does not rely on amplitude amplification over the prover's messages.
A numerical check on small instances of the distributional-stability lemma, comparing bit sensitivity of full views versus transcripts, would show whether the O(√ρ) bound is tight in the presence of private workspace.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: the paper defines QSWI and argues that honest-verifier, malicious-verifier, and public-coin versions coincide, plus a quantum batch-proof-to-QSWI implication. The high-level approach is right, and I think the main theorems are probably true, but the written proofs don't yet support them. There are two specific gaps that need patching before I'd trust the details.

What's genuinely new: the QSWI definition, the collapse of the three variants, and the corollary SWI ⊆ QSWI. The reduction to Kobayashi's machinery is sensible, and the paper correctly notes there's no classical analogue. The batch-proof compilation is a natural quantum extension of BKP+24, and the use of Drucker's distributional stability is appropriate. Credit also for including Appendix A, a failed batch-proof attempt with a real attack; that level of transparency is rare and useful.

The soft spots, in order of importance. First, Proposition 5.5 applies Corollary 2.3 to the full verifier view, but the output size of that view isn't bounded by ρt. The compression definition only bounds k·q_M, the total message communication; it says nothing about q_V, the verifier's private workspace, or about the batch instances x that the prover sends in the QSWI protocol. The stress-test note is right: as written, the O(√ρ) witness-indistinguishability error doesn't follow. This is likely fixable by arguing the view can be replaced by the transcript via a fixed efficient map, but that argument is absent.

Second, Lemma 4.5 (malicious verifier) is a sketch. The simulator post-selects on X=0 after applying the malicious verifier's transformation, but the state space bookkeeping is off—S(x,1) is a state on the honest verifier's registers, not on the adversary's auxiliary register, and the normalization after post-selection is hand-waved. Again, probably repairable following Kobayashi, but as written it doesn't prove the claim.

There are minor notation issues throughout, but nothing else that looks like a load-bearing error. The paper's honesty in the appendix and its clear discussion of the limitations (non-uniform prover, inverse-polynomial error) count in its favor.

Who should read it: someone working on quantum interactive proofs or on the classical SWI question. It's a solid paper to give a serious referee, but the referee will need to ask for those two fixes. If I were handling it, I'd send it out and expect a revised version to be correct.

Referee Report

3 major / 4 minor

Summary. The paper introduces QSWI, a quantum analogue of statistical witness indistinguishability, and proves two main results. First, any problem with an honest-verifier QSWI proof can be transformed into a 3-message, public-coin, malicious-verifier QSWI proof, yielding pubQSWI = QSWI = hvQSWI and, as a corollary, SWI ⊆ QSWI. Second, any ρ-compressing quantum batch proof for an NP relation gives an honest-verifier QSWI proof with O(√ρ) witness-indistinguishability error, using a non-uniform honest prover. The proofs follow Kobayashi's QSZK transformations, Watrous rewinding, and Drucker's quantum distributional stability lemma, and the paper includes a transparently labeled failed attempt at quantum batch proofs for NP in Appendix A.

Significance. If the proofs are made fully rigorous, this is a substantive contribution: it initiates the study of QSWI, shows a malicious-verifier/ honest-verifier collapse that is not known classically, proves a classical-class containment SWI ⊆ QSWI, and extends the batch-proof-to-WI compilation of Bitansky et al. to the quantum setting. Strengths include a clean set of definitions, explicit error tracking through the transformations, reliance on established external results, and honest disclosure of a failed construction. The main concerns below are about load-bearing gaps in the written proofs rather than about the novelty or plausibility of the claims.

major comments (3)

[§5.2, Prop. 5.5 / Thm. 5.4] Definition 5.2 bounds only k·q_M = o(ρt), i.e., the total message communication. The function f_τ(b) = ViewV(x,w(b),j) used in Prop. 5.5 outputs the full verifier view, which includes the verifier's private workspace (q_V qubits) and, in the compiled protocol, the full instance vector x of length n·t sent by the prover. Corollary 2.3 gives O(√(t'/t)) where t' is the output qubit count, and nothing in the definition of ρ-compression bounds q_V + n·t by O(ρt). For example, q_V = t² and n·t = t² with ρ = 1/t would give only O(1), not O(√ρ). The stated O(√ρ) WI error therefore does not follow from the written argument. The proof needs either a definition of ρ-compression that also bounds the view size, or an explicit argument reducing the view to the transcript (of size O(k·q_M)) in a way that preserves the trace distance.
[§4.1, Lemma 4.1] In the WI analysis for the compressed protocol, S'(x,1) is defined as the tensor product of S(x,j-1) over the round registers, and the proof bounds ∥ViewV'(x,w,1) − S'(x,1)∥_tr by a sum of per-round errors via 'subadditivity of trace distance for tensor products.' That subadditivity only applies when both states are tensor products. ViewV'(x,w,1) is the joint state of all the round registers and is not shown to be a product state; correlations between the round states are not addressed. This is a load-bearing gap in the round-compression step of Theorem 4.6.
[§4.3, Lemma 4.5] The malicious-verifier simulation is presented as a sketch. In particular, step 5 post-selects on the register X containing |0⟩, but the proof does not justify that the post-selection operation preserves the εWI error; the probability of the conditioning event can differ between real and simulated executions, and conditioning can amplify trace distance. Since this lemma is the step that upgrades honest-verifier security to malicious-verifier security, a formal argument (or a precise reference to the exact claim in [Kob08, Lemma 28]) is needed.

minor comments (4)

[Fact 3.4 proof] The second triangle inequality in the reverse direction uses ∥ViewV(x,w0,j) − S(x,j)∥ twice; it should be ∥ViewV(x,w1,j) − S(x,j)∥.
[Def. 5.2] The definition says ρ ∈ N, but Theorem 5.4 and Corollary 5.6 use ρ ∈ (0,1). Please reconcile the notation.
[Figs. 3–4] The QSWI prover is described as sending 'x and j' to the verifier, but the verifier algorithm appears to use only x. Clarify whether the index j is part of the message and how it is used in completeness and soundness.
[Appendix A] The appendix is clearly labeled as a failed attempt and is discussed as such in Section 6; I did not treat it as a proof claim.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central derivations reduce to external prior work (Kobayashi, Kitaev-Watrous, Marriott-Watrous, Watrous, Drucker, Lipton-Yung) and are not self-referential.

full rationale

The paper’s main equality theorem is not circular. Facts 3.4 and 3.5 are direct equivalences between trace-distance witness indistinguishability and the existence of an unbounded simulator; each direction is proved by a canonical-witness simulation or by the triangle inequality, and the facts do not presuppose the theorem being proved. The subsequent transformations in Lemmas 4.1, 4.2, 4.3, 4.4, and 4.5 import their completeness and soundness analyses from Kobayashi (TCC 2008), Kitaev-Watrous, Marriott-Watrous, and Watrous—external sources, not the authors’ own prior work—and only add WI-error accounting through the simulator characterization. The batching argument in Theorem 5.4 is likewise non-circular: it defines a zero-sum game whose payoff is the WI trace distance, bounds the game value by O(sqrt(rho)) using Drucker’s quantum distributional stability lemma, and then applies the Lipton-Yung sparse minimax theorem to obtain a non-uniform prover strategy. No fitted parameter is renamed as a prediction, and no target conclusion appears as a premise. The one flagged weakness—Proposition 5.5 applying Corollary 2.3 to the full verifier view without an explicit bound on q_V from ρ-compression—is a possible technical gap in the written argument, not a circular reduction. Appendix A transparently reports a failed batching attempt rather than smuggling in an assumption. The paper’s self-citations ([MNRV24], [NWW24], [NWW25]) appear only in related-work discussion and are not load-bearing. Therefore the derivation is self-contained against external benchmarks and no circularity is identified.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The paper's central results rely on external theorems from quantum zero-knowledge, instance compression, and game theory. The main unstated addition is the assumption that the quantum distributional stability lemma can be applied to the full verifier view despite only the message communication being bounded by the compression parameter.

assumptions (4)

standard math Kobayashi's QSZK transformations (Lemmas 17, 20, 28 in [Kob08]) remain correct when ZK is replaced by unbounded-simulator statistical WI and when prover efficiency must be preserved.
Theorems 1.1 relies on these transformations. The paper says the proofs are 'nearly identical' and delegates soundness to Kobayashi, so correctness of the cited results is load-bearing.
ad hoc to paper Drucker's quantum distributional stability lemma (Lemma 2.2) applies to the input-to-view mapping with output size bounded by the message communication length.
Lemma 2.2 is cited from [Dru12] but the paper applies it to the full verifier view without proving that the view has O(ρt) qubits. This is an unstated assumption needed for Theorem 5.4.
standard math The Lipton-Yung sparse minimax theorem gives a poly(n)-sized multiset strategy for the column player that approximately matches the value of the game.
Theorem 5.4 uses Lemma 5.3 from [LY94] to obtain the non-uniform distribution S_n over dummy instances. This is a standard game theory result.
standard math Quantum parallel repetition reduces soundness error as stated in [KW00, Theorem 6].
Lemma 4.2 uses parallel repetition for quantum interactive proofs to amplify soundness. The paper cites [KW00] for this fact.

invented entities (1)

QSWI complexity class
purpose: Captures languages with quantum statistical witness indistinguishable proofs against honest and malicious verifiers.
This is a formal definition rather than a physical entity. Its properties are the subject of the paper, and there is no falsifiable handle external to the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Quantum Statistical Witness Indistinguishability." pith.science (2026). https://pith.science/paper/CD4WRU4P

@misc{pith2026250901945,
  author       = {Pith},
  title        = {Pith review of: Quantum Statistical Witness Indistinguishability},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CD4WRU4P}},
  note         = {Machine review of arXiv:2509.01945}
}

read the original abstract

Statistical witness indistinguishability is a relaxation of statistical zero-knowledge which guarantees that the transcript of an interactive proof reveals no information about which valid witness the prover used to generate it. In this paper we define and initiate the study of QSWI, the class of problems with quantum statistically witness indistinguishable proofs. Using inherently quantum techniques from Kobayashi (TCC 2008), we prove that any problem with an honest-verifier quantum statistically witness indistinguishable proof has a 3-message public-coin malicious-verifier quantum statistically witness indistinguishable proof. There is no known analogue of this result for classical statistical witness indistinguishability. As a corollary, our result implies SWI is contained in QSWI. Additionally, we extend the work of Bitansky et al. (STOC 2023) to show that quantum batch proofs imply quantum statistically witness indistinguishable proofs with inverse-polynomial witness indistinguishability error.

Figures

Figures reproduced from arXiv: 2509.01945 by the authors.

**Figure 2.** Honest verifier’s three-message public-coin protocol. [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

**Figure 3.** Algorithm P ′ . QSWI Verifier Algorithm Inputs: an instance x. 1. Receives x and j from the prover. 2. Each circuit V ′ j (x, w) is simply defined as the circuit Vj (x, w) [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Algorithm V ′ . Completeness and soundness follow immediately from the completeness and soundness of (P, V ) and the fact that the prover samples “yes” instances with valid witnesses. We move on to honest-verifier witness indistinguishability. The goal is to find a dis…

**Figure 5.** Figure 5: The main subroutine of our failed attempt to quantumly batch all of [PITH_FULL_IMAGE:figures/full_fig_p018_5.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

QMA Lower Bounds for Batch Verification via Approximate Degree
cs.CC 2026-07 accept novelty 7.0 of 10

Approximate degree of f yields QMA witness-query tradeoffs for AND_m ◦ f^m, giving new lower bounds for surjectivity, k-element distinctness, and DNF batch verification.

Reference graph

Works this paper leans on

33 extracted references · 32 canonical work pages · cited by 1 Pith paper

[1]

Snargs for monotone policy batch np

Zvika Brakerski, Maya Farber Brodsky, Yael Tauman Kalai, Alex Lombardi, and Omer Paneth. Snargs for monotone policy batch np. In Annual International Cryptology Conference , pages 252--283. Springer, 2023

work page 2023
[2]

Does co-np have short interactive proofs? Information Processing Letters , 25(2):127--132, 1987

Ravi B Boppana, Johan Hastad, and Stathis Zachos. Does co-np have short interactive proofs? Information Processing Letters , 25(2):127--132, 1987

work page 1987
[3]

Batch proofs are statistically hiding

Nir Bitansky, Chethan Kamath, Omer Paneth, Ron D Rothblum, and Prashant Nalini Vasudevan. Batch proofs are statistically hiding. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 435--443, 2024

work page 2024
[4]

Correlation intractability and snargs from sub-exponential ddh

Arka Rai Choudhuri, Sanjam Garg, Abhishek Jain, Zhengzhong Jin, and Jiaheng Zhang. Correlation intractability and snargs from sub-exponential ddh. In Annual International Cryptology Conference , pages 635--668. Springer, 2023

work page 2023
[5]

Non-interactive batch arguments for np from standard assumptions

Arka Rai Choudhuri, Abhishek Jain, and Zhengzhong Jin. Non-interactive batch arguments for np from standard assumptions. In Annual International Cryptology Conference , pages 394--423. Springer, 2021

work page 2021
[6]

Snargs for p from lwe

Arka Rai Choudhuri, Abhihsek Jain, and Zhengzhong Jin. Snargs for p from lwe. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 68--79. IEEE, 2022

work page 2021
[7]

And-compression of np-complete problems: Streamlined proof and minor observations

Holger Dell. And-compression of np-complete problems: Streamlined proof and minor observations. Algorithmica , 75:403--423, 2016

work page 2016
[8]

New limits to classical and quantum instance compression

Andrew Drucker. New limits to classical and quantum instance compression. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages 609--618. IEEE, 2012

work page 2012

Show all 33 references

[9]

The complexity of perfect zero-knowledge

Lance Fortnow. The complexity of perfect zero-knowledge. In Proceedings of the nineteenth annual ACM symposium on Theory of computing , pages 204--209, 1987

1987
[10]

Witness indistinguishable and witness hiding protocols

Uriel Feige and Adi Shamir. Witness indistinguishable and witness hiding protocols. In Proceedings of the twenty-second annual ACM symposium on Theory of computing , pages 416--426, 1990

1990
[11]

Knowledge complexity of interactive proof-systems

Shafi Goldwasser, Silvio Micali, and Charles Rackoff. Knowledge complexity of interactive proof-systems. In Conference Proceedings of the Annual ACM Symposium on Theory of Computing , pages 291--304, 1985

1985
[12]

Private coins versus public coins in interactive proof systems

Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In Proceedings of the eighteenth annual ACM symposium on Theory of computing , pages 59--68, 1986

1986
[13]

On Arbitrary Phases in Quantum Amplitude Amplification

Peter Hoyer. On Arbitrary Phases in Quantum Amplitude Amplification . Phys. Rev. A , 62(5), October 2000. arXiv:quant-ph/0006031

2000 arXiv
[14]

General properties of quantum zero-knowledge proofs

Hirotada Kobayashi. General properties of quantum zero-knowledge proofs. In Theory of Cryptography: Fifth Theory of Cryptography Conference, TCC 2008, New York, USA, March 19-21, 2008. Proceedings 5 , pages 107--124. Springer, 2008

2008
[15]

Batch verification for statistical zero knowledge proofs

Inbar Kaslasi, Guy N Rothblum, Ron D Rothblum, Adam Sealfon, and Prashant Nalini Vasudevan. Batch verification for statistical zero knowledge proofs. In Theory of Cryptography Conference , pages 139--167. Springer, 2020

2020
[16]

Public-coin statistical zero-knowledge batch verification against malicious verifiers

Inbar Kaslasi, Ron D Rothblum, and Prashant Nalini Vasudevanr. Public-coin statistical zero-knowledge batch verification against malicious verifiers. In Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages 219--246. Springer, 2021

2021
[17]

Doubly-efficient batch verification in statistical zero-knowledge

Or Keret, Ron D Rothblum, and Prashant Nalini Vasudevan. Doubly-efficient batch verification in statistical zero-knowledge. In Theory of Cryptography Conference , pages 371--398. Springer, 2024

2024
[18]

Parallelization, amplification, and exponential time simulation of quantum interactive proof systems

Alexei Kitaev and John Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In Proceedings of the thirty-second annual ACM symposium on Theory of computing , pages 608--617, 2000

2000
[19]

Simple strategies for large zero-sum games with applications to complexity theory

Richard J Lipton and Neal E Young. Simple strategies for large zero-sum games with applications to complexity theory. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing , pages 734--740, 1994

1994
[20]

Strong batching for non-interactive statistical zero-knowledge

Changrui Mu, Shafik Nassar, Ron D Rothblum, and Prashant Nalini Vasudevan. Strong batching for non-interactive statistical zero-knowledge. In Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages 241--270. Springer, 2024

2024
[21]

Quantum arthur--merlin games

Chris Marriott and John Watrous. Quantum arthur--merlin games. computational complexity , 14(2):122--152, 2005

2005
[22]

Zero knowledge with efficient provers

Minh-Huyen Nguyen and Salil Vadhan. Zero knowledge with efficient provers. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , pages 287--295, 2006

2006
[23]

Monotone policy bargs from bargs and additively homomorphic encryption

Shafik Nassar, Brent Waters, and David J Wu. Monotone policy bargs from bargs and additively homomorphic encryption. In Theory of Cryptography Conference , pages 399--430. Springer, 2024

2024
[24]

Monotone-policy bargs and more from bargs and quadratic residuosity

Shafik Nassar, Brent Waters, and David J Wu. Monotone-policy bargs and more from bargs and quadratic residuosity. In IACR International Conference on Public-Key Cryptography , pages 283--313. Springer, 2025

2025
[25]

On relationships between statistical zero-knowledge proofs

Tatsuaki Okamoto. On relationships between statistical zero-knowledge proofs. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing , pages 649--658, 1996

1996
[26]

Witness-indistinguishability against quantum adversaries

Raluca Ada Popa. Witness-indistinguishability against quantum adversaries. Project Report , 2011

2011
[27]

Constant-round interactive proofs for delegating computation

Omer Reingold, Guy N Rothblum, and Ron D Rothblum. Constant-round interactive proofs for delegating computation. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages 49--62, 2016

2016
[28]

Efficient batch verification for up

Omer Reingold, Guy N Rothblum, and Ron D Rothblum. Efficient batch verification for up. In 33rd Computational Complexity Conference (CCC 2018) , pages 22--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2018

2018
[29]

A complete problem for statistical zero knowledge

Amit Sahai and Salil Vadhan. A complete problem for statistical zero knowledge. Journal of the ACM (JACM) , 50(2):196--249, 2003

2003
[30]

A study of statistical zero-knowledge proofs

Salil Pravin Vadhan. A study of statistical zero-knowledge proofs . PhD thesis, Massachusetts Institute of Technology, 1999

1999
[31]

Limits on the power of quantum statistical zero-knowledge

John Watrous. Limits on the power of quantum statistical zero-knowledge. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. , pages 459--468. IEEE, 2002

2002
[32]

Zero-knowledge against quantum attacks

John Watrous. Zero-knowledge against quantum attacks. In Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing , pages 296--305, 2006

2006
[33]

Batch arguments for np and more from standard bilinear group assumptions

Brent Waters and David J Wu. Batch arguments for np and more from standard bilinear group assumptions. In Annual International Cryptology Conference , pages 433--463. Springer, 2022

2022

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.

[1] [1]

Snargs for monotone policy batch np

Zvika Brakerski, Maya Farber Brodsky, Yael Tauman Kalai, Alex Lombardi, and Omer Paneth. Snargs for monotone policy batch np. In Annual International Cryptology Conference , pages 252--283. Springer, 2023

work page 2023

[2] [2]

Does co-np have short interactive proofs? Information Processing Letters , 25(2):127--132, 1987

Ravi B Boppana, Johan Hastad, and Stathis Zachos. Does co-np have short interactive proofs? Information Processing Letters , 25(2):127--132, 1987

work page 1987

[3] [3]

Batch proofs are statistically hiding

Nir Bitansky, Chethan Kamath, Omer Paneth, Ron D Rothblum, and Prashant Nalini Vasudevan. Batch proofs are statistically hiding. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 435--443, 2024

work page 2024

[4] [4]

Correlation intractability and snargs from sub-exponential ddh

Arka Rai Choudhuri, Sanjam Garg, Abhishek Jain, Zhengzhong Jin, and Jiaheng Zhang. Correlation intractability and snargs from sub-exponential ddh. In Annual International Cryptology Conference , pages 635--668. Springer, 2023

work page 2023

[5] [5]

Non-interactive batch arguments for np from standard assumptions

Arka Rai Choudhuri, Abhishek Jain, and Zhengzhong Jin. Non-interactive batch arguments for np from standard assumptions. In Annual International Cryptology Conference , pages 394--423. Springer, 2021

work page 2021

[6] [6]

Snargs for p from lwe

Arka Rai Choudhuri, Abhihsek Jain, and Zhengzhong Jin. Snargs for p from lwe. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 68--79. IEEE, 2022

work page 2021

[7] [7]

And-compression of np-complete problems: Streamlined proof and minor observations

Holger Dell. And-compression of np-complete problems: Streamlined proof and minor observations. Algorithmica , 75:403--423, 2016

work page 2016

[8] [8]

New limits to classical and quantum instance compression

Andrew Drucker. New limits to classical and quantum instance compression. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages 609--618. IEEE, 2012

work page 2012