The End Game For a Post Quantum Computer Era … Isogenies?

We have a problem in cybersecurity… and it’s a big problem. Everything that uses our public key methods, needs to be removed within an era…

Photo by Daniele Levis Pelusi on Unsplash

The End Game For a Post Quantum Computer Era … Isogenies?

We have a problem in cybersecurity… and it’s a big problem. Everything that uses our public key methods, needs to be removed within an era of quantum computers. This includes checking the identity of the server that you are connecting to, and in the proof of your identity within online systems. The digital signatures that we produce for cryptocurrencies will also break. So we must start to migrate our systems over the next few years, and create as little disruption as possible. That’s why companies such as Amazon, Cloudflare, Google and Microsoft are already integrating post-quantum cryptography methods for key exchange and digital signatures. For this we need a core method and an alternative, just in case the core method has a weakness. For key exchange, Lattice methods, such as with SABER and Kyber, are likely to be the winners. But, for an alternative, the isogenies look to be an excellent contender, and SIKE is right up there.

Supersingular Isogeny Key Encapsulation (SIKE)

Supersingular Isogeny Key Encapsulation (SIKE) [4] 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. 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 crypto methods (where the public key is 378 bytes and the private key is 434 bytes).

In elliptic curve methods, the public key is only 32 bytes. It also supports perfect forward secrecy (PFS) and stops the long-term key from being compromised, on the cracking of a single key (neither NTRU [here] Ring-LWS [here] are set up 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). In this case, we will implement SIKEp434 (128-bit security), SIKEp503 and SIKEp751 (256-bit security).

The following defines the key sizes for Kyber, SABER, SIKE, NTRU and McEliece:

We can see that SIKE produces the smallest key and cipher sizes. In terms of performance on an ARM Cortex-M4 (32-bit RISC processor), the following is the number of cycles taken for various operations for key generation, key encapsulation and key decapsulation [1]:

We can see that SIKE has a poorer performance than the lattice methods, but it is likely that research will improve this.

Theory

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 as 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 y2=x3+px+q, the j-invariant is:

j=17284p34p3+27q2

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.

Coding

The following is an outline of the code [here]:

package main

// Based on examples at https://github.com/cloudflare/circl/tree/master/kem/kyber

import (
	"fmt"
	"math/rand"
	"os"
	"time"

	"github.com/cloudflare/circl/kem/schemes"
)

func main() {

	meth := "Kyber512"

	argCount := len(os.Args[1:])

	if argCount > 0 {
		meth = os.Args[1]
	}

	scheme := schemes.ByName(meth)
	rand.Seed(time.Now().Unix())

	var seed [48]byte
	kseed := make([]byte, scheme.SeedSize())
	eseed := make([]byte, scheme.EncapsulationSeedSize())
	for i := 0; i < 48; i++ {

		seed[i] = byte(rand.Intn(255))
	}

	g := NewDRBG(&seed)

	g.Fill(seed[:])

	g2 := NewDRBG(&seed)

	g2.Fill(kseed[:32])
	g2.Fill(kseed[32:])

	g2.Fill(eseed)
	pk, sk := scheme.DeriveKeyPair(kseed)
	ppk, _ := pk.MarshalBinary()
	psk, _ := sk.MarshalBinary()
	ct, ss, _ := scheme.EncapsulateDeterministically(pk, eseed)
	ss2, _ := scheme.Decapsulate(sk, ct)

	fmt.Printf("Method: %s \n", meth)
	fmt.Printf("Seed for key exchange: %X\n", seed)

	fmt.Printf("Public Key (pk) = %X (first 32 bytes)\n", ppk[:32])
	fmt.Printf("Private key (sk) = %X (first 32 bytes)\n", psk[:32])
	fmt.Printf("Cipher text (ct) = %X (first 32 bytes)\n", ct[:32])
	fmt.Printf("\nShared key (Bob):\t%X\n", ss)
	fmt.Printf("Shared key (Alice):\t%X", ss2)

	fmt.Printf("\n\nLength of Public Key (pk) = %d bytes \n", len(ppk))
	fmt.Printf("Length of Secret Key (pk)  = %d  bytes\n", len(psk))
	fmt.Printf("Length of Cipher text (ct) = %d  bytes\n", len(ct))

A sample run for SIKEp434 is [here]:

Method: SIKEp434 
Seed for key exchange: 5C654D1BABF98CDFEABE56B235EA52FDEC1839DB9FC0AA143B0E7D5235AB8925DB73BE4B125032579F2BEE16F06E1167
Public Key (pk) = C813D012F6A8A8E4873945170EE49010166D5EE1B27CC2EB7BC3E9149B900D44 (first 32 bytes)
Private key (sk) = D21D2742521EF908C4BB621F858E49F773D5184554F1CF5DFD1C889FD62763E5 (first 32 bytes)
Cipher text (ct) = D2B28A66405C896ACBA843E1E144969055D4F06614E04C5D639BE0EFE28543A7 (first 32 bytes)

Shared key (Bob):	38FEF101B08A344A5AA462D139666ACE
Shared key (Alice):	38FEF101B08A344A5AA462D139666ACE

Length of Public Key (pk) = 330 bytes 
Length of Secret Key (pk)  = 44  bytes
Length of Cipher text (ct) = 346  bytes
Keys are the same

A sample run for SIKEp434 is [here]:

Method: SIKEp503 
Seed for key exchange: 74A5E508A3187CBE7D005EA27B819D78CEDE8C0FE02FFCACE277CCC17BFB79C4046C3DFD2541BA463A87E2ABD8AEDC2F
Public Key (pk) = 7F109D0EFFE2120F808BD8BE935C1438CC0A39D1BCADA650F0C1A564F693429B (first 32 bytes)
Private key (sk) = 59A8853A5D2C582863F57554D5AE0EFFF76FFF6E812CBA12E6675738E1D86A2A (first 32 bytes)
Cipher text (ct) = F5BDA6BAB3F12CC74D912E8B0B975D04E1763B1902D32F70DE9E1391E1B8CDB9 (first 32 bytes)

Shared key (Bob):	C1D5E520E4571C5F595FA6D7ED1EDB59CFDF7E26563DDC63
Shared key (Alice):	C1D5E520E4571C5F595FA6D7ED1EDB59CFDF7E26563DDC63

Length of Public Key (pk) = 378 bytes 
Length of Secret Key (pk)  = 56  bytes
Length of Cipher text (ct) = 402  bytes

A sample run for SIKEp751 [here]:

Method: SIKEp751 
Seed for key exchange: E7B1B58ED1098C6F1D91ACE00B7FBB4165ADCCBC17129992C42DBC5EAF6B628936701573D6C305DBCFB1259EAB78C6AB
Public Key (pk) = C3EC4A47C4DA001F484F6E30F2E479F7F33F470225ECFE0F63C6F914CDA6C652 (first 32 bytes)
Private key (sk) = 05A309A4CCF5A77BE8BF9CB76AC8AE31BA3F40813A2616484CDF7424D679E42D (first 32 bytes)
Cipher text (ct) = 7C43E5C0D906DA84F626E037099022916ABE481B39ABD01D84B6269642F95328 (first 32 bytes)

Shared key (Bob):	A81E89A4B679B3CAB207B0E5FE8C65985FC83D3C50144DC8D36A8678C5EDB5E7
Shared key (Alice):	A81E89A4B679B3CAB207B0E5FE8C65985FC83D3C50144DC8D36A8678C5EDB5E7

Length of Public Key (pk) = 564 bytes 
Length of Secret Key (pk)  = 80  bytes
Length of Cipher text (ct) = 596  bytes

Conclusions

And there you go … SIKE … a great alternative to lattice methods. While their key and cipher sizes wins over lattice methods, they still struggle to complete with them on performance. But, research will improve things, and they could soon rival the lattice methods.

References

[1] Costello, C. (2017). An introduction to supersingular isogeny-based cryptography. ECC. [paper]

[2] Jao, D., & De Feo, L. (2011, November). Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In International Workshop on Post-Quantum Cryptography (pp. 19–34). Springer, Berlin, Heidelberg. [paper]

[3] Costello, C., Longa, P., & Naehrig, M. (2016, August). Efficient algorithms for supersingular isogeny Diffie-Hellman. In Annual International Cryptology Conference (pp. 572–601). Springer, Berlin, Heidelberg. [paper]

[4] Douglas Stebila, Introduction to post-quantum cryptography and learning with errors, Summer School on real-world crypto and privacy, Šibenik, Croatia, June 11, 2018 [slides].