Supersingular Isogeny Diffie-Hellman for Key Generation
Supersingular Isogeny Diffie-Hellman for Key Generation
A demonstration of Supersingular Isogeny Diffie-Hellman (SIDH) is here.
Introduction
Key exchange is a fundamental part of security on the Internet. Every time we connect to our company VPN, or to an HTTPs site, we negotiate a key with the other side. Public key encryption or key exchange methods are normally used to generate the unique key for our session. With public encryption encryption, the client can encrypt the session key that it wants with the public key of the server. With key exchange methods, the client and server talk openly between themselves, and, in the end, generate a share secret key. Unfortunately most current methods of public key encryption will be cracked by quantum computers, so we need to find an alternative, as all our previous, current and future secured communications (and in the storage of data) could be cracked.
SIDH is a quantum robust key-exchange method. It has a similar methodology to the Diffie-Hellman method, but is quantum robust. It was created by Luca de Feo, David Jao and Jerome Plut [2][paper] and enhanced by Craig Costello, Patrick Longa, and Michael Naehrig at Microsoft [3][paper], and has one of the smallest key sizes for quantum robust cryptography methods (where the public keys is 751 bytes). In elliptic curve methods the public key is only 32 bytes.
SIDH 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).
So what’s 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 isogeneous 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 E2E2. 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.
So how does it work?
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 select two random values mama and nA and keeps these secret. These will be scalar values. She then determines a secret point Ra which is:
Ra=ma×Pa+na×QaRa=ma×Pa+na×Qa
This is her secret isogeny (ϕaϕa).
She then transforms Pb and Pq with this isogeny, and where Alice evaluates ϕA at point Pb, and at Qb. Next 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 EaEa, ϕa(Pa), ϕb(Qa) to construct an isogeny ϕ′a using ma×ϕa(Pa)+na×ϕb(qa)ma×ϕa(Pa)+na×ϕb(qa).
Bob uses Ea, ϕa(Pb)), ϕa(Qb) to construct an isogeny ϕ′bϕb′ using mb×ϕa(Pb)+nb×ϕa(Qb)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.
Here is the code:
What does it look like?
A sample run is:
Prime number is: 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831
Alice's secret key:
435021324722526758847034025958405612706390148130772120768335274627785365385958811689883343175920069161606637496
Bob's secret key:
95820692860154366098762856681766620479692843995753083863291033379611568448592207349096668106836620847462125376925
Alice's keygen needs 638 multiplications by 4 and 1330 isogenies
Keysize of Alice's public key: 4496 bits
Alice's Public Key:
(9527934692687635054127921406831392226237904306404947505314723784572544634956292806969604907597293881220562350845978911245978403662002258322987463876566285818508802620457498685200775134798534644560154140325348363494257012628129, 1319218121514264043522088105219321186807482641840965949571969715997635718382456316075187471593771585996488046799475595629189279280710988612577139907205468870207124786687501889759900070622673052680224957161925146079760168159137)
(1674749232426940333847703163044640118590244742631866933290190155259879067379027591405510922030184871077969357836557567600359746354990464919095980583416031764009355983126260695650133789149398100533226179902820802519836504310547, 5185270356639748467358522382213424386196843877139266295642329353738549885358268785277415803459895231327605360707845871030393397756469863783073723841582248318656923893747085036329138515314970873324344489868234595561314647323425)
(2257905056024826074228726362391607003865492365423634409389433258919865968070453227769029250227660736544145568626455017743634591984210249288947795940138586655586462367358080863093729721675704922119827920871334922596802976787482, 2352248155188235091005652067330502188312796339662851120906412185752360838871558110257632339907796207388275008458447787976855826919270576990490891459453823118008104761257244634404653769794106148565730527929175124238240284518885)
Bob's keygen needs 811 multiplications by 3 and 1841 isogenies
Keysize of Bob's public key: 4498 bits
Alice's secret needs 638 multiplications by 4 and 772 isogenies
Alice's shared secret:
(9644805818383308077798354007642496223439194562661765503938942557095452492348685668055808819598953449904700578772389257923586867829274374340760028955774319105388805086072041646972932527433865767356550700983041247693919233920479, 9139706380661225318810248254600369325978534493499644212796790931701975828896911181742121311796503926909838119125478588945821660232356997111261364912691010976813747205022640406208146623710752390666626370458712839721129027178189)
Bob's secret needs 811 multiplications by 3 and 1124 isogenies
Bob's shared secret:
(9644805818383308077798354007642496223439194562661765503938942557095452492348685668055808819598953449904700578772389257923586867829274374340760028955774319105388805086072041646972932527433865767356550700983041247693919233920479, 9139706380661225318810248254600369325978534493499644212796790931701975828896911181742121311796503926909838119125478588945821660232356997111261364912691010976813747205022640406208146623710752390666626370458712839721129027178189)
keys are equal :)
Conclusions
SIDH is certainly one of the best methods around in replacing our existing key exchange methods, especially for ECDH (Elliptic Curve Diffie Hellman). It has relatively small keys (around 750 bytes compared with only 32 bytes for elliptic curve methods), and can act as a direct replacement for ECDH in SSL and VPN tunnels. While it gives an acceptable level of performance, it is still slow compared with existing public key methods (such as RSA and elliptic curve).
A demonstration of SIDH is here.
References
[1] https://www.academia.edu/32263564/Introduction_to_Supersingular_Isogeny_Diffie-Hellman
[2] De Feo, Luca, David Jao, and Jérôme Plût. “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies.” Journal of Mathematical Cryptology 8.3 (2014): 209–247.
[3] Costello, C., Longa, P., & Naehrig, M. (2016, August). Efficient algorithms for supersingular isogeny Diffie-Hellman. In Annual Cryptology Conference (pp. 572–601). Springer, Berlin, Heidelberg.