Direct Product Theorems
Theorems on whether solving many independent instances of a hard problem is proportionally harder than solving one.
| Status | Problem | 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 \(\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