Batch Verification
Proving many statements at once more cheaply than proving each separately, while preserving the proof system’s guarantees.
| Status | Problem | Tags |
|---|---|---|
|
SZK Batch Verification Named by the source as the most pressing open question its work leaves. Its Theorem 1.1 gives the NISZK analogue: communication and CRS length \(\mathrm{poly}(n,\log k)\) for \(k\) up to \(2^{n^{0.01}}\). A \(\mathrm{poly}(n)\) dependence is unavoidable even at \(k=1\) under a sub-exponential hardness assumption, so \(\log k\) is the aggressive part of the bound. The source also offers a weaker fallback target: any sub-linear dependence on \(k\). 5 open |
Batch VerificationDirect Product TheoremsLimited IndependenceRandomness Extractioncharacterization |
No matching items