Type 3 pairing ⇒ Optimally short structure-preserving signatures (AGHO)

Free reduction · generic group model · AGHO11

Statement

In a Type 3 bilinear group there is a structure-preserving signature scheme whose messages are vectors of group elements and whose signatures consist of three group elements. It is strongly existentially unforgeable under adaptive chosen-message attack against generic adversaries — AGHO11. AGHO11 also prove that in Type 3 groups every structure-preserving signature scheme whose signer uses only generic group operations has signatures of at least three group elements, so the scheme is optimally short — AGHO11.

Notes

• No algebraic reduction from a non-interactive assumption proves an optimally short structure-preserving signature scheme secure (barrier) — AGO11.
• Longer structure-preserving signatures are secure under standard assumptions, for instance SXDH (SXDH ⇒ Structure-preserving signatures) — KPW15.