Key exchange protocol using supersingular isogeny

Diffie-Hellman Protocol Using Supersingular Isogeny Supersingular isogeny Diffie – Hellman key exchange, SIDH) is a post-quantum cryptographic algorithm that allows two or more parties to obtain a shared secret key using an unprotected communication channel. This is an analog of the Diffie-Hellman protocol , based on wandering in a supersingular isogenic graph that is designed to withstand a cryptanalytic attack by an adversary owning a quantum computer . Of all post-quantum key exchange protocols, SIDH has the shortest key length; with compression in mind, SIDH uses a 2688-bit ^[1] public key at a 128-bit quantum cryptographic level . SIDH also differs from other similar systems, such as NTRU and Ring-LWE, in that it maintains perfect direct secrecy , which ensures that session keys obtained using a set of long-term keys will not be compromised when one of the long-term keys is compromised. These properties of SIDH make it one of the candidates for replacing Diffie-Hellman (DHE) and Diffie-Hellman on elliptic curves (ECDHE), which are used to protect data transmitted over the network.

Introduction

For some classes of problems, algorithms running on a quantum computer are able to achieve less time complexity than when executed on a classical computer. The use of quantum algorithms significantly affects open cryptography . For example, the Shore algorithm can decompose an integer N in polynomial time , while the most efficient factorizing classical algorithm, the general method of sifting a number field , works in sub-exponential time . At the same time, RSA security is at risk, based on the complexity of the task of factoring integers . The Shore algorithm can also effectively solve the discrete logarithm problem, the complexity of which determines the security of Diffie-Hellman , Diffie-Hellman on elliptic curves , ECDSA , Curve2551 , ed25519 and El-Gamal . Thus, both the factorization of integers and the discrete logarithm problem will be easily solvable on large enough quantum computers. Currently, post-quantum cryptography is being developed, which uses algorithms that are independent of quantum computing, that is, resistant to quantum attacks. ^[2]

SIDH was created by De Feo, Jao and Plut in 2011 ^[3] . It uses standard operations on elliptic curves and is not patented. SIDH provides perfect direct secrecy and does not rely on the security of long-term private keys. Direct secrecy improves the long-term security of encrypted connections, helps protect against mass surveillance and reduces the impact of vulnerabilities such as Heartbleed . ^[4] ^[5]

Algorithm Description

j-invariant of the elliptic curve given by the equation $y^{2}=x^{3}+ax+b$ ${\ displaystyle y ^ {2} = x ^ {3} + ax + b}$ has the form:

j(E)=1728{\frac {4a^{3}}{4a^{3}+27b^{2}}}

{\ displaystyle j (E) = 1728 {\ frac {4a ^ {3}} {4a ^ {3} + 27b ^ {2}}}}

Isomorphic curves have the same j-invariant; over an algebraically closed field, two curves with the same j-invariant are isomorphic.

SIDH uses many supersingular elliptic curves and their isogenies. For isomorphic curves, it is worth considering isogeny between different classes of isomorphic curves. Isogeny $\phi \colon E\to E'$ ${\ displaystyle \ phi \ colon E \ to E '}$ between elliptical curves $E$ ${\ displaystyle E}$ and $E^{'}$ ${\ displaystyle E '}$ Is a rational map , which is a homomorphism. If a $\phi$ ${\ displaystyle \ phi}$ is separable , then it is determined by its core up to an isomorphism of the curve $E^{'}$ ${\ displaystyle E '}$ .

SIDH requires a field characteristic — a prime number of type $p=l_{A}^{e_{A}}\cdot l_{B}^{e_{B}}\cdot f\mp 1$ ${\ displaystyle p = l_ {A} ^ {e_ {A}} \ cdot l_ {B} ^ {e_ {B}} \ cdot f \ mp 1}$ , with small primes $l_{A}$ ${\ displaystyle l_ {A}}$ and $l_{B}^{e_{B}}$ ${\ displaystyle l_ {B} ^ {e_ {B}}}$ large degrees $e_{A}$ ${\ displaystyle e_ {A}}$ and $e_{B}$ ${\ displaystyle e_ {B}}$ and a small factor $f$ ${\ displaystyle f}$ ; as well as a supersingular curve $E$ ${\ displaystyle E}$ given over $\mathbb {F} _{p^{2}}$ ${\ displaystyle \ mathbb {F} _ {p ^ {2}}}$ . Such a curve has two large torsion subgroups , $E[l_{A}^{e_{A}}]$ ${\ displaystyle E [l_ {A} ^ {e_ {A}}]}$ and $E[l_{B}^{e_{B}}]$ ${\ displaystyle E [l_ {B} ^ {e_ {B}}]}$ which are intended for Alice and Bob, respectively. Each side starts the protocol by selecting a (secret) random cyclic subgroup from the corresponding torsion subgroup and calculating the corresponding (secret) isogeny. Then they exchange the equations of the transformed curves, which are the results of the action of their isogenies on the curve $E$ ${\ displaystyle E}$ , as well as the values of their isogeny, calculated by the torsion group of the other side. This allows both sides to secretly calculate new isogeny from $E$ ${\ displaystyle E}$ whose nuclei are co-generated using two secret cyclic subgroups. Since the kernels of these isogenies are consistent, their new transformed curves are isomorphic. In this case, the joint j-invariant of the transformed curves can be used as a necessary common secret.

More information on this topic can be found in De Feo's article "Mathematics of Isogeny Based Cryptography." ^[6]

Cryptographic Strength

Many isogenies of supersingular elliptic curves together with the composition form a non-Abelian group, and SIDH security is based on this non-Abelian structure. ^[3] SIDH security is closely related to the problem of finding isogenic mappings between two supersingular elliptic curves having the same number of points. De Feo, Jao and Plut have suggested that SIDH security will $O(p^{\frac {1}{4}})$ ${\ displaystyle O (p ^ {\ frac {1} {4}})}$ for a classic computer and $O(p^{\frac {1}{6}})$ ${\ displaystyle O (p ^ {\ frac {1} {6}})}$ for quantum. It turns out that SIDH with a 768-bit prime number will have a cryptographic strength of 128 bits. ^[3] In 2014, when studying the problem of isogenic mappings, Delfs and Galbraith confirmed $O(p^{\frac {1}{4}})$ ${\ displaystyle O (p ^ {\ frac {1} {4}})}$ security for a classic computer. ^[7] Resilience Level $O(p^{\frac {1}{4}})$ ${\ displaystyle O (p ^ {\ frac {1} {4}})}$ has also been confirmed by Biasse, Jao and Sankar, and by Galbraith, Petit, Shani, and Bo Ti. ^[8] ^[9]

Efficiency

In the process of exchanging keys, each of the parties A and B will be transferred $2({\text{mod}}p^{2})$ ${\ displaystyle 2 ({\ text {mod}} p ^ {2})}$ coefficients defining an elliptic curve, and 2 points of the elliptic curve. Each elliptic curve coefficient requires $\log _{2}p^{2}$ ${\ displaystyle \ log _ {2} p ^ {2}}$ bit. Each point of an elliptic curve can be transmitted for $\log _{2}p^{2}+1$ ${\ displaystyle \ log _ {2} p ^ {2} +1}$ bit. Total transmitted $8\log _{2}p+2$ ${\ displaystyle 8 \ log _ {2} p + 2}$ bit. It turns out 6144 bits for the 768-bit field characteristic length $p$ ${\ displaystyle p}$ (128-bit cryptographic strength). However, this number can be reduced to 2640 bits (330 bytes) using the key compression technique, the latest version of which can be found in the work of Costello, Jao, Longa, Naehrig, Renes and Urbanik. ^[10] Based on the compression technique, SIDH has bandwidth requirements close to traditional 3072-bit RSA certification or Diffie-Hellman key exchange. Due to the small key length requirements, SIDH can be used in the context of a limited available space, for example, in Bitcoin and Tor . The data cell size in Tor should be less than 517 bytes and SIDH with a key length of 330 bytes fit there, while NTRUEncrypt must exchange approximately 600 bytes in order to achieve a 128-bit security level and cannot be used in Tor without increasing data cell size. ^[eleven]

In 2014, researchers from the University of Waterloo developed a software implementation of SIDH. It was launched on an x86-64 processor with a frequency of 2.4 GHz. For a characteristic length of 768 bits, they were able to perform key exchange in 200 milliseconds, showing the practicality of calculating SIDH. ^[12]

In 2016, researchers from Microsoft published software for SIDH, which works in constant time (thereby resistant to time attacks ) and is the most effective implementation to date. ^[13] Their implementation can be found here .

In 2016, researchers from Florida Atlantic University developed an effective implementation of SIDH for ARM architecture and made comparisons for affine and projective coordinates. ^[14] ^[15] In 2017, the first FPGA implementation of SIDH was developed at the same university. ^[sixteen]

Diffie-Hellman Protocol Using Supersingular Isogeny

While some SIDH steps use complex isogeny calculations, a general understanding of SIDH for parties A and B is quite simple for those familiar with the Diffie-Hellman protocol or its variant on elliptic curves.

Domain Settings

The following domain parameters are used, which can be accessible to everyone in the community or the parties can provide them at the beginning of the session.

Field characteristic - a prime number of the form $p=w_{A}^{e_{A}}\cdot w_{B}^{e_{B}}\cdot f\pm 1.$ ${\ displaystyle p = w_ {A} ^ {e_ {A}} \ cdot w_ {B} ^ {e_ {B}} \ cdot f \ pm 1.}$
Supersingular Elliptic Curve $E$ ${\ displaystyle E}$ above $\mathbb {F} _{p^{2}}$ ${\ displaystyle \ mathbb {F} _ {p ^ {2}}}$ .
Fixed points $P_{A},Q_{A},P_{B},Q_{B}$ ${\ displaystyle P_ {A}, Q_ {A}, P_ {B}, Q_ {B}}$ on an elliptic curve $E$ ${\ displaystyle E}$ .
Points $P_{A}$ ${\ displaystyle P_ {A}}$ and $Q_{A}$ ${\ displaystyle Q_ {A}}$ have order $(w_{A})^{e_{A}}$ ${\ displaystyle (w_ {A}) ^ {e_ {A}}}$ , but $P_{B}$ ${\ displaystyle P_ {B}}$ and $Q_{B}$ ${\ displaystyle Q_ {B}}$ order $(w_{B})^{e_{B}}$ ${\ displaystyle (w_ {B}) ^ {e_ {B}}}$ .

Key Exchange

When exchanging keys, each of the sides A and B should generate isogeny from a common elliptic curve $E$ ${\ displaystyle E}$ . This is done by generating a random point at which the core of their isogeny will be. The base vectors for this kernel will be pairs of points $P_{A}$ ${\ displaystyle P_ {A}}$ , $Q_{A}$ ${\ displaystyle Q_ {A}}$ and $P_{B}$ ${\ displaystyle P_ {B}}$ , $Q_{B}$ ${\ displaystyle Q_ {B}}$ respectively. Using different pairs of points ensures that the parties generated different, non-commuting isogenies. Random Point ( $R_{A}$ ${\ displaystyle R_ {A}}$ , or $R_{B}$ ${\ displaystyle R_ {B}}$ ) in the core of isogeny is generated as a random linear combination of points $P_{A}$ ${\ displaystyle P_ {A}}$ , $Q_{A}$ ${\ displaystyle Q_ {A}}$ and points $P_{B}$ ${\ displaystyle P_ {B}}$ , $Q_{B}$ ${\ displaystyle Q_ {B}}$ .

Using $R_{A}$ ${\ displaystyle R_ {A}}$ , or $R_{B}$ ${\ displaystyle R_ {B}}$ , sides A and B apply the Velu formula to obtain isogeny $\phi _{A}$ ${\ displaystyle \ phi _ {A}}$ and $\phi _{B}$ ${\ displaystyle \ phi _ {B}}$ respectively. After that, they calculate the images of pairs of points $P_{A}$ ${\ displaystyle P_ {A}}$ , $Q_{A}$ ${\ displaystyle Q_ {A}}$ or $P_{B}$ ${\ displaystyle P_ {B}}$ , $Q_{B}$ ${\ displaystyle Q_ {B}}$ under the action of isogeny $\phi _{A}$ ${\ displaystyle \ phi _ {A}}$ and $\phi _{B}$ ${\ displaystyle \ phi _ {B}}$ respectively.

As a result, A and B have two pairs of points $\phi _{B}(P_{A})$ ${\ displaystyle \ phi _ {B} (P_ {A})}$ , $\phi _{B}(Q_{A})$ ${\ displaystyle \ phi _ {B} (Q_ {A})}$ and $\phi _{A}(P_{B})$ ${\ displaystyle \ phi _ {A} (P_ {B})}$ , $\phi _{A}(Q_{B})$ ${\ displaystyle \ phi _ {A} (Q_ {B})}$ respectively. Now A and B exchange the counted pairs of points through the communication channel.

A and B use pairs of points obtained from the other side as a basis for the core of their new isogeny. Taking the same linear coefficients that were previously used to generate a random point ( $R_{A}$ ${\ displaystyle R_ {A}}$ , or $R_{B}$ ${\ displaystyle R_ {B}}$ ), each of them generate a point in the core of the isogeny that they want to build. Each side calculates points $S_{BA}$ ${\ displaystyle S_ {BA}}$ and $S_{AB}$ ${\ displaystyle S_ {AB}}$ and uses the Velu formula to construct new isogeny.

To complete the key exchange, A and B calculate the coefficients of two new elliptic curves with two new isogenies and calculate their j-invariant. If no errors occurred during the transfer, the j-invariant of the curve constructed by A must be equal to the j-invariant of the curve constructed by B.

A key exchange between parties A and B using SIDH can be written as follows:

1A. A generates two random integers $m_{A},n_{A}<(w_{A})^{e_{A}}.$ ${\ displaystyle m_ {A}, n_ {A} <(w_ {A}) ^ {e_ {A}}.}$

2A. A generates $R_{A}:=m_{A}\cdot (P_{A})+n_{A}\cdot (Q_{A}).$ ${\ displaystyle R_ {A}: = m_ {A} \ cdot (P_ {A}) + n_ {A} \ cdot (Q_ {A}).}$

3A. A uses a point $R_{A}$ ${\ displaystyle R_ {A}}$ to build isogeny $\phi _{A}:E\rightarrow E_{A}$ ${\ displaystyle \ phi _ {A}: E \ rightarrow E_ {A}}$ and curve $E_{A}$ ${\ displaystyle E_ {A}}$ isogenic $E .$ ${\ displaystyle E.}$

4A. A applies $\phi _{A}$ ${\ displaystyle \ phi _ {A}}$ to $P_{B}$ ${\ displaystyle P_ {B}}$ and $Q_{B}$ ${\ displaystyle Q_ {B}}$ to get two points on $E_{A}:\phi _{A}(P_{B})$ ${\ displaystyle E_ {A}: \ phi _ {A} (P_ {B})}$ and $\phi _{A}(Q_{B}).$ ${\ displaystyle \ phi _ {A} (Q_ {B}).}$

5A. A passes B $E_{A},\phi _{A}(P_{B})$ ${\ displaystyle E_ {A}, \ phi _ {A} (P_ {B})}$ and $\phi _{A}(Q_{B}).$ ${\ displaystyle \ phi _ {A} (Q_ {B}).}$

1B - 4B: Similar to A1 - A4, replacing A with B (and vice versa).

5B. B transmits A $E_{B},\phi _{B}(P_{A})$ ${\ displaystyle E_ {B}, \ phi _ {B} (P_ {A})}$ and $\phi _{B}(Q_{A}).$ ${\ displaystyle \ phi _ {B} (Q_ {A}).}$

6A. A has $m_{A},n_{A},\phi _{B}(P_{A})$ ${\ displaystyle m_ {A}, n_ {A}, \ phi _ {B} (P_ {A})}$ and $\phi _{B}(Q_{A})$ ${\ displaystyle \ phi _ {B} (Q_ {A})}$ . A finds $S_{BA}:=m_{A}(\phi _{B}(P_{A}))+n_{A}(\phi _{B}(Q_{A})).$ ${\ displaystyle S_ {BA}: = m_ {A} (\ phi _ {B} (P_ {A})) + n_ {A} (\ phi _ {B} (Q_ {A})).}$

7A. A uses $S_{BA}$ ${\ displaystyle S_ {BA}}$ to build isogeny $\psi _{BA}$ ${\ displaystyle \ psi _ {BA}}$ .

8A. A uses $\psi _{BA}$ ${\ displaystyle \ psi _ {BA}}$ to build an elliptic curve $E_{BA}$ ${\ displaystyle E_ {BA}}$ which is isogenic $E$ ${\ displaystyle E}$ .

9A. A computes $K:={\text{ j-invariant }}(j_{BA})$ ${\ displaystyle K: = {\ text {j-invariant}} (j_ {BA})}$ crooked $E_{BA}$ ${\ displaystyle E_ {BA}}$ .

6B. Similarly, B has $m_{B},n_{B},\phi _{A}(P_{B})$ ${\ displaystyle m_ {B}, n_ {B}, \ phi _ {A} (P_ {B})}$ and $\phi _{A}(Q_{B})$ ${\ displaystyle \ phi _ {A} (Q_ {B})}$ . Finds $S_{AB}=m_{B}(\phi _{A}(P_{B}))+n_{B}(\phi _{A}(Q_{B}))$ ${\ displaystyle S_ {AB} = m_ {B} (\ phi _ {A} (P_ {B})) + n_ {B} (\ phi _ {A} (Q_ {B}))}$ .

7B. B uses $S_{AB}$ ${\ displaystyle S_ {AB}}$ to build isogeny $\psi _{AB}$ ${\ displaystyle \ psi _ {AB}}$ .

8B. B uses $\psi _{AB}$ ${\ displaystyle \ psi _ {AB}}$ to build an elliptic curve $E_{AB}$ ${\ displaystyle E_ {AB}}$ which is isogenic $E$ ${\ displaystyle E}$ .

9B. B computes $K:={\text{ j-invariant }}(j_{AB})$ ${\ displaystyle K: = {\ text {j-invariant}} (j_ {AB})}$ crooked $E_{AB}$ ${\ displaystyle E_ {AB}}$ .

The curves $E_{AB}$ ${\ displaystyle E_ {AB}}$ and $E_{BA}$ ${\ displaystyle E_ {BA}}$ must have the same j-invariant. Function from $K$ ${\ displaystyle K}$ used as a shared key. ^[3]

Parameters example

The following parameters were used by De Feo et al .: ^[3]

p = field characteristic (prime) for key exchange with w _A = 2, w _B = 3, e _A = 63, e _B = 41, and f = 11. It turns out p = (2 ⁶³ · 3 ⁴¹ · 11) - one.

E ₀ = main (initial) curve for key exchange = y ² = x ³ + x

Luca De Feo, one of the authors of the article describing key exchange, has published a software implementation of key exchange for these and other parameters. ^[17]

Similar systems

The predecessor of SIDH was a method published in 2006 by Rostovtsev and Stolbunov. They created the first Diffie-Hellman analog using isogeny of elliptic curves. Unlike the De Feo, Jao, and Plut method, the Rostovtsev and Stolbunov method used ordinary elliptic curves ^[18] and was subject to subexponential quantum attacks. ^[nineteen]

In March 2014, researchers from the Chinese State Key Lab for Integrated Service Networks and Xidian University expanded SIDH's security to a digital signature form with strictly defined verifiers. ^[20] In October 2014, researchers Jao and Soukharev from Waterlu University presented an alternative way to get explicit signatures with given verifiers using elliptic curves. ^[21]

Cryptographic attacks

Active Attack

Active attacks are a standard type of attack on cryptosystems with a static private key. If A has a fixed private key $(m_{A},n_{A})$ ${\ displaystyle (m_ {A}, n_ {A})}$ then attacker B can send $(E,P_{B},Q_{B})$ ${\ displaystyle (E, P_ {B}, Q_ {B})}$ and A will calculate isogeny $\phi :E\rightarrow E'$ ${\ displaystyle \ phi: E \ rightarrow E '}$ with core $<m_{A}P+n_{A}Q>$ ${\ displaystyle <m_ {A} P + n_ {A} Q>}$ . An attacker may try to calculate the private key. $(m_{A},n_{A})$ ${\ displaystyle (m_ {A}, n_ {A})}$ knowing $E^{'}$ ${\ displaystyle E '}$ . To prevent this type of attack, you need to check the correctness $(E,P_{B},Q_{B})$ ${\ displaystyle (E, P_ {B}, Q_ {B})}$ : ^[13]

$E$ ${\ displaystyle E}$ is a supersingular elliptic curve,
$P_{B}$ ${\ displaystyle P_ {B}}$ and $Q_{B}$ ${\ displaystyle Q_ {B}}$ lie on this curve, have the correct order and are independent.

To verify the correctness $(E,P_{B},Q_{B})$ ${\ displaystyle (E, P_ {B}, Q_ {B})}$ Weil pairing condition can be used

e_{2^{n}}(\phi _{B}(P_{A}),\phi _{B}(Q_{A}))=e_{2^{n}}(P_{A},Q_{A})^{3^{m}}.

{\ displaystyle e_ {2 ^ {n}} (\ phi _ {B} (P_ {A}), \ phi _ {B} (Q_ {A})) = e_ {2 ^ {n}} (P_ { A}, Q_ {A}) ^ {3 ^ {m}}.}

However, this check will not be able to protect against all adaptive attacks. ^[9]

Adaptive Attack

Galbraith, Petit, Shani, and Ti showed that for static private keys there is an adaptive attack that requires less than log 2 (p) calls to A, which will be tested by Weil conjugation and checked for the degree of isogeny. In this attack, the attacker B iteratively finds the bits of the secret key A, selecting the transmitted parameters and looking at the answer A. However, the verification method proposed by Kirkwood can recognize this attack. ^[9]

Kirkwood Verification Method

The verification method proposed by Kirkwood et al. ^[22] uses the Fujisaki-Okamoto transform ^[23] . The idea of this method is that the parties exchange keys, and then exchange encrypted random numbers that were used to generate the key to confirm the correctness of the key exchange. The protocol can be written as follows:

1. B receives a static key A $(E_{A},\phi _{A}(P_{B}),\phi _{A}(Q_{B}))$ ${\ displaystyle (E_ {A}, \ phi _ {A} (P_ {B}), \ phi _ {A} (Q_ {B}))}$ .

2. B selects a random number $r_{B}$ ${\ displaystyle r_ {B}}$ and gets the private key using the pseudo-random function G:

(b_{1},b_{2})={\text{G}}(r_{B})

{\ displaystyle (b_ {1}, b_ {2}) = {\ text {G}} (r_ {B})}

.

Then B computes the message $(E_{B},\phi _{B}(P_{A}),\phi _{B}(Q_{A}))$ ${\ displaystyle (E_ {B}, \ phi _ {B} (P_ {A}), \ phi _ {B} (Q_ {A}))}$ where $\phi _{B}$ ${\ displaystyle \ phi _ {B}}$ $<[b_{1}]P_{B}+[b_{2}]Q_{B}>$ ${\ displaystyle <[b_ {1}] P_ {B} + [b_ {2}] Q_ {B}>}$ .

3. B gets a shared secret $E_{AB}$ ${\ displaystyle E_ {AB}}$ of $(E_{A},\phi _{A}(P_{B}),\phi _{A}(Q_{B}))$ ${\ displaystyle (E_ {A}, \ phi _ {A} (P_ {B}), \ phi _ {A} (Q_ {B}))}$ and $(b_{1},b_{2})$ ${\ displaystyle (b_ {1}, b_ {2})}$ and calculates the session $(SK)$ ${\ displaystyle (SK)}$ and test $(VK)$ ${\ displaystyle (VK)}$ keys using the K function:

SK|VK={\text{K}}(j(E_{AB}))

{\ displaystyle SK | VK = {\ text {K}} (j (E_ {AB}))}

.

4. B transmits A $(E_{B},\phi _{B}(P_{A}),\phi _{B}(Q_{A}))$ ${\ displaystyle (E_ {B}, \ phi _ {B} (P_ {A}), \ phi _ {B} (Q_ {A}))}$ and $c_{B}={\text{ENC}}_{VK}(r_{B}\oplus SK)$ ${\ displaystyle c_ {B} = {\ text {ENC}} _ {VK} (r_ {B} \ oplus SK)}$ .

5. From $(a_{1},a_{2})$ ${\ displaystyle (a_ {1}, a_ {2})}$ and $(E_{B},\phi _{B}(P_{A}),\phi _{B}(Q_{A}))$ ${\ displaystyle (E_ {B}, \ phi _ {B} (P_ {A}), \ phi _ {B} (Q_ {A}))}$ And gets $E'_{AB}$ ${\ displaystyle E '_ {AB}}$ , and then $(SK')$ ${\ displaystyle (SK ')}$ and $(VK')$ {\ displaystyle (VK ')} .

6. A computes

r'_{B}={\text{Dec}}_{VK'}(c_{B})\oplus SK'.

{\ displaystyle r '_ {B} = {\ text {Dec}} _ {VK'} (c_ {B}) \ oplus SK '.}

For a hypothetical number $r'_{B}$ ${\ displaystyle r '_ {B}}$ And he can re-perform all operations B. If the resulting message matches $(E_{B},\phi _{B}(P_{A}),\phi _{B}(Q_{A}))$ ${\ displaystyle (E_ {B}, \ phi _ {B} (P_ {A}), \ phi _ {B} (Q_ {A}))}$ that B originally sent, then A completes the protocol and uses $SK=SK'$ ${\ displaystyle SK = SK '}$ for further communication with B. If messages differ, the protocol is interrupted with an error, without further communication.

When using this protocol, B opens his private key A, so he has to change it after each check. This verification method can be applied to both key exchange protocols and encryption protocols. ^[9]

Change Attack

Modified attacks are a standard type of attack that involves physical access to a device that uses a private key. These attacks are based on the ability of the attacking party to distort the execution of protocol A, forcing them to make errors in the calculations.

Cycle Break Attack

This attack uses an iterative structure for computing isogeny. You can make a change that forces A to calculate isogeny only partially, revealing information about the secret key $(a_{1},a_{2})$ ${\ displaystyle (a_ {1}, a_ {2})}$ . This attack cannot be found by the Kirkwood scan, because the attacker uses the correct data. Private key A is opened bitwise, the protocol completion status is used when the calculation of the curve by side A successfully interrupts the calculation. The complexity of this attack is approximately $\log _{2}p/\mu$ ${\ displaystyle \ log _ {2} p / \ mu}$ where $\mu$ ${\ displaystyle \ mu}$ - probability of successful interruption of calculations. ^[24]

Links

↑ Costello, Craig; Jao, David; Longa, Patrick; Naehrig, Michael; Renes, Joost; Urbanik, David. Efficient compression of SIDH public keys (unspecified) . - 2016 .-- October 4.
↑ Utsler, Jim Quantum Computing Might Be Closer Than Previously Thought (neopr.) . IBM (September 2013). Date of treatment May 27, 2013.
↑ ¹ ² ³ ⁴ ⁵ De Feo, Luca Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies (neopr.) . PQCrypto 2011 . Springer Date of treatment May 4, 2014.
↑ Higgins, Parker Long Term Privacy with Forward Secrecy (neopr.) . Electronic Frontier Foundation. Date of treatment May 4, 2014.
↑ Zhu, Yan Why the Web Needs Perfect Forward Secrecy More Than Ever (neopr.) . Electronic Frontier Foundation. Date of treatment May 4, 2014.
↑ De Feo, Luca (2017), "Mathematics of Isogeny Based Cryptography", arΧiv : 1711.04062
↑ Delfs, Christina & Galbraith (29 Oct 2013), "Computing isogenies between supersingular elliptic curves over F_p", arΧiv : 1310.7789
↑ biasse A quantum algorithm for computing isogenies between supersingular elliptic curves (neopr.) . CACR. Date of treatment December 11, 2016.
↑ ¹ ² ³ ⁴ Galbraith ON THE SECURITY OF SUPERSINGULAR ISOGENY CRYPTOSYSTEMS (neopr.) . IACR
↑ Costello, Craig Efficient Compression of SIDH public keys (neopr.) . Date of treatment October 8, 2016.
↑ Key Compression for Isogeny-Based Cryptosystems (neopr.) . eprint.iacr.org . Date of treatment March 2, 2016.
↑ Fishbein, Dieter Machine-Level Software Optimization of Cryptographic Protocols (unspecified) . University of Waterloo Library - Electronic Theses . University of Waterloo (April 30, 2014). Date of treatment June 21, 2014.
↑ ¹ ² Costello, Craig; Longa, Patrick; Naehrig, Michael. Efficient algorithms for supersingular isogeny Diffie-Hellman : journal. - 2016 .-- January 1.
↑ Koziel, Brian; Jalali, Amir; Azarderakhsh, Reza; Kermani, Mehran; Jao, David. NEON-SIDH: Efficient Implementation of Supersingular Isogeny Diffie-Hellman Key Exchange Protocol on ARM ( journal ) : journal. - 2016. - 3 November.
↑ Jalali, A .; Azarderakhsh, R .; Kermani, M. Mozaffari; Jao, D. Supersingular Isogeny Diffie-Hellman Key Exchange on 64-bit ARM (English) // IEEE Transactions on Dependable and Secure Computing: journal. - 2017 .-- Vol. PP , no. 99 . - P. 1-1 . - ISSN 1545-5971 . - DOI : 10.1109 / TDSC.2017.2723891 .
↑ Koziel, Brian; Kermani, Mehran; Azarderakhsh, Reza. Fast Hardware Architectures for Supersingular Isogeny Diffie-Hellman Key Exchange on FPGA ( journal ) : journal. - 2016 .-- 7 November.
↑ defeo / ss-isogeny-software (neopr.) . Github Date of treatment May 29, 2015.
↑ Rostovtsev, Alexander PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES (neopr.) . Springer (2006). Date of treatment May 10, 2014. Archived May 29, 2006.
↑ Childs, Andrew M; Jao, Soukharev. Constructing elliptic curve isogenies in quantum subexponential time (English) // Journal of Mathematical Cryptology: journal. - Vol. 8 . - P. 1-29 . - DOI : 10.1515 / jmc-2012-0016 . - arXiv : 1012.4019 .
↑ Sun, Xi; Tian. Toward quantum-resistant strong designated verifier signature (neopr.) // International Journal of Grid and Utility Computing. - 2014 .-- 2 March ( v. 5 ). - S. 80 . - DOI : 10.1504 / IJGUC.2014.06010187 .
↑ Jao, David Isogeny-based quantum-resistant undeniable signatures (neopr.) (October 3, 2014). doi : 10.1007 / 978-3-319-11659-4_10 . Date of treatment April 28, 2016.
↑ Failure is not an option: standardization issues for post-quantum key (unspecified) . Talk at NIST workshop on Cybersecurity in a Post-Quantum (April 2015).
↑ Hofheinz, Dennis A Modular Analysis of the Fujisaki-Okamoto Transformation (neopr.) . Theory of Cryptography . Springer (2017) (September 26, 2017).
↑ Loop-Abort Faults on Supersingular Isogeny Cryptosystems (neopr.) . Springer (June 4, 2017).

[1] Costello, Craig; Jao, David; Longa, Patrick; Naehrig, Michael; Renes, Joost; Urbanik, David. Efficient compression of SIDH public keys (unspecified) . - 2016 .-- October 4.

[2] Utsler, Jim Quantum Computing Might Be Closer Than Previously Thought (neopr.) . IBM (September 2013). Date of treatment May 27, 2013.

[defeo-3] ¹ ² ³ ⁴ ⁵ De Feo, Luca Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies (neopr.) . PQCrypto 2011 . Springer Date of treatment May 4, 2014.

[4] Higgins, Parker Long Term Privacy with Forward Secrecy (neopr.) . Electronic Frontier Foundation. Date of treatment May 4, 2014.

[5] Zhu, Yan Why the Web Needs Perfect Forward Secrecy More Than Ever (neopr.) . Electronic Frontier Foundation. Date of treatment May 4, 2014.

[6] De Feo, Luca (2017), "Mathematics of Isogeny Based Cryptography", arΧiv : 1711.04062

[7] Delfs, Christina & Galbraith (29 Oct 2013), "Computing isogenies between supersingular elliptic curves over F_p", arΧiv : 1310.7789

[8] biasse A quantum algorithm for computing isogenies between supersingular elliptic curves (neopr.) . CACR. Date of treatment December 11, 2016.

[galbraith-9] ¹ ² ³ ⁴ Galbraith ON THE SECURITY OF SUPERSINGULAR ISOGENY CRYPTOSYSTEMS (neopr.) . IACR

[SIDHcompressed-10] Costello, Craig Efficient Compression of SIDH public keys (neopr.) . Date of treatment October 8, 2016.

[Report_2016/229-11] Key Compression for Isogeny-Based Cryptosystems (neopr.) . eprint.iacr.org . Date of treatment March 2, 2016.

[12] Fishbein, Dieter Machine-Level Software Optimization of Cryptographic Protocols (unspecified) . University of Waterloo Library - Electronic Theses . University of Waterloo (April 30, 2014). Date of treatment June 21, 2014.

[costello-13] ¹ ² Costello, Craig; Longa, Patrick; Naehrig, Michael. Efficient algorithms for supersingular isogeny Diffie-Hellman : journal. - 2016 .-- January 1.

[14] Koziel, Brian; Jalali, Amir; Azarderakhsh, Reza; Kermani, Mehran; Jao, David. NEON-SIDH: Efficient Implementation of Supersingular Isogeny Diffie-Hellman Key Exchange Protocol on ARM ( journal ) : journal. - 2016. - 3 November.

[15] Jalali, A .; Azarderakhsh, R .; Kermani, M. Mozaffari; Jao, D. Supersingular Isogeny Diffie-Hellman Key Exchange on 64-bit ARM (English) // IEEE Transactions on Dependable and Secure Computing: journal. - 2017 .-- Vol. PP , no. 99 . - P. 1-1 . - ISSN 1545-5971 . - DOI : 10.1109 / TDSC.2017.2723891 .

[16] Koziel, Brian; Kermani, Mehran; Azarderakhsh, Reza. Fast Hardware Architectures for Supersingular Isogeny Diffie-Hellman Key Exchange on FPGA ( journal ) : journal. - 2016 .-- 7 November.

[17] / ss-isogeny-software (neopr.) . Github Date of treatment May 29, 2015.

[18] Rostovtsev, Alexander PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES (neopr.) . Springer (2006). Date of treatment May 10, 2014. Archived May 29, 2006.

[19] Childs, Andrew M; Jao, Soukharev. Constructing elliptic curve isogenies in quantum subexponential time (English) // Journal of Mathematical Cryptology: journal. - Vol. 8 . - P. 1-29 . - DOI : 10.1515 / jmc-2012-0016 . - arXiv : 1012.4019 .

[20] Sun, Xi; Tian. Toward quantum-resistant strong designated verifier signature (neopr.) // International Journal of Grid and Utility Computing. - 2014 .-- 2 March ( v. 5 ). - S. 80 . - DOI : 10.1504 / IJGUC.2014.06010187 .

[21] Jao, David Isogeny-based quantum-resistant undeniable signatures (neopr.) (October 3, 2014). doi : 10.1007 / 978-3-319-11659-4_10 . Date of treatment April 28, 2016.

[22] Failure is not an option: standardization issues for post-quantum key (unspecified) . Talk at NIST workshop on Cybersecurity in a Post-Quantum (April 2015).

[23] Hofheinz, Dennis A Modular Analysis of the Fujisaki-Okamoto Transformation (neopr.) . Theory of Cryptography . Springer (2017) (September 26, 2017).

[24] Loop-Abort Faults on Supersingular Isogeny Cryptosystems (neopr.) . Springer (June 4, 2017).