Is there a fine-grained hardness assumption with a lossless direct product theorem?
The reduction to a plain function is done; nobody has built the function
Motivation
Permissionless consensus without a random oracle or a beacon needs a proof-of-work puzzle with an unusually strong amplification property: an adversary handed \(t\) independent puzzles and given only about as much time as solving them one after another honestly should succeed on all of them with probability at most its single-puzzle success probability raised to the \(t\)-th power — a “dream” direct product theorem, with no slack in the exponent. The source paper needs this at a subexponentially small per-instance bound, because the machinery that lets parties agree on which puzzles are legitimate — a security-preserving distributed sampler, used in place of a trusted beacon — loses a multiplicative factor exponential in the number of times it is reused.
Nothing currently supplies a puzzle that strong. Complexity leveraging cannot substitute for it: raising the puzzle’s security parameter to compensate also raises the honest solving cost, defeating the point of a puzzle. Known proofs of work built from fine-grained hardness assumptions do not reach subexponential soundness either.
Provenance and history
From Abram, Ball, Garay and Kiayias, Permissionless Consensus from a Common Random String, Cryptology ePrint Archive, Report 2026/1179; abridged version to appear at CRYPTO 2026. Section 5, “Extensions and Open Questions”, closes with:
“In Section 3, we observe that a sufficiently moderately hard function can be combined with subexponentially secure LWE to yield a proof of work, constructing this moderately (very) hard function from standard complexity conjectures is an interesting open problem in hardness amplification. For example, can one show a (tight) ‘dream’ strong direct product theorem for some function assuming, say, NSETH?”
What the paper actually closes
The paper’s own contribution here is not the amplification statement — it is the observation that efficient verifiability is not the obstacle. Given any function that is moderately hard in the paper’s sense but not necessarily efficiently checkable, a subexponentially sound SNARG for \(\mathsf{P}\) (available from subexponentially secure LWE) upgrades it to a full proof of work for free. That collapses the entire remaining gap to a pure hardness-amplification question about a plain function family, with no proof-of-work machinery left in it.
What is settled and what is not
| status | |
|---|---|
| efficient verifiability can be added for free by a SNARG, given a moderately hard function | proved — the source’s Section 3 remark, via Choudhuri–Jain–Jin |
| a moderately hard function with the required subexponential parameters, from a standard fine-grained hypothesis | open — tracked as c/0040 |
| existing fine-grained-hardness proofs of work reach the required soundness | refuted — the source states existing constructions fall short |
| complexity leveraging supplies the gap | refuted — raising the security parameter with \(t\) also raises honest cost with \(t\) |
The paper names NSETH only as an example (“assuming, say, NSETH”) rather than committing to it, so c/0040 states the conjecture with NSETH as the hypothesis but explicitly invites substituting another standard fine-grained hardness conjecture.
Statements in this hub
- A Dream Direct Product Theorem for a Moderately Hard Function — open; whether a function family exists, secure under a standard fine-grained hypothesis, whose multi-instance hardness amplifies losslessly in the exponent.