Proof Size Lower Bounds
Lower bounds on how small a non-interactive argument or proof can be.
| Status | Statement | Tags |
|---|---|---|
|
dv-SNARG, One Group Element Numbered Conjecture 1.3 of the source. Its own theorems achieve one group element plus O(tau) bits, and (with a random oracle) one group element, one hash output and about 2 tau bits; the conjecture halves the additive term to tau + o(tau) and asks for no random oracle. 4 open |
Generic Group ModelProof Size Lower BoundsSnarksggmcharacterization | |
|
AVPs Are Lengthy Posed as Hypothesis 1.2 and offered both as a working hypothesis and as an ambitious target. Theorem 1.3 proves it implies super-polynomial lower bounds on sd-PIR, general secret sharing and fully-decomposable randomized encodings – for none of which a super-linear lower bound is currently known. The source adapts counting-based arguments to the model but does not reach the best-known bound for any primitive. 4 open |
Garbled CircuitsPrivate Information RetrievalProof Size Lower BoundsRandomized Encodingslower-boundbarrier (ai) | |
|
CSAT with Small Space and Preprocessing Conjecture 1.2 of the source, a parameterized family rather than a single claim. Corollary 1.3 turns each parameter setting into a limitation on succinct IOPs. The source attaches decreasing confidence as the class T grows, calling the largest setting only (arguably) unlikely to be false rather than confidently believed. 4 open |
Interactive Oracle ProofsProof Size Lower BoundsSpace Bounded ComputationTime Space Tradeoffslower-boundbarrier (ai) | |
|
No 2-element split NILPs A submitted construction gives a two-element split NILP for Boolean circuit satisfiability in the plain generic Type-III bilinear-group model; proof review and formalization remain open. 2 open |
Generic Group ModelProof Size Lower BoundsSnarksimpossibilityresearch-solved |
No matching items