SQIsignHD: New Dimensions in Cryptography

We introduce SQISignHD, a new post-quantum digital signature scheme inspired by SQISign. SQISignHD exploits the recent algorithmic breakthrough underlying the attack on SIDH, which allows to efficiently represent isogenies of arbitrary degrees as components of a higher dimensional isogeny. SQISignHD overcomes the main drawbacks of SQISign. First, it scales well to high security levels, since the public parameters for SQISignHD are easy to generate: the characteristic of the underlying field needs only be of the form 2 f 3 f -1. Second, the signing procedure is simpler and more efficient. Third, the scheme is easier to analyse, allowing for a much more compelling security reduction. Finally, the signature sizes are even more compact than (the already record-breaking) SQISign, with compressed signatures as small as 116 bytes for the post-quantum NIST-1 level of security. These advantages may come at the expense of the verification, which now requires the computation of an isogeny in dimension 4, a task whose optimised cost is still uncertain, as it has been the focus of very little attention.

Public set-up. We choose a prime p and a supersingular elliptic curve E 0 /F p 2 of known endomorphism ring O 0 ∼ = End(E 0 ) such that E 0 has smooth torsion defined over a small extension of F p 2 (of degree 1 or 2). In practice, one may use the curve E 0 : y 2 = x 3 + x (and p ≡ 3 mod 4).

The prover generates a random secret isogeny τ : E 0 -→ E A of fixed smooth degree D τ . Then, the prover publishes E A . Knowing τ , only