### On the Impossibility of Purely Algebraic Signatures

Nico Döttling, Dominik Hartmann, Dennis Hofheinz, Eike Kiltz, Sven Schäge, and Bogdan Ursu

##### Abstract

The existence of one-way functions implies secure digital signatures, 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 assumptions (such as the factoring of Diffie-Hellman-like assumptions) than efficient 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 the signature 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 exactly this structure on signatures that invites attacks like ours and makes it hard to construct efficient signatures.

Available format(s)
Category
Foundations
Publication info
A minor revision of an IACR publication in TCC 2021
Keywords
Digital Signatures
Contact author(s)
nico doettling @ gmail com
dominik hartmann @ rub de
hofheinz @ inf ethz ch
eike kiltz @ rub de
sven schaege @ rub de
bogdan ursu @ inf ethz ch
History
2021-09-17: last of 2 revisions
See all versions
Short URL
https://ia.cr/2021/738

CC BY

BibTeX

@misc{cryptoeprint:2021/738,
author = {Nico Döttling and Dominik Hartmann and Dennis Hofheinz and Eike Kiltz and Sven Schäge and Bogdan Ursu},
title = {On the Impossibility of Purely Algebraic Signatures},
howpublished = {Cryptology ePrint Archive, Paper 2021/738},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/738}},
url = {https://eprint.iacr.org/2021/738}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.