No reduction from Falsifiable assumption to KEA

A reduction of class unstated from Falsifiable assumption to KEA would imply a contradiction.

Statement

Migrated verbatim from knowledge-of-exponent § Known Results:

  • KEA-like assumptions cannot be derived from falsifiable assumptions via black-box reductions — standard

Notes

source: folklore: the claim carried no citation on the page it was migrated from, and none was invented.

class: unstated: no citing page says which notion of reduction is meant. Recording a class the wiki does not state would add a claim.

Recorded during migration and not fixed — these are claims about the source text, not changes to it:

  • No citation; GW11 (Gentry-Wichs) is the canonical barrier and is missing.
  • SUSPECTED IMPRECISION: GW11 rules out black-box reductions proving succinct non-interactive arguments sound from falsifiable assumptions; KEA-like assumptions cannot be derived from falsifiable assumptions is a vaguer and different claim.
  • Marked standard for an attributable barrier result.
  • The barrier consequence Q is left implicit — as written it is only a non-existence claim about reductions.
  • NO CITATION, marked ’— standard’. This is the Gentry-Wichs barrier (STOC 2011) — a named, heavily cited theorem, not folklore. No GW11 reference page exists in content/References/. CLAUDE.md’s folklore exception explicitly does not cover ‘obvious to a working cryptographer’.
  • The statement is also imprecise: GW11 rules out black-box reductions from falsifiable assumptions to the ADAPTIVE SOUNDNESS of succinct non-interactive arguments (for sub-exponentially hard languages), not ‘KEA-like assumptions’ generically. The hypothesis and conclusion objects are both wrong.
  • The closely related claim at content/Primitives/succinct-argument.md:95 states the same barrier and cites Gro16, which is the wrong paper (Gro16 is a construction, not a barrier).
  • line 28 on the same page (‘KEA is non-falsifiable … — standard’) is a definitional observation, also marked standard, blurring the line between a definition and a theorem.