Are Isogenies Back on The Post Quantum Roadmap? Meet SQIsign
Are Isogenies Back on The Post Quantum Roadmap? Meet SQIsign
Isogenies were — for a while — the darling of the world of cryptography. They seemed to be a way to map our existing elliptic curve methods into a post-quantum cryptography world. But they crashed as they entered the last bend in the race to become the future foundation for a replacement for the ECDH (Elliptic Curve Diffie Hellman) method.
And, so, the NIST competition for PQC (Post Quantum Cryptography) was not a good time for isogenies, and where the SIKE method. reached the final round and was marked as being insecure:
And, so, the trailblazing isogeny methods — the great hope against the lattice methods — hit the bumpers. But, with SQIsign being submitted as the only isogeny method for PQC signing, there is still hope that isogenies will take its place as a real hope for a signature method in small keys and signature sizes.
Isogenies
The world of cryptography could be changed using a relatively technique: isogenies (“equal origin”). One of the best usages of isogenies is within quantum robust key exchange (using SIDH — Supersingular isogeny key exchange) An isogeny provides a mapping from one elliptic curve to another. The standard form of an elliptic curve equation is:
y²=x³+ax+b
In this case we will follow the example defined by on Page 277 of [1]:
This defines a mapping of:
E2: y²=x³+1132x+278
to:
E4: y²=x³+500x+1005
and using 𝔽_2003. The mapping from one curve to the next is then defined with:
In [1], we defined two points on E2 of P2=(1120,1391) and Q2=(894,1452) — see the sample run below. These then map to: P4=(565,302) and Q4=(1818,1002) on E4. E2 and E4 are isogenous, but not isomorphic (and where we cannot reverse the mapping from E4 to E2.
The following is the coding required for this isogeny [here]:
https://asecuritysite.com/pqc/iso2
A sample run is given next, and where the mapping of (1120,1391) on E2 is seen to map to (565,302) on E4:
Finite field: 2003y^2 = x^3+1132x+278 (mod 2003) y^2 = x^3 + 500x + 1005 (mod 2003)
(1102 911) (1465 1312) Check (1465 691)
(1103 536) (537 73) Check (537 73)
(1105 442) (1651 655) Check (1651 655)
(1108 1919) (807 1397) Check (807 606)
(1109 404) (1125 541) Check (1125 1462)
(1110 1804) (314 1163) Check (314 840)
(1111 611) (1144 1245) Check (1144 1245)
(1113 1931) (585 1278) Check (585 1278)
(1114 655) (953 1501) Check (953 1501)
(1116 1909) (1474 874) Check (1474 874)
(1119 1498) (1417 1598) Check (1417 405)
(1120 1391) (565 302) Check (565 302)
(1123 1277) (1769 301) Check (1769 1702)
(1124 1000) (1182 868) Check (1182 1135)
(1125 227) (1256 1497) Check (1256 1497)
(1127 147) (722 984) Check (722 984)
(1128 711) (1989 776) Check (1989 776)
(1130 850) (1973 681) Check (1973 681)
(1133 903) (1903 1692) Check (1903 1692)
(1134 770) (389 247) Check (389 1756)
(1135 503) (152 256) Check (152 1747)
(1136 463) (537 73) Check (537 1930)
(1140 573) (1998 655) Check (1998 1348)
(1143 786) (515 570) Check (515 1433)
(1147 1089) (565 302) Check (565 1701)SQIsign
But, don’t dismiss isogenies too soon. They are still a cool method, but where the parameter settings for SIKE let them down. Now, in the additional signature competition for PQC, they are back with [here][2]:
With the three current developing standards for PQC digital signatures, we see, that for 128-bit security, that Dilthium has a public key size of 1,312 bytes and a private key of 2,528 bytes, and a signature size of 2,420 bytes. SPHINCS+ improves on the key sizes, but has a relatively lare signature of 17,088 bytes:
Method Public key size Private key size Signature size Security level
------------------------------------------------------------------------------------------------------
Crystals Dilithium 2 (Lattice) 1,312 2,528 2,420 1 (128-bit) Lattice
Crystals Dilithium 3 1,952 4,000 3,293 3 (192-bit) Lattice
Crystals Dilithium 5 2,592 4,864 4,595 5 (256-bit) Lattice
Falcon 512 (Lattice) 897 1,281 690 1 (128-bit) Lattice
Falcon 1024 1,793 2,305 1,330 5 (256-bit) Lattice
Sphincs SHA256-128f Simple 32 64 17,088 1 (128-bit) Hash-based
Sphincs SHA256-192f Simple 48 96 35,664 3 (192-bit) Hash-based
Sphincs SHA256-256f Simple 64 128 49,856 5 (256-bit) Hash-based
RSA-2048 256 256 256
ECC 256-bit 64 32 256
SQIsign NIST-I 64 782 177
SQIsign NIST-III 96 1138 263
SQIsign NIST-V 128 1509 335But, look at the isogeny method. It has a 64 byte public key, a 782 byte private key, and the smaller of all the signatures of a 177 byte signature. If we could get isogenies to be secure, we can see that they would produce an even smaller signature than our existing public key encryption methods.
The downside of SQIsign is the complexity of the signing process, and where it can be relatively expensive in computing time to conduct. But the verification of the signature is fast and efficient:
Conclusions
The security proof for isogenies is known, but isogenies are still a realitively new method, and have not been analysed as much as lattice and hash-based methods. Overall, it is relative fast for verification, but the signing process is much slower than most of the competing PQC methods.
References
[1] Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., & Vercauteren, F. (2005). Handbook of elliptic and hyperelliptic curve cryptography. Chapman and Hall/CRC.
[2] De Feo, L., Kohel, D., Leroux, A., Petit, C., & Wesolowski, B. (2020). SQISign: compact post-quantum signatures from quaternions and isogenies. In Advances in Cryptology–ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part I 26 (pp. 64–93). Springer International Publishing.