Direct Product Theorems
Theorems on whether solving many independent instances of a hard problem is proportionally harder than solving one.
| Status | Statement | Tags |
|---|---|---|
|
Dream DPT for a moderately hard function Open: whether there exists a function family, and a standard fine-grained hardness hypothesis (the paper suggests NSETH as an example), for which solving t independent instances requires resources within a subexponentially small factor of solving them one at a time, with no loss in the exponent. The source reduces its permissionless consensus protocol to exactly this statement and leaves it unconstructed. 5 open |
Direct Product TheoremsFine Grained CryptographyassumptionIOG | |
|
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 poly(n, log k) for k up to 2(n0.01). A 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