Supersingular Isogeny Diffie-Hellman (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 crypo methods (where the public keys is 751 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).
SIDH with Go |
Outline
The following defines the key sizes for the NIST KEM finalists (Kyber, SABER, NTRU, and McEliece) and SIDH:
Type Public key size (B) Secret key size (B) Ciphertext size (B) ------------------------------------------------------------------------ SIDH 564 48 564 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
Theory
If we have two elliptic curves (\(E_1\) and \(E_2\)), we can create a function that maps a point (P) on \(E_1\) to a point Q on \(E_2\). This function is known as an isogeny. If we can map this function, every point on \(E_1\) can be mapped to \(E_2\). 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 \(\phi\) : \(E_1\) -> \(E_2\) and where points on the source curve \(E_1\) map to the target curve \(E_2\). It turns out that for every isogeny \(\phi\): \(E_1\) -> \(E_2\), there's a dual isogeny \(\phi\): \(E_2\) -> \(E_1\), 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 \(E_0\), and four points on that curve: \(P_A\), \(Q_A\), \(P_B\), \(Q_B\).
Alice then select two random values \(m_a\) and \(n_A\) and keeps these secret. These will be scalar values.
She then determines a secret point \(R_a\) which is:
\(R_a = m_a \times P_a + n_a \times Q_a \)
This is her secret isogeny (\(\phi_a\)).
She then transforms \(P_b\) and \(P_q\) with this isogeny, and where Alice evaluates \(\phi_A\) at point \(P_b\), and at \(Q_b\).
She then sends \(E_a\) (her public key), and two transformed points (\(\phi_A(P_b)\) and \(\phi_A(Q_b)\)) to Bob.
Bob does the same, but swaps the a and b values \(P_a\) for \(P_b\), \(Q_a\) for \(Q_b\) and vice versa. He will generate his own random values \(m_b\) and \(n_b\). Bob calculates his secret: (\(\phi_B\)).
The following defines the exchange [1]:
Next, Alice uses \(E_a\), \(\phi_a(P_a)\), \(\phi_b(Q_a)\) to construct an isogeny \(\phi'_a\) using \(m_a \times \phi_a(P_a) + n_a \times \phi_b(q_a)\).
Bob uses \(E_a\), \(\phi_a(P_b)\), \(\phi_a(Q_b)\) to construct an isogeny \(\phi'_b\) using \(m_b \times \phi_a(P_b) + n_b \times \phi_a(Q_b)\).
Now \(\phi'a\) maps to a curve \(E_{ab}\), and \(\phi'_b\) maps to \(E_{ba}\), and we can define them is isomorphic. After this, we can calculate a value from the j-invariant, and where \(j(E_{ab})\) is equal to \(j(E_{ba})\), and this will be the same shared secret between Bob and Alice. For a curve of \(y^2 = x^3 + px + q\), the j-invariant is:
\(j = 1728 \frac{4p^3}{4p^3 + 27q^2}\)
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 (based on code [here]):
package main import ( "bytes" "crypto/rand" "fmt" "github.com/cloudflare/circl/dh/sidh" ) func main() { prvA := sidh.NewPrivateKey(sidh.Fp503, sidh.KeyVariantSidhA) pubA := sidh.NewPublicKey(sidh.Fp503, sidh.KeyVariantSidhA) prvB := sidh.NewPrivateKey(sidh.Fp503, sidh.KeyVariantSidhB) pubB := sidh.NewPublicKey(sidh.Fp503, sidh.KeyVariantSidhB) prvA.Generate(rand.Reader) prvA.GeneratePublicKey(pubA) prvB.Generate(rand.Reader) prvB.GeneratePublicKey(pubB) fmt.Printf("Alice private: %x\nAlice public: %x\n", *prvA, *pubA) fmt.Printf("Bob private: %x\nBob public: %x\n", *prvB, *pubB) ssA := make([]byte, prvA.SharedSecretSize()) ssB := make([]byte, prvA.SharedSecretSize()) prvA.DeriveSecret(ssA[:], pubB) prvB.DeriveSecret(ssB[:], pubA) fmt.Printf("\nAlice shared: %x\nBob shared: %x %t\n", ssA,ssB,bytes.Equal(ssA, ssB)) }
A sample run is:
Alice private: {{c000043c00 1} 263cd19c7ba407ff524f1fdca95fc727f6f60997e29a2284ec71ea66cfe84e03 } Alice public: {{c000044300 1} [{[ccf0d548ddf07cbd 41199ff6cb06cd1c 26edf09167369570 583653a5dfc8bf79 a6b60a3e51ccef10 17d09493788c062e ca28c8e362c0577c 23e670204b7c2e 0 0 0 0] [1bebcdfe9a68e613 480868650344ae50 a51d0c94c4c35c0f 54980dbbf9d3ba74 768be9dc86eabf2d 65e47814164d67e1 7aac13c267169ee2 17a7cb569c0222 0 0 0 0]} {[653a2eeb739adaef b1b3de9baffda8a9 202a5c21c7655fe8 8850ea3e6831eb71 29dda4197c2c8d11 5f1779c50c36189c 1cec4572be725d94 4930889adf411 0 0 0 0] [37923a29ede16f4f bc9e52fb88852e3a f527ace725bc46df 1531958d06ccbe80 ef6319126721093c 1ee175ee2e559c43 8c3e8021db814e9f 3b0367ba4f8c12 0 0 0 0]} {[d8048555f96155b9 6aa4f05706d9b136 ea7eb22094c79deb 2e0fd664eb5831c3 be1ae15f1852ce37 85c6a5e5ff1da308 8c9a2af5b4b4ffb2 2c1711f1a6e0ee 0 0 0 0] [a7f3bb6eb1540728 4f86a78ca0a8c2c1 91f9d1bb5fa83045 6b9b1db7059a6270 744d633664da3983 dcec49662fd57327 4dedf20e70b77e6e 3d870d02d854b7 0 0 0 0]}]} Bob private: {{c000044a00 2} 658bbaaca7c5d39687c172cd89e49ad259cccf3cf193dbb4e4f20329f17df90e } Bob public: {{c000045100 2} [{[779fee56c8ae5a6d 1df5384bf4e875b3 e66a92e0674a6ac1 f4b812e744881eb9 87ddb7b75e0b881a 29c082d639ad247e 48a8b98261502531 35183c3418bd05 0 0 0 0] [48d60db3d3e8712a 9077e0efb3e742a1 78beaf48b2f93b1b 659d965bfdb3c7ac 804f1aa60ea1f3ae 1088ffa2a895f753 4be4ae41ff327b65 1bbfc3a56f6530 0 0 0 0]} {[53a5828dfed30fe9 ea1d9d39e51e107b 8204909ecd6e91d5 12327b817eb67166 4fd743c1400448be 23f778a231181804 1f7a764eaa240b21 382c3b4b33f1e2 0 0 0 0] [b4b227800846b6b4 589b3c40a510bc57 d6433037c4ce52e5 17edcd6e7b4d3d85 3971a2b34b2e22ea 360e9744f9c3fb74 1e96c717031e7dfc 243bcdfdf1e32c 0 0 0 0]} {[a75c045e62dcf5a5 7be21cee7a50b78f a2208f93932edbdf bd8fbf4cec758ac9 3532672b58939839 3f93bb3a8080d007 b60db88f3e237ace 48dc08eaa29106 0 0 0 0] [847f1a0bf673891f 6d00f16ccc02c2f4 88f9428aec35d449 d29085baef95abb4 8adf6402ca39965b 3722f594787565d4 c174301f2e2ca47e 31ac701f6f997e 0 0 0 0]}]} Alice shared: 951774bd3663d61328044b79f0503813ad051691ef985b96529cab3d14c3c0ff0987f2b2e01863328df3240f0b84af97dc9df970b89e1fc5e2e8abaa7fa93c801538cec72bba6045cbf85056375294a0bd956b6fbeba6045f0e24961c7fcf689e7ee3036eb62976b41dc1794254c3418b2904a03b49f8758a78294e71223 Bob shared: 951774bd3663d61328044b79f0503813ad051691ef985b96529cab3d14c3c0ff0987f2b2e01863328df3240f0b84af97dc9df970b89e1fc5e2e8abaa7fa93c801538cec72bba6045cbf85056375294a0bd956b6fbeba6045f0e24961c7fcf689e7ee3036eb62976b41dc1794254c3418b2904a03b49f8758a78294e71223