Communications in Cryptology IACR CiC

A Key-Recovery Attack on a Leaky SeaSign Variant

Authors

Shai Levin
Shai Levin ORCID
University of Auckland, New Zealand
shai dot levin at auckland dot ac dot nz
Keywords: Isogeny-based cryptography Cryptanalysis CSIDH Signature Schemes

Abstract

We present a key-recovery attack on a variant of the SeaSign signature scheme presented by [Kim24], which attempts to avoid rejection sampling by presampling vectors f such that the f-e is contained in an acceptable bound, where e is the secret key. We show that this choice leads to a bias of these vectors such that, in a small number of signatures, the secret key can either be completely recovered or its keyspace substantially reduced. In particular, given 20 signatures, with parameter set II of their paper, the attack reduces the private key to 128 possibilities.

References

[DG19]
Luca De Feo and Steven D. Galbraith. SeaSign: Compact Isogeny Signatures from Class Group Actions. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part III, volume 11478 of LNCS, pages 759–789. May 2019. Springer, Cham. DOI: 10.1007/978-3-030-17659-4_26
Google Scholar ePrint
[DPV19]
Thomas Decru, Lorenz Panny, and Frederik Vercauteren. Faster SeaSign Signatures Through Improved Rejection Sampling. In Jintai Ding and Rainer Steinwandt, editors, Post-Quantum Cryptography - 10th International Conference, PQCrypto 2019, pages 271–285. 2019. Springer, Cham. DOI: 10.1007/978-3-030-25510-7_15
Google Scholar ePrint
[Kim24]
Google Scholar ePrint
[Lyu09]
Vadim Lyubashevsky. Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures. In Mitsuru Matsui, editor, ASIACRYPT 2009, volume 5912 of LNCS, pages 598–616. December 2009. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-10366-7_35
Google Scholar ePrint

PDFPDF Open access

DOI: https://doi.org/10.62056/a3c39qgxq
History
Submitted: 2024-10-02
Accepted: 2024-12-03
Published: 2025-01-13
How to cite

Shai Levin, A Key-Recovery Attack on a Leaky SeaSign Variant. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/a3c39qgxq.

License

Copyright is held by the author(s)

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