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

Conditional · assuming non-interactive assumptions · HJK12

Statement

Let $\Pi$ be a non-interactive assumption. Every simple reduction from $\Pi$ to the EUF-CMA security of Waters signatures loses a factor $\Omega (q_S)$, for $q_S$ signing queries, unless $\Pi$ is false. The meta-reduction is stated for black-box reductions to signature schemes with efficiently re-randomizable signatures, and Waters signatures re-randomize publicly — HJK12. 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.

Notes

• Waters’s reduction from CDH in a symmetric bilinear group (Type 1 pairing + CDH ⇒ Waters signatures) loses a factor $O(n{q}_S)$ for $n$-bit messages — HJK12; recasting its hash as a programmable hash function improves the loss to $O(\sqrt{n}{q}_S)$ — HK08. Waters signatures on messages encoded so that any two encodings are far apart in Hamming distance are EUF-CMA under CDH with loss $O(q_S)$, which the bound shows optimal up to a constant factor among simple reductions — HJK12.
• Coron’s earlier meta-reduction, stated for schemes with unique signatures, gives the bound for BLS signatures (the barrier for BLS signatures) — Cor02.
• In the random-oracle model the meta-reduction does not capture every scheme with unique, hence re-randomizable, signatures: a reduction from CDH for the chain-based unique signature scheme loses at most $n\cdot q_H^{1/n}$ for $q_H$ hash queries — GCS+17.