On the Impossibility of Purely Algebraic Signatures

The existence of one-way functions implies secure digital sig-
natures, but not public-key encryption (at least in a black-box setting).
Somewhat surprisingly, though, efficient public-key encryption schemes
appear to be much easier to construct from concrete algebraic assump-
tions (such as the factoring of Diffie-Hellman-like assumptions) than ef-
ficient digital signature schemes. In this work, we provide one reason for
this apparent difficulty to construct efficient signature schemes.
Specifically, we prove that a wide range of algebraic signature schemes
(in which verification essentially checks a number of linear equations over
a group) fall to conceptually surprisingly simple linear algebra attacks.
In fact, we prove that in an algebraic signature scheme, sufficiently many
signatures can be linearly combined to a signature of a fresh message. We
present attacks both in known-order and hidden-order groups (although
in hidden-order settings, we have to restrict our definition of algebraic
signatures a little). More explicitly, we show:
– the insecurity of all algebraic signature schemes in Maurer’s generic
group model (in pairing-free groups), as long as these schemes do not
rely on other cryptographic assumptions, such as hash functions.
– the insecurity of a natural class of signatures in hidden-order groups,
where verification consists of linear equations over group elements.
We believe that this highlights the crucial role of public verifiability in
digital signature schemes. Namely, while public-key encryption schemes
do not require any publicly verifiable structure on ciphertexts, it is ex-
actly this structure on signatures that invites attacks like ours and makes
it hard to construct efficient signatures.