Communications in Cryptology IACR CiC

Breaking BASS

Authors

Simon-Philipp Merz, Kenneth G. Paterson, Àlex Rodríguez García
Simon-Philipp Merz ORCID
ETH Zurich, Zurich, Switzerland
research at simon-philipp dot com
Kenneth G. Paterson ORCID
ETH Zurich, Zurich, Switzerland
kenny dot paterson at inf dot ethz dot ch
Àlex Rodríguez García
Universitat Politècnica de Catalunya, Barcelona, Spain
alex dot rodriguez dot garcia at upc dot edu

Abstract

We provide several attacks on the BASS signature scheme introduced by Grigoriev, Ilmer, Ovchinnikov and Shpilrain in 2023. We lay out a trivial forgery attack which generates signatures passing the scheme's probabilistic signature verification with high probability. Generating these forgeries is faster than generating signatures honestly. Moreover, we describe a key-only attack which allows us to recover an equivalent private key from a signer's public key. The time complexity of this recovery is asymptotically the same as that of signing messages.

References

[GIOS24]
Dima Grigoriev, Ilia Ilmer, Alexey Ovchinnikov, and Vladimir Shpilrain. BASS: Boolean Automorphisms Signature Scheme. In Mark Manulis, Diana Maimuţ, and George Teşeleanu, editors, Innovative Security Solutions for Information Technology and Communications, pages 1–12, Cham. 2024. Springer Nature Switzerland. DOI: 10.1007/978-3-031-52947-4_1
Google Scholar ePrint
[Rod24]
Google Scholar ePrint

PDFPDF Open access

DOI: https://doi.org/10.62056/avl86chdj
History
Submitted: 2025-01-13
Accepted: 2025-03-11
Published: 2025-04-08
How to cite

Simon-Philipp Merz, Kenneth G. Paterson, and Àlex Rodríguez García, Breaking BASS. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/avl86chdj.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.