Erebor and Durian: Full Anonymous Ring Signatures from Quaternions and Isogenies

Link to the preprint. Proof of Concept implementation at giacomoborin/RingSQISign-poc.

In this work we address the problem of instantiating efficient ring signatures from isogenies that provides both full anonymity and sufficient post-quantum security constructing two efficient post-quantum ring signatures with anonymity against full key exposure, addressing the limitations of existing isogeny-based ring signatures.

We remark that turning SQIsign into an efficient full anonymous ring signature requires some new ideas. In fact, in the first part of the paper, we present an efficient concrete distinguisher for the SQIsign simulator when the signing key is provided using one transcript. This

Erebor

As a linear ring signature we propose a variant of SQIsign (Asiacrypt’20) that is resistant to the distinguisher attack with only a $\times 1.4$ increase in size and we render it to a ring signature, that we refer 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.

Durian

To get instead a logarithmic ring signature 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.

Recommended citation: Giacomo Borin, Yi-Fu Lai, Antonin Leroux". Cryptology ePrint Archive (2024).
Download Paper