Falsifiable assumptions

An assumption is falsifiable if a violation of it can be witnessed by a polynomial-time game between a challenger and an adversary, so that a counterexample can be efficiently recognized; KEA-style knowledge assumptions are not.

TODO: syntax and security definition.

Bounded-round assumptions

An $r(\cdot )$-round intractability assumption is a pair $(C,t)$ of a challenger $C$ and a threshold $t(\lambda )$. The challenger may be computationally unbounded, and it interacts with the adversary in at most $r(\lambda )$ rounds, for a polynomial $r$ fixed in advance. The assumption holds if every efficient adversary makes $C$ output $1$ with probability at most $t(\lambda )+\mathrm{negl}(\lambda )$. A bounded-round assumption is an $r$-round assumption for some polynomial $r$ — Pas11, who calls them polynomial-round intractability assumptions. Search and decision assumptions such as DLOG and DDH are 2-round, with thresholds $0$ and $1/2$ — standard. OMDL is not bounded-round: its adversary may make any polynomial number of discrete-logarithm queries, so no polynomial bounds the number of rounds in advance — standard. The challenger need not be efficient, so bounded-round assumptions are not a special case of falsifiable ones, whose challenger is efficient.

Non-interactive assumptions

A non-interactive assumption is a pair $(\mathcal{I},\mathcal{V})$ of efficient algorithms. The instance generator $\mathcal{I}(1^{\lambda })$ outputs an instance $X$ together with private verification information $\omega$, and the verifier $\mathcal{V}(X,\omega ,y)$ accepts or rejects an answer $y$. The assumption holds if for all efficient $\mathcal{A}$, given the instance and no oracle, $\mathrm{Pr}[\mathcal{V}(X,\omega ,\mathcal{A}(1^{\lambda },X))=1]$ is negligible — standard. DLOG, CDH and q-SDH are non-interactive; LRSW and OMDL are not, since their adversaries query an oracle — standard. The challenger of a non-interactive assumption runs $\mathcal{I}$ and $\mathcal{V}$, so every non-interactive assumption is falsifiable — standard.

Participates in

Barriers

• No fully-black-box reduction from bounded-round assumptions to Schnorr identification under concurrent attack (via Bounded-round assumptions)
• No fully-black-box reduction from bounded-round assumptions to OMDL (via Bounded-round assumptions)
• No fully-black-box reduction from Falsifiable assumption to SNARK
• No tight simple reduction from non-interactive assumptions to BLS signatures (via Non-interactive assumptions) — circumvented by co-CDH ⇒ BLS signatures, DLOG ⇒ BLS signatures
• No algebraic reduction from non-interactive assumptions to optimally short structure-preserving signatures (via Non-interactive assumptions)
• No tight simple reduction from non-interactive assumptions to Waters signatures (via Non-interactive assumptions) — circumvented by Type 1 pairing + CDH ⇒ Waters signatures