Isogeny-based Signatures with Randomizable Keys
Andrea Basso, Giacomo Borin, Maria Corte-Real Santos +5 more
Digital signature schemes based on isogenies are among the most compact signatures achieving post-quantum security.Recent advances, especially those leveraging higher-dimensional isogenies, have also made such schemes practically efficient.However, comparatively little attention has been devoted to endowing these signatures with additional privacy-enhancing properties, such as the re-randomization of keys and the adaptation of signatures to new public keys.Although some results exist in the isogeny group action setting, these signatures suffer from a subexponential quantum attack which renders them rather inefficient.In this work, we initiate the first systematic study of privacy-enhancing isogeny-based signatures outside the group-action framework.We base our exploration on the notion of signatures with randomizable keys (SWRKs) developed by Celi et al. (FC'24), which aims to unify privacy notions related to key updatability and signature adaptation.In particular, we analyze which of their privacy notions can be achieved from the state-ofthe-art signatures SQIsign, PRISM and the hash-and-sign signature scheme derived from the Deuring verifiable unpredictable function (DeuringVUF).To this end, we naturally extend SQIsign to an SWRK scheme that allows key randomization, and enhance both PRISM and the DeuringVUF signature to additionally allow for message adaptation.We show that, due to the deterministic nature of the signatures, the DeuringVUF signature achieves perfect adaptability.We formally prove all three of our modifications achieve unlinkability against unbounded adversaries, and remain unforgeable under the same assumptions as the original schemes.Compared to the group-action-based schemes, however, these signatures provide less flexibility, making advanced functionalities in general harder to build.Exacerbating this, the lack of overarching frameworks often results in advanced constructions that tend to be somewhat ad-hoc and largely scheme-dependent.Contributions.In this work, we address these issues and present three novel isogeny-based signatures with randomizable keys.Our constructions build upon SQIsign [1], PRISM [5] and the signature obtained from the DeuringVUF [44, §5.2].We present our constructions in a unified framework, by abstracting away the heavy machinery of the Deuring correspondence, and relying on a set of high-level algorithms that are shared among the three signatures.Concretely, our contributions are the following.
•Jun 4, 2026•0 citations