Projects per year
Abstract
We present a generic forgery attack on signature schemes constructed from 5-round identification schemes made non-interactive with the Fiat-Shamir transform. The attack applies to ID schemes that use parallel repetition to decrease the soundness error. The attack can be mitigated by increasing the number of parallel repetitions, and our analysis of the attack facilitates parameter selection. We apply the attack to MQDSS, a post-quantum signature scheme relying on the hardness of the MQ-problem. Concretely, forging a signature for the L1 instance of MQDSS, which should provide 128 bits of security, can be done in ≈ 2 95 operations. We verify the validity of the attack by implementing it for round-reduced versions of MQDSS, and the designers have revised their parameter choices accordingly. We also survey other post-quantum signature algorithms and find the attack succeeds against PKP-DSS (a signature scheme based on the hardness of the permuted kernel problem) and list other schemes that may be affected. Finally, we use our analysis to choose parameters and investigate the performance of a 5-round variant of the Picnic scheme.
Original language | English |
---|---|
Title of host publication | Cryptology and Network Security - 19th International Conference, CANS 2020, Vienna, Austria, December 14–16, 2020, Proceedings |
Subtitle of host publication | 19th International Conference, CANS 2020, Vienna, Austria, December 14–16, 2020, Proceedings |
Editors | Stephan Krenn, Haya Shulman, Serge Vaudenay |
Publisher | Springer |
Pages | 3-22 |
Number of pages | 20 |
ISBN (Electronic) | 978-3-030-65411-5 |
ISBN (Print) | 9783030654108 |
DOIs | |
Publication status | Published - 14 Dec 2020 |
Event | 19th International Conference on Cryptology And Network Security - Virtuell, Austria Duration: 14 Dec 2020 → 16 Dec 2020 https://cans2020.at/ |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 12579 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 19th International Conference on Cryptology And Network Security |
---|---|
Abbreviated title | CANS 2020 |
Country/Territory | Austria |
City | Virtuell |
Period | 14/12/20 → 16/12/20 |
Internet address |
Keywords
- signatures
- post-quantum cryptography
- Fiat-Shamir heuristic
- Post-quantum cryptography
- MQDSS
- Fiat-Shamir transform
- Public-key signatures
- Security analysis
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science
Fingerprint
Dive into the research topics of 'An Attack on Some Signature Schemes Constructed From Five-Pass Identification Schemes'. Together they form a unique fingerprint.Projects
- 1 Finished
-
EU - KRAKEN - Brokerage and market platform for personal data
1/12/19 → 30/11/22
Project: Research project