Learning to SQI

Implementing SQISign in SageMath

Maria Corte-Real Santos, Giacomo Pope

Introduction

This blog has been written as supplementary material to support the SageMath implementation of SQISign. The aim of this implementation is to create an educational resource for the interested isogenist or cryptographer and focuses on being clear and verbose. We do not claim any novelty in the blog posts (see references below and given in the code descriptions for the papers we followed). Additionally, the implementation aims (within reason) to allow user-supplied parameters, which we hope will aid in research and experimentation to enable progress on optimising the protocol.

The implementation follows the initial 2020 description of SQISign, and in particular does not include the most recent improvements from New algorithms for the Deuring correspondence: Towards practical and secure SQISign signatures. Including these optimisations is planned for future work.

Although the code has been written with plenty of comments, there are certain aspects of SQISign which require careful attention or special tricks to deal with edge cases. This is the primary focus of this blog, and we hope that these pages will act as a guide for anyone else interested in implementing SQISign themselves.

Implementing SQISign has been a lot of fun. More than anything, we hope that with the SageMath code and these pages, more people will be able to learn about and experiment with the protocol.

Acknowledgements

SQISign-SageMath was implemented by Maria Corte-Real Santos, Jonathan Komada Eriksen, Michael Meyer and Giacomo Pope. We thank Antonin Leroux and Lorenz Panny for their advice and helpful discussions while writing the SQISign implementation.

The blog Learning to SQI was written by Maria Corte-Real Santos and Giacomo Pope. We thank our code co-authors, Jonathan Komada Eriksen and Michael Meyer for their helpful feedback while writing this material.

Existing Implementations

When published in 2020, the paper was accompanied by a C/Pari implementation, as well as a Magma reference implementation:

Similarly, when the faster description was published in 2022, a new implementation with various improvements was also released:

The most recent implementation follows the updated 2023 paper “New algorithms for the Deuring correspondence - Towards practical and secure SQISign signatures” by Luca De Feo, Antonin Leroux, Benjamin Wesolowski and Patrick Longa and is approximately 3-4 times faster than the original implementation:

References

This blog does not aim to be self-contained and much of the context for the objects and algorithms discussed come from the SQISign paper and various references.

Back to Top