- Active work is performed to create quantum computers. Quantum computers can break existing public key cryptography. So they can break Diffie-Hellman key exchange protocol. Matrix algorithms of key exchange can be considered as the alternative to Diffie-Hellman key exchange protocol. The improved method of key-exchange protocol is offered in the article. The method deals with the original matrix one-way function and the generalized method of processing the corresponding high order matrix multiplicative finite commutative group.
Scientists and experts are actively working on the creation of quantum computers. GOOGLE Corporation, NASA the association USRA (Universities Space Research Association and D-Wave teamed-up to develop quantum processors. Quantum computers can break existing public-key crypto systems. Quantum computer solves the discrete logarithm problem both for finite fields and elliptic curves. Being able to calculate efficiently discrete logarithms, it can break Diffie
Quantum computer also solves the factorization problem, so it can easily break RSA cryptosystem.
© 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0)
One of the modifications of Diffie-Hellman's well-known method of cryptographic key exchange is the matrix algorithms of the exchange, the basis for which is the high order cyclic multiplicative matrix groups in the GF (2) field.
Suppose that the P matrix is a primitive element of a cyclic matrix group. While (P) is a multiplicative group formed by this matrix, with the power 2 − 1, where n is the size of the square matrix.
The matrix algorithm for general key development is the following:
channel 1 = 1 vector, where 1 ∈ 〈 〉 is the secret matrix, selected by the sender, and ∈ is commonly known ( – is vector space on
(2)field);
The receiving party chooses 2 ∈ 〈 〉 to send a secret matrix and sends to the sender 2 = 2 vector; non-secret vectors from the above mentioned algorithm and 1 = ( ⋮ is the secret matrix. Then, according to the algorithm: 1 = ( 1 12 + 2 22 + ⋯ + 2 The number of variables in the system of linear equations is the square of the number of equations. Generally, solutions in such cases are not uniquely defined, and the system has infinitely many solutions. However, because we deal with a special types of matrices, the solution is defined uniquely. In addition, it is obvious that the solution of the system is very time consuming and is practically impossible in real time if the size of the matrix is large enough.
All this makes it necessary to generate high order Abelian multiplication matrix group, whose primitive element will be a high order quadratic matrix. Let's consider (1 + ) , where = 0, 1, 2, ⋯, and α represents the root of primitive polynomial in the (2 )field with the module ( ).
(1 + )0 = 1 (1 + )1 = 1 + (1 + )2 = 1 + 2 (1 + )3 = 1 + + 2 + 3 (1 + )4 = 1 + 4 (1 + )5 = 1 + + 4 + 5 1 11 101 1111 10001 110011
The polynomial coefficients generated by the above structure, are known as the Serpinsky triangle. Serpinsky's structure contains a number of sub-structures, that can be used as a generator (generating matrix) for multiplication groups, i.e. primitive elements. For example, Therefore we derived the insertion-enlargement method of second order enlargement of the basic structure of P3 [5]. Let’s keep the structure of the matrix 3 and enlarge it by elements of the set (4) as following [5]: 3
3 3 0 3
3 0 32( , )= ( 3 0 ), where i,j=0..6.
(
that 5 , = 1,2, … , 25 − 1 is a finite Abelian multiplicative group.
Any second order ( , + 1) enlargement of 3 32( , + 1), Consider basic structure 3 and enlarge it by 50 and 51 = 0. .5, is a primitive element and forms a finite Abelian matrices.
([ 32(
matrices are primitive elemenents. Therefore the set
( 3×51( 50, 51))is a finite Abelian multiplicative group.
multiplicative group ( 32( , + 1))with power 232– 1.
For example, the matrix 32(
For example, following enlargements are primitive: 31 31 30 0 0 0 0 31) , ( 31 31 31) , ( 0 31
There exist such enlargements of 3 matrix by 50 and 51 matrices, that are primitive elements. For example: is a diagonal matrix. With the analogy to (7) we see that ([ 3×51( 50, 51)]22∙51+251+1) , = 1,2, … diagonal, and when = 2 51 − 1, we see
52 ( 0 0 52
0 0 0 0 52 ) the identity matrix.
That means, that the set ( 3×51( 50, 51))is a finite Abelian multiplicative group with power of 23×51 − 1.
Consider now enlargements of order k=2 5 , = 1,2, … , 25 − 1 of the primitive element 5 using elements 5 ( 50, 51), = 2. There exist such enlargements, that form a primitive matrix. For example: 5 ( 50, 51)= , = 2 the matrix ( 5 ( 50, 51)) , where
Using the software developed by us, it could be seen that = 24∙5 −1 + 23∙5 −1 + 22∙5 −1
24∙5 −1+23∙5 −1+22∙5 −1+25 −1+1 = 54 All powers ( 5 ( 50, 51))
, are diagonal matrices with elements 5 , = 1,2, … , 25 − 1 from primary group 3 −1 diagonal. When = 2
− 1, we have the identity matrix: ( 4 5
The results, described above, give us the prospect of generating the high order multiplicative Abelian matrix groups and of the creating protocol, resistant quantum computers attacks.
Springer, Cham Rogaway P. (eds) Advances in Cryptology – CRYPTO 2011. CRYPTO 2011. Lecture Notes in Computer Science, vol 6841.
Springer, Berlin, Heidelberg
Iashvili, Post-quantum
Key Exchange Protocol Using