No algebraic reduction from non-interactive assumptions to optimally short structure-preserving signatures

Unconditional · AGO11

Statement

Let $S$ be a structure-preserving signature scheme in a Type 3 bilinear group whose signatures consist of three group elements, the minimum of AGHO11. If an algebraic reduction proves $S$ existentially unforgeable under adaptive chosen-message attack from a non-interactive assumption, then the assumption is false. A reduction is algebraic if every group element it outputs comes with its representation in the group elements it was given — AGO11.

Notes

• Optimally short structure-preserving signatures are secure in the generic group model (Type 3 pairing ⇒ Optimally short structure-preserving signatures) — AGHO11.
• Longer structure-preserving signatures are secure under SXDH (SXDH ⇒ Structure-preserving signatures) — KPW15, and tightly under DLIN in symmetric groups (Type 1 pairing + DLIN ⇒ Structure-preserving signatures) — HJ12.