CryptoDB
Erebor and Durian: Full Anonymous Ring Signatures from Quaternions and Isogenies
| Authors: |
|
|---|---|
| Download: | |
| Abstract: | We construct two efficient post-quantum ring signatures with anonymity against full key exposure from isogenies, addressing the limitations of existing isogeny-based ring signatures. First, we present an efficient concrete distinguisher for the SQIsign simulator when the signing key is provided using one transcript. This shows that turning SQIsign into an efficient full anonymous ring signature requires some new ideas. Second, we propose a variant of SQIsign (Asiacrypt'20) that is resistant to the distinguisher attack with only a x1.4 increase in size and we render it to a ring signature, that we refer to as Erebor. This variant introduces a new zero-knowledge assumption that ensures full anonymity. The efficiency of Erebor remains comparable to that of SQIsign, with only a proportional increase due to the ring size. This results in a signature size of 0.71 KB for 4 users and 1.41 KB for 8 users, making it the most compact post-quantum ring signature for up to 29 users. Third, we revisit the GPS signature scheme (Asiacrypt'17), developing efficient subroutines to make the scheme more efficient and significantly reduce the resulting signature size. By integrating our scheme with the paradigm by Beullens, Katsumata, and Pintore (Asiacrypt’20), we achieve an efficient logarithmic ring signature, that we call Durian, resulting in a signature size of 9.87 KB for a ring of size 1024. |
BibTeX
@article{cic-2025-34897,
title={Erebor and Durian: Full Anonymous Ring Signatures from Quaternions and Isogenies},
journal={cic},
publisher={International Association for Cryptologic Research},
volume={1, Issue 4},
url={https://cic.iacr.org/p/1/4/4},
doi={10.62056/ava3zivrzn},
author={Giacomo Borin and Yi-Fu Lai and Antonin Leroux},
year=2025
}