A Key-Recovery Attack on a Leaky SeaSign Variant
Shai Levin · IACR Communications in Cryptology · 2025
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.