No tight simple reduction from non-interactive assumptions to BLS signatures

Conditional · assuming non-interactive assumptions · Cor02, KK12

Statement

Let $\Pi$ be a non-interactive assumption. Every simple reduction from $\Pi$ to the EUF-CMA security of BLS signatures in the random-oracle model loses a factor of about $q_S$, the number of the forger’s signing queries: a simple reduction that loses less yields an efficient algorithm breaking $\Pi$ — Cor02, KK12. A reduction is simple if it invokes the forger only as straight-line instances, run one after another; Coron’s meta-reduction and its extensions rule out only simple reductions — MP18.

Coron stated his meta-reduction for signature schemes with unique signatures and applied it to full-domain hash and the Gennaro–Halevi–Rabin scheme — Cor02. It needs the public key that the reduction hands the forger to be efficiently recognizable as correctly formed, so the bound holds for full-domain hash only over a certified trapdoor permutation, and not for RSA full-domain hash at practical parameters — KK12. BLS signatures have certified keys: every element of ${\mathbb{G}}_2$ is a public key, and under each one exactly one $\sigma \in {\mathbb{G}}_1$ verifies on each message — standard. The loss of BLS signatures, linear in $q_S$, cannot be avoided with current proof techniques — BW24.

Notes

• The reduction from co-CDH (co-CDH ⇒ BLS signatures) loses a factor $e(q_S+1)$, which matches the bound up to a constant factor — BLS04.
• For algebraic forgers in the algebraic group model, EUF-CMA security of BLS signatures reduces tightly to DLOG (DLOG ⇒ BLS signatures) — FKL18.
• Without certified keys the bound can fail: RSA full-domain hash with a small prime exponent is tightly EUF-CMA under Φ-hiding (Φ-Hiding ⇒ DS) — KK12.
• The meta-reduction is extended to schemes with efficiently re-randomizable signatures, among them Waters signatures (the barrier for Waters signatures) — HJK12. A simpler meta-reduction gives better bounds and rules out tight reductions from a very general class of non-interactive assumptions — BJLS16.
• Without the restrictions to simple reductions and to non-interactive assumptions: if a black-box reduction whose security loss is bounded by a polynomial fixed in advance bases the security of a unique signature scheme on a bounded-round assumption, the assumption can be broken in polynomial time — MP18.
• Coron’s meta-reduction does not cover every scheme with unique signatures in the random-oracle model. For the chain-based unique signature scheme, whose signature is $n$ BLS signatures computed in sequence, a reduction from CDH loses at most $n\cdot q_H^{1/n}$ for $q_H$ hash queries, and the meta-reductions of Cor02, HJK12 and BJLS16 do not capture it — GCS+17. A simple reduction for that scheme from a non-interactive assumption loses at least a factor $q_S^{1/n}$ for $q_S$ signing queries unless the assumption is false, and a reduction from CDH losing $4q_S^{1/n}$ attains it up to a constant factor — GS22.