Zero-Knowledge
Statements tagged with the zk area. This is a generated view, not a home directory – a statement can belong to several areas at once. See all statements for the full index, or the schema for what each column means.
| 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 | |
|
SSS Implies Fiat-Shamir Friendly Conjecture 1.3 of the source. It is explicit that it does not prove it – ‘only conjecture it’ – and asks for the proof or refutation as an important open problem. It does prove that SSS implies straight-line soundness, hence post-quantum soundness, and that its own instantiation of Kilian’s protocol is SSS. 4 open |
Commitment SchemesFiat ShamirSnarkscharacterization |
No matching items