Paper 2024/773

SQIPrime: A dimension 2 variant of SQISignHD with non-smooth challenge isogenies

Max Duparc, École Polytechnique Fédérale de Lausanne
Tako Boris Fouotsa, École Polytechnique Fédérale de Lausanne
Abstract

We introduce SQIPrime, a post-quantum digital signature scheme based on the Deuring correspondence and Kani's Lemma. Compared to its predecessors that are SQISign and especially SQISignHD, SQIPrime further expands the use of high dimensional isogenies, already in use in the verification in SQISignHD, to both key generation and commitment. In doing so, it no longer relies on smooth degree isogenies (of dimension 1). SQIPrime operates with a prime number of the form $p = 2^\alpha f-1$, as opposed to SQISignHD that uses SIDH primes. The most intriguing novelty in SQIPrime is the use of non-smooth degree isogenies as challenge isogeny. In fact, in the SQISign family identification scheme, the challenge isogeny is computed by the verifier, who is not well-equipped to compute an isogeny of large non-smooth degree. To overcome this obstacle, the verifier samples the kernel of the challenge isogeny and the task of computing this isogeny is accomplished by the prover. The response is modified in such a way that the verifier can check that his challenge isogeny was correctly computed by the prover, on top of verifying the usual response in the SQISign family. We describe two variants of SQIPrime: SQIPrime4D which uses dimension 4 isogenies to represent the response isogeny, and SQIPrime2D which solely uses dimension 2 isogenies to represent the response isogeny and hence is more efficient compared to SQIPrime4D and to SQISignHD.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Post-Quantum CryptographySupersingular IsogeniesSQISignSQISignHDKani’s LemmaSQIPrime
Contact author(s)
maxduparc @ gmail com
tako fouotsa @ epfl ch
History
2024-05-22: approved
2024-05-20: received
See all versions
Short URL
https://ia.cr/2024/773
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/773,
      author = {Max Duparc and Tako Boris Fouotsa},
      title = {{SQIPrime}: A dimension 2 variant of {SQISignHD} with non-smooth challenge isogenies},
      howpublished = {Cryptology ePrint Archive, Paper 2024/773},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/773}},
      url = {https://eprint.iacr.org/2024/773}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.