Whatever Happened To Isogenies?
Whatever Happened To Isogenies?
WARNING: the SIKE algorithm is only for research purposes, insecure
And, so, isogenies looked to be the next great thing in cybersecurity in replacing ECDH for key exchange, and for us to move towards a post quantum world. For key sizes, it all looked great:
Type Public key size (B) Secret key size (B) Ciphertext size (B)
------------------------------------------------------------------------
Kyber512 800 1,632 768
Kyber738 1,184 2,400 1,088
Kyber1024 1,568 3,168 1,568
LightSABER 672 1,568 736
SABER 992 2,304 1,088
FireSABER 1,312 3,040 1,472
McEliece348864 261,120 6,452 128
McEliece460896 524,160 13,568 188
McEliece6688128 1,044,992 13,892 240
McEliece6960119 1,047,319 13,948 226
McEliece8192128 1,357,824 14,120 240
NTRUhps2048509 699 935 699
NTRUhps2048677 930 1,234 930
NTRUhps4096821 1,230 1,590 1,230
SIKEp434 330 44 346
SIKEp503 378 56 402
SIKEp751 564 80 596
Frodokem19888 9,616 19,888 9,720
Frodokem31296 15,632 31,296 15,744
Frodokem43088 21,520 43,088 21,632As we see, the private key, public key and ciphertext are all much smaller than Kyber. While the performance was not quite as good, and where SIKE was much slower than the lattice methods for Saber and Kyber:
scheme (implementation) level key generation encapsulation decapsulation
----------------------------------------------------------------------------
frodokem640aes (m4) 1 48,348,105 47,130 922 46,594,383
kyber512 (m4) 1 463,343 566,744 525,141
kyber768 (m4) 3 763,979 923,856 862,176
lightsaber (m4f) 1 361,687 513,581 498,590
saber (m4f) 3 654,407 862,856 835,122
ntruhps2048509 (m4f) 1 79,658,656 564,411 537,473
ntruhps2048677 (m4f) 3 143,734,184 821,524 815,516
sikep434 (m4) 1 48,264,129 78,911,465 84,276,911
sikep610 (m4) 3 119,480,622 219,632,058 221,029,700
mceliece348864f 1 1,430,811,294 582,199 2,706,681
mceliece348864 1 2,146,932,033 582,199 2,706,681And, 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)SIKE
Supersingular Isogeny Key Encapsulation (SIKE) is a post-quantum cryptography key encapsulation method for key exchange and is based on Supersingular Isogeny Diffie-Hellman (SIDH). It has a similar methodology to the Diffie-Hellman method but is quantum robust. Overall it was created by Luca de Feo and David Jao [2][paper] and enhanced by Craig Costello, Patrick Longa, and Michael Naehrig at Microsoft [3][paper].
It has one of the smallest key sizes for quantum robust crypto methods (where the public key can be compressed to 378 bytes and with a private key of 434 bytes):
In elliptic curve methods, the public key is only 32 bytes. It also supports perfect forward secrecy (PFS) and which stops the long-term key from being compromised, on the cracking of a single key (neither NTRU [here] Ring-LWS [here] are setup for PFS). Optimised code has shown the key parameters can be generated with 200 milliseconds, and the code has even been ported to ARM processors. The method is still relatively slow compared with elliptic curve methods (and requires around 50 million cycles of a processor). We can see in the following that SIKE-p434 is over 261 times slower than Kyber512 for key generation, 311 times slower for key encapsulation, and over 237 times slower for key decapsulation:
Creating an isogeny
If we have two elliptic curves (E1 and E2), we can create a function that maps a point (P) on E1 to a point Q on E2. This function is known as an isogeny. If we can map this function, every point on E1 can be mapped to E2. Our secret key is then the isogeny, and the public key is the elliptic curve. For key exchange, Bob and Alice mix their isogeny and the other side’s curve to generate a secret curve.
With isogenous elliptic curves we thus do not deal with a single elliptic curve but a family of them [paper]. An isogeny is then a map ϕ: E1 -> E2 and where points on the source curve E1 map to the target curve E2. It turns out that for every isogeny ϕ: E1 -> E2, there’s a dual isogeny ϕ: E2 -> E1, so we can say that two curves are isogenous if they’re linked by an isogeny:
Let’s take an example of Bob and Alice generating the same shared key (as we do with the Diffie-Hellman methods). First Alice has a starting curve of E0, and four points on that curve: PA, QA, PB, QB.
Alice then selects two random values ma and nA and keeps these secret. These will be scalar values.
She then determines a secret point Ra which is:
Ra=ma×Pa+na×Qa
This is her secret isogeny (ϕa). She then transforms Pb and Pq with this isogeny, and where Alice evaluates ϕA at point Pb, and at Qb.
She then sends Ea (her public key), and two transformed points (ϕA(Pb) and ϕA(Qb)) to Bob.
Bob does the same but swaps the a and b values Pa for Pb, Qa for Qb and vice versa. He will generate his own random values mb and nb. Bob calculates his secret: (ϕB).
The following defines the exchange [1]:
Next, Alice uses Ea, ϕa(Pa), ϕb(Qa) to construct an isogeny ϕ′a using ma×ϕa(Pa)+na×ϕb(qa).
Bob uses Ea, ϕa(Pb), ϕa(Qb) to construct an isogeny ϕ′b using mb×ϕa(Pb)+nb×ϕa(Qb).
Now ϕ′a maps to a curve Eab, and ϕ′b maps to Eba, and we can define them is isomorphic. After this, we can calculate a value from the j-invariant, and where j(Eab) is equal to j(Eba), and this will be the same shared secret between Bob and Alice. For a curve of y²=x³+px+q , the j-invariant is:
At the end of this, Bob and Alice will have the same key, and they will know that a quantum computer will not be able to crack it and that no previous keys can be cracked.
The following is the some code [here]:
namespace Sike
{
using Org.BouncyCastle.Pqc.Crypto.Sike;
using Org.BouncyCastle.Security;
class Program
{
static void Main(string[] args)
{
try {
var method="sikep434_compressed";
if (args.Length >0) method=args[0];
var random = new SecureRandom();
var keyGenParameters = new SikeKeyGenerationParameters (random, SikeParameters.sikep434);
if (method=="sikep434_compressed") keyGenParameters = new SikeKeyGenerationParameters(random, SikeParameters.sikep434_compressed);
else if (method=="sikep503") keyGenParameters = new SikeKeyGenerationParameters(random, SikeParameters.sikep503);
else if (method=="sikep503_compressed") keyGenParameters = new SikeKeyGenerationParameters(random, SikeParameters.sikep503_compressed);
else if (method=="sikep610") keyGenParameters = new SikeKeyGenerationParameters(random, SikeParameters.sikep610);
else if (method=="sikep610_compressed") keyGenParameters = new SikeKeyGenerationParameters(random, SikeParameters.sikep610_compressed);
else if (method=="sikep751") keyGenParameters = new SikeKeyGenerationParameters(random, SikeParameters.sikep751);
else if (method=="sikep751_compressed") keyGenParameters = new SikeKeyGenerationParameters(random, SikeParameters.sikep751_compressed);
var SikeKeyPairGenerator = new SikeKeyPairGenerator();
SikeKeyPairGenerator.Init(keyGenParameters);
var aKeyPair = SikeKeyPairGenerator.GenerateKeyPair();
var aPublic = (SikePublicKeyParameters)aKeyPair.Public;
var aPrivate = (SikePrivateKeyParameters)aKeyPair.Private;
var pubEncoded =aPublic.GetEncoded();
var privateEncoded = aPrivate.GetEncoded();
var bobSikeKemGenerator = new SikeKemGenerator(random);
var encapsulatedSecret = bobSikeKemGenerator.GenerateEncapsulated(aPublic);
var bobSecret = encapsulatedSecret.GetSecret();
var cipherText = encapsulatedSecret.GetEncapsulation();
var aliceSikeKemExtractor = new SikeKemExtractor(aPrivate);
var aliceSecret = aliceSikeKemExtractor.ExtractSecret(cipherText);
Console.WriteLine("Sike Engine:\t\t\t{0}",keyGenParameters.Parameters.Name);
Console.WriteLine("Sike Key Size:\t\t\t{0}",keyGenParameters.Parameters.DefaultKeySize);
Console.WriteLine("Private key length:\t\t{0} bytes",aPrivate.GetEncoded().Length);
Console.WriteLine("Public key length:\t\t{0} bytes",aPublic.GetEncoded().Length);
Console.WriteLine("Ciphertext length:\t\t{0} bytes",cipherText.Length);
Console.WriteLine("\nAlice private (first 50 bytes):\t{0}",Convert.ToHexString(aPrivate.GetEncoded())[..100]);
Console.WriteLine("Alice public (first 50 bytes):\t{0}",Convert.ToHexString(aPublic.GetEncoded())[..100]);
Console.WriteLine("\nCipher (first 50 bytes):\t{0}",Convert.ToHexString(cipherText)[..100]);
Console.WriteLine("\nBob secret:\t\t{0}",Convert.ToHexString(bobSecret));
Console.WriteLine("Alice secret:\t\t{0}",Convert.ToHexString(aliceSecret));
} catch (Exception e) {
Console.WriteLine("Error: {0}",e.Message);
}
}
}
}Sike P434 produces a 128-bit key size [here]:
Sike Engine: sikep434
Sike Key Size: 128
Private key length: 374 bytes
Public key length: 330 bytes
Ciphertext length: 346 bytes
Alice private (first 50 bytes): 3E4CB940F44A181D61615644140E30A78E308FF24B0AF36ADD86EEEE04D02BE9A95CA91C0757A6855FEC00007A8028AFB6C3
Alice public (first 50 bytes): 7A8028AFB6C3653AD5CFAC3AB78961B126D971E1D4C7EAFD586E4428E0325D3A3E3D6787F5AE9AAC85CEF1DF23F503745EFB
Cipher (first 50 bytes): 404D1C040BED897B31EEF1FC3993F5B407571EE060AE85C6354F7EFFCC436FF56CBCF1AFD0A415E3DA3FD22EE3E951ACABFC
Bob secret: 7E17D32E5C8DDFAB71FBFC26FEA4AE29
Alice secret: 7E17D32E5C8DDFAB71FBFC26FEA4AE29and for Sike p503, we have a 192-bit key size [here]:
Sike Engine: sikep503
Sike Key Size: 192
Private key length: 434 bytes
Public key length: 378 bytes
Ciphertext length: 402 bytes
Alice private (first 50 bytes): E00271024A34DB496262D002FC838ABC263600730DCB22A77BC1A6B274FE85477A9CA3B73D316B19EA1BE0902C94DECCCB81
Alice public (first 50 bytes): 89D27879E6CB2A5A409FCA16E11C7A0B493DB9D4A312A5E3F328DD2D3B1493915B735EE6DCB3C65D23F25F445251E8492E13
Cipher (first 50 bytes): 413AADAA134A10001011BD22A751E0B042B7993CBB33DAC74C235C8267293ABEA24B1126C3BE0AB097D2542C5AB89A3FA053
Bob secret: BF3244AB69AC2C3C6DA78CCCB343C54B270B9968F8057352
Alice secret: BF3244AB69AC2C3C6DA78CCCB343C54B270B9968F8057352and for Sike P751, we get a 256-bit key [here]:
Sike Engine: sikep751
Sike Key Size: 256
Private key length: 644 bytes
Public key length: 564 bytes
Ciphertext length: 596 bytes
Alice private (first 50 bytes): ED31E23CDC3C90679056842B863CB1C864837463388F083AF1D3DB4366193197644C490189D8EBBC5C2D847F368B6380EF24
Alice public (first 50 bytes): 007846E6DA04B6836DB811E96E5FB1E6E178E8E5B7589EF89DB5AD6B72375C63DBB19BF8CC448775C4B9E308D5D5E0F01FB5
Cipher (first 50 bytes): 4E26A3383C67BED6F69F5589F2BC5400A4FDE06AD5406C9457BE6A39B9815BB5867BDD5E969676FE7ECD26FAB3A34AF78F28
Bob secret: 615C19587497F12745000EEAC247963C9E299066A79C4BB6A7794F956DD69DFD
Alice secret: 615C19587497F12745000EEAC247963C9E299066A79C4BB6A7794F956DD69DFDSQIsign
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 335
But, 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.