## Abstract

We introduce a new signature scheme, SQISign, (for Short Quaternion and Isogeny Signature) from isogeny graphs of supersingular elliptic curves. The signature scheme is derived from a new one-round, high soundness, interactive identification protocol. Targeting the postquantum NIST-1 level of security, our implementation results in signatures of 204 bytes, secret keys of 16 bytes and public keys of 64 bytes. In particular, the signature and public key sizes combined are an order of magnitude smaller than all other post-quantum signature schemes. On a modern workstation, our implementation in C takes 0.6s for key generation, 2.5s for signing, and 50ms for verification.

While the soundness of the identification protocol follows from classical assumptions, the zero-knowledge property relies on the second main contribution of this paper. We introduce a new algorithm to find an isogeny path connecting two given supersingular elliptic curves of known endomorphism rings. A previous algorithm to solve this problem, due to Kohel, Lauter, Petit and Tignol, systematically reveals paths from the input curves to a `special' curve. This leakage would break the zero-knowledge property of the protocol. Our algorithm does not directly reveal such a path, and subject to a new computational assumption, we prove that the resulting identification protocol is zero-knowledge.

While the soundness of the identification protocol follows from classical assumptions, the zero-knowledge property relies on the second main contribution of this paper. We introduce a new algorithm to find an isogeny path connecting two given supersingular elliptic curves of known endomorphism rings. A previous algorithm to solve this problem, due to Kohel, Lauter, Petit and Tignol, systematically reveals paths from the input curves to a `special' curve. This leakage would break the zero-knowledge property of the protocol. Our algorithm does not directly reveal such a path, and subject to a new computational assumption, we prove that the resulting identification protocol is zero-knowledge.

Original language | English |
---|---|

Title of host publication | 26th Annual International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt 2020) |

Publisher | Springer |

Number of pages | 30 |

Publication status | Accepted/In press - 16 Aug 2020 |

Event | 26th Annual International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt 2020) - Virtual Event Duration: 7 Dec 2020 → 11 Dec 2020 |

### Conference

Conference | 26th Annual International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt 2020) |
---|---|

City | Virtual Event |

Period | 7/12/20 → 11/12/20 |

## Keywords

- Post-quantum
- Signatures
- Isogenies