Investigations in the sphere of quantum calculations form up new challenges in the public key cryptography. Currently known public key crypto algorithms may be compromised with the implementation of quantum computers. The workgroups of ETSI and NIST determined the promising trends, within the framework of which there could be obtained acceptable solutions and one of the trends is the use of algorithms that process points of supersingular elliptic curves. Hardware implementations of components for processing points of elliptic curves are well known. The purpose of this publication is to investigate how they can be used to process points of supersingular elliptic curves.
The advent of large-scale quantum computing offers great promise to science and society, but brings with it a significant threat to global information infrastructure. Publickey cryptography - widely used on the internet today – relies upon mathematical problems that are believed to be difficult to solve given the computational power available now and in the medium term.
However, popular cryptographic schemes based on these hard problems – including Elliptic Curve Cryptography – will be easily broken by a quantum computer. This will rapidly accelerate the obsolescence of currently deployed security systems and will have dramatic impacts on any industry where information needs to be kept secure.
Quantum-safe cryptography refers to efforts to identify algorithms that are resistant to attacks by both classical and quantum computers, to keep information assets secure even after a large-scale quantum computer has been built [1].
Supersingular isogeny Diffie–Hellman key exchange (SIDH) is a post-quantum cryptographic algorithm used to establish a secret key between two parties over an otherwise insecure communications channel. It is analogous to the Diffie–Hellman key exchange, but is designed to resist cryptanalytic attack by an adversary in possession of a quantum computer.
II. THE SUPERSINGULAR ISOGENY DIFFIE
The supersingular isogeny Diffie-Hellman (SIDH) method works with the set of supersingular elliptic curves E over Galois Field GF( p 2 ) . An isogeny of an elliptic curve E is a rational map from E to another elliptic curve E' which is also a group homomorphism. Provided the isogenies are separable, they are determined by the points inside their kernel up to isomorphisms of E'.
The SIDH method works with a prime of the form p = ( wA )eA ( wB )eB ( f ) ± 1 where wA and wB are small primes and an elliptic curve E defined by the equation: y 2 = x 3 + ax + b . SIDH builds an isogeny map from a single elliptic curve point which is taken as the generator for the isogeny's kernel. This point is chosen to be a random linear combination to two fixed points chosen to be in the kernel of the isogeny.
The j-invariant of an elliptic curve E is a fixed function of a set of isomorphic curves. It is computed from the parameters that define the curve. For an elliptic curve E defined by the equation: y 2 = x 3 + ax + b the j-invariant 4a 3 + 27b 2
The security of SIDH is closely related to the problem of finding the isogeny mapping between two supersingular elliptic curves with the same number of points. In [3] it was shown that the security of SIDH will be O(p1/4) for classical computers and O(p1/6) for quantum computers. This suggests that SIDH with a 768-bit prime (p) will have a 128-bit security level.
In 2014, researchers at the University of Waterloo developed a software implementation of SIDH. They ran their partially optimized code on an x86-64 processor running at 2.4 GHz. For a 768-bit modulus they were able to complete the key exchange computations in 200 milliseconds thus demonstrating that the SIDH is computationally practical [4].
In 2016, researchers from Microsoft posted software for the SIDH which runs in constant time (thus protecting against timing attacks) and is the most efficient implementation to date [5].
In 2017, researchers from Florida Atlantic University developed the first FPGA implementations of SIDH for 83bit and 124-bit quantum security levels [6].
For supersingular elliptic curves there is well known Vélu
algorithm [
x 3 − 4 x 2 − 8 x − 8 x 3 y − 6 x 2 y − 5xy − 6 y ( x, y ) →( ,
x 2 − 4 x − 4 x 3 − 6 x 2 − 7 x − 8
So, to determine the isogeny, it is necessary to perform the operations of addition, multiplication and inverse element calculation in the Galois field GF(p2). ) .
IV. ESTIMATION OF THE SOFTWARE TIME COMPLEXITY OF OPERATIONS IN THE GALOIS
In works [
One of the computer system hacking methods is the
bruteforce method [
Field Characteristic 2 3 5 7
The relative time complexity was determined by the ratio of the multiplication time in the field GF(dm) to the multiplication time in the field GF(2999).
As can be seen from the Table 1, software multiplication of triple extended field elements has the longest execution time. It provides hardware cryptoprocessors based on such fields additional protection against hacking. Software-implemented operations on simple field elements are executed in the fastest way, that indicates the inappropriateness of cryptographic processors based on such fields. Multiplication in binary fields has one of the highest time complexity, it is
Re lative time comple xity
V. ESTIMATION OF THE HARDWARE TIME COMPLEXITY OF OPERATIONS IN THE GALOIS
FIELDS
Implemented in modern FPGA hardware multipliers for
extended Galois field GF (dm) with approximately the same
number of elements dm ≈ 2n were estimated in [
HARDWARE TIME COMPLEXITY OF
OPERATIONS IN THE GALOIS FIELDS
We will assume that the hardware implementation is used by users of data protection tools, and software is used by hackers. Then we can introduce a generalized time complexity index. We will calculate this indicator as the ratio of software time complexity to hardware time complexity for the same fields. When the value of this indicator is greater, then hackers will have more problems, so data protection will be better. 2 3 4 5 6 7 8 9
Results of hardware-software complexity estimation is shown in Fig. 3.
As can be seen from Fig. 3, the trial and binary Galois fields provide the best data protection. Fields with large characteristics provide weaker protection. The use of hardware tools for working in such fields has less effect than for working in binary and trial fields. As result the use of hardware tools to work in the field with the characteristic 768 [3] also has less effect than for working in binary and ternary fields.
The use of isogenies of supersingular elliptic curves is oriented toward usage of Galois field with big characteristics, so they are focused on software implementation. Re lative HS-Comle xity
Field Charact erist ic
The use of isogenies of supersingular elliptic curves is oriented toward software implementation of the method. Hardware implementation of this method will not provide such a reduction in time complexity and increase the degree of data protection as it provides in methods oriented on binary fields.