## 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 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 exactly this structure on signatures that invites attacks like ours and makes it hard to construct efficient signatures.

Original language | English |
---|---|

Title of host publication | Theory of Cryptography - 19th International Conference, TCC 2021, Proceedings |

Editors | Kobbi Nissim, Brent Waters, Brent Waters |

Pages | 317-349 |

Number of pages | 33 |

DOIs | |

Publication status | Published - 2021 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 13044 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Bibliographical note

DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.### Funding

Acknowledgements. We thank Mark Zhandry and the anonymous reviewers for their helpful comments. Nico Döttling was supported by the Helmholtz Association within the project “Trustworthy Federated Data Analytics” (TFDA) (funding number ZT-I-OO1 4). Dennis Hofheinz and Bogdan Ursu were supported in part by ERC grant 724307. Dominik Hartmann was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under German’s Excellence Strategy - EXC 2092 CASA - 390781972, and the German Federal Ministry of Education and Research (BMBF) iBlockchain project. Eike Kiltz was supported by the BMBF iBlockchain project, the EU H2020 PROMETHEUS project 780701, DFG SPP 1736 Big Data, and by the Deutsche Forschungsgemeinschaft (DFG, German research Foundation) as part of the Excellence Strategy of the German Federal and State Governments – EXC 2092 CASA - 390781972. Sven Schäge was supported by the German Federal Ministry of Education and Research (BMBF), Project DigiSeal (16KIS0695) and Huawei Technologies Düsseldorf, Project vHSM. Part of this work was done while Sven Schäge was at Ruhr-University Bochum.

Funders | Funder number |
---|---|

European Union H2020 | 16KIS0695, 780701 |

Huawei Technologies Deutschland | |

TFDA | ZT-I-OO1 4 |

European Union's Horizon 2020 - Research and Innovation Framework Programme | 724307 |

European Research Council | |

Deutsche Forschungsgemeinschaft | EXC 2092 CASA - 390781972 |

Bundesministerium für Bildung und Forschung | |

Helmholtz Association |