Short signatures from the Weil pairing (Q1772229)

In this article the authors introduce a new signature scheme based on the Weil pairing. The main feature of this new signature scheme is that it is shorter than other known schemes: following the authors, a 170 bit signature provides a level of security similar to that of the 320 bit DSA signature. The scheme is based on groups for which the computational Diffie-Hellman problem is hard, but the decisional Diffie-Hellman problem is easy. Such groups are called by the authors ``gap Diffie-Hellman'' (GDH) groups, and the main tools for constructing them are elliptic curves. For instance, explicit GDH groups arising from some families of elliptic curves are considered. To that end they define the ``security multiplier'', \(\alpha\) of a subgroup \(\langle P \rangle\) of \(E({\mathbb F}_q)\). If \(\alpha>1\) they take \(G^1=\langle P \rangle\), \(G^2=\langle Q \rangle\), for suitable \(P\) and \(Q\), and use the Weil pairing to obtain a GDH group. Explicit families of curves with \(\alpha=6\) are described. Constructing elliptic curves having a given security multiplier \(\alpha\) remains as an open problem.