A Key-Recovery Attack on a Leaky Seasign Variant

Shai Levin

Paper 2024/1261

A Key-Recovery Attack on a Leaky Seasign Variant

Shai Levin

, University of Auckland

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 $\mathbf{f}$ such that the $\mathbf{f}-\mathbf{e}$ is contained in an acceptable bound, where $\mathbf{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, on average, given $20$ signatures, with parameter set II of their paper, the attack reduces the private key to 128 possibilities

Note: (Update #1) Final version for publication. (Update #2) Added missing acknowledgements

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published by the IACR in CIC 2024
Keywords: isogenies isogeny cryptanalysis signatures rejection sampling
Contact author(s): shai levin @ auckland ac nz
History: 2025-01-14: last of 2 revisions; 2024-08-09: received; See all versions
Short URL: https://ia.cr/2024/1261
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1261,
      author = {Shai Levin},
      title = {A Key-Recovery Attack on a Leaky Seasign Variant},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1261},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1261}
}