Fine Grained Cryptography
Cryptographic constructions based on worst-case, fine-grained hardness assumptions rather than average-case ones.
| 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 | |
|
Planted k-OV Hardness Conjecture 10 of the source, and a newly proposed average-case assumption rather than a question the literature already asked. Its worst-case counterpart – that k-OV requires n^(k-o(1)) time – is a central conjecture of fine-grained complexity. The planting preserves the marginal distribution of any subset of fewer than k vectors, and the source gives a search-to-decision reduction. 5 open |
Average Case HardnessFine Grained CryptographyOrthogonal VectorsPlanted Constraint Satisfactionassumption |
No matching items