The paper considers a way to increase the stability of the NTRU Encrypt algorithm by replacing the uniform distribution with a normal one when generating encryption keys to increase the stability of transformations. The use of fast Fourier sampling to reduce the number of operations when performing encryption is justified.
With the constant process of improving
quantum computers, which leads to increase in the
number of qubits, the classic encryption
algorithms can be rapidly hacked. [
on solving NP-complexity problems, have become an alternative to classical algorithms in fields and rings.
NP-complexity problems include the
following tasks: finding the shortest lattice vector
(SVP - Shortest Vector Problem) or finding the
(approximately) shortest independent vectors
(SIVP – Shortest Independent Vectors Problem)
[
2. Algebraic lattices and fast Fourier transform.
tool for cryptographic transformations in modern
conditions. An algebraic lattice of dimension m
means a set of all possible combinations of
linearly independent vectors from a space of
dimension n with integer coefficients. [
The basis of a lattice 1, 2 ,… , is a set of linearly independent vectors that generates the specified lattice. Coordinates of basis vectors are = { 11, 12, . . . 1 } = ̅1̅̅,̅̅.
which rows are the coordinates of the basis vectors that form it. It is well known that any lattice can be defined by several bases and build a matrix of transition from one basis to another. basic vector of dimension n, the coordinates of which are equal to the coefficients coordinates of the basis vectors with the formula: where is the number of basis vectors, is the degree of the original element, is the value of the original root of unity, is the value of the polynomial from the degrees of the original root of unity.
This mathematical apparatus allows with performing transformations on algebraic lattices to reduce the number of operations due to the properties such as 0 = = 1. In addition, ∙ = element then. +
= ( + ) condition −1 = −1 . So, it is enough to use the to find the inverse
With the help of fast Fourier transform it is possible to solve a problem which consists in search from a numerical matrix of the big size of extraction of the small size block with the specified properties.
Under the block means the submatrix of the initial matrix. The idea of this algorithm, based on the fast Fourier transform, is to find some pattern 0, 1, … … −1 in a range 0, 1, … , −1, where , are some numbers. It is well known that the subrange enters from the i-th position, if = + , = 0,1,2, … ,
− 1. Entry of the subrange of the i-th position is equivalent to the fulfillment of the condition: −1 =0 = ∑ ( − + ) = 0.
(4) 2
Calculating the array Ві allows to determine all
entries of subranges into the range. This property
is used to construct one-sided functions with a
trapdoors,
which
are
used in
cryptographic
transformations on algebraic lattices [
[
Polynomial calculations are performed ( )= ( ) ( ), where ( )= −1 −1 + ⋯ + 1 + 0, ( )= 0 −1 + ⋯ + −1 the coefficient of the specified polynomial at −1+ −1+ = 0 + 1 +1 + ⋯ + is equal to
−1 −1 −1 = ∑ =0 + .
2. Calculations = ∑ =−01 2 performed and this addend is present in every Ві; 3. Calculations = ∑ =−01 2 performed; are are of (
) = 0 1 ⋮ −1 1 ⋮ −1 ( −1)( −1) ) ( 1 ), 0
⋮ −1 (1) = ( 1 ⋮ 1 1 ⋮ 1 −1… … … ⋮ where is the value of the polynomial from the degrees of the original root of unity, is the value of the original root of unity degree і, are polynomial coefficients that determine the coordinates of the basis vectors.
For any prime number in the field of surpluses modulo there is a root of degree ( − 1)of unity, which satisfies the following formula: − 1 = 2 , (2) where is the root of degree of unity. Formula 2 allows the application of fast Fourier transform algorithms for polynomials of degree . It can be shown that for any natural number k such a prime number q exists. This follows from
theorem
Dirichlet's
on prime
numbers
[
NTRU Encrypt algorithm [
build a mathematical model of the algorithm: N – the dimension of the ring of polynomials which used in encrypting messages; p
– a natural number involved in encrypting and decrypting of the message; q – a natural number that participates in encrypting, decrypting to attacks depends;
with certain properties, such as to find the shortest lattice vector.
• dі (і=1,2) – distributions of polynomial coefficients used in the formation of the public and secret keys.
When generating keys, consider a ring of truncated polynomials element of the ring polynomial form = = [ ]/( − 1). Each can −1 ∑ =0 be represented in or in vector form ( 1, 2, … , −1). All coefficients of a polynomial are integers. To reduce the complexity calculating the operation of multiplication of polynomials in a ring of truncated polynomials is possible by applying the operation of of "convolution" according to the following rule: let it be necessary to multiply 2 polynomials = −1 ∑ =0 and =
−1 ∑ =0 truncated polynomials in a ring of = [ ]/( − 1). The result of multiplication ℎ = ⨂ is a polynomial of the form: ℎ = are calculated by the formula: ∑ =0 −1 ℎ , which coefficients
ℎ
= ∑ =0 − + ∑ −1 = +1 + − .
This formula = [ ]/( − 1) due to the numbers, but they must satisfy the conditions: НСД (p, q) = 1 and parameter p should be much smaller than q. Using the values of the parameters p and q, two polynomials and are randomly selected. A polynomial truncated polynomials belongs to a ring of = [ ]/( − 1) with the distribution of coefficients with the parameter d1. This means that the polynomial contains d1 coefficients equal to 1, d1 -1 coefficients equal to -1 and all other coefficients equal to 0. This distribution of coefficients is due to the presence of an inverse polynomial to the polynomial . A polynomial polynomials belongs to a ring of truncated = [ ]/( − 1) with the distribution of coefficients with the parameter d2. This means that the polynomial contains d2 coefficients equal to 1, d2 -1 coefficients equal to -1 and all other coefficients equal to 0. Using polynomial coefficients, polynomials ≡ ( )and ≡ (
)are constructed.
The obtained
polynomials have inverse polynomials in the ring of truncated polynomials = [ ]/( − 1) and = [ ]/( − 1). As for polynomials obtained by reducing a polynomial modulo p and q, they do not have inverse polynomials in the ring of truncated polynomials = [ ]/( − 1) and = [ ]/( − 1).
The public key is calculated according to the rule: ℎ ≡ −1 ⊗ ( ). It should be noted that the polynomial ℎ and the numbers p and q are open parameters, and the polynomial and −1 are secret. To encrypt messages a polynomial r , that has a distribution of coefficients d3 in the ring of truncated polynomials = [ ]/( − 1), and a public key ℎ are randomly selected. This means that the polynomial ℎ contains d3 coefficients equal to 1, d3 -1 coefficients equal to -1 and all other coefficients equal to 0.
).
First, calculate the polynomial p with integer coefficients from the interval ( formula: ≡ ⊗ ( ). Then calculate 2
2 − , ) by the −1 ⊗ .
The specified encryption algorithm has a disadvantage, which is associated with the appearance of parameters that contribute to errors. Therefore, it is necessary to include control bits for each message block. The cause of such errors is incorrect message centering. It is possible to get rid of it by calculating a polynomial ≡ ⊗ )with integer coefficients in the interval + ) for a small value of negative or positive x. If this algorithm does not work, then the encryption procedure is repeatable.
concluded that the
NTRU cryptosystem is probabilistic, so the plaintext is not always restored correctly from the encrypted text. The correct choice of polynomials f, g, r allows to reduce the probability of such an error to . (
− ( 2 + ,
2 4. Means to increase the stability of the NTRU algorithm and its speed
Encrypt algorithm
and
the
existing
specific attacks [
To
determine
the
coefficients
of
the
polynomial r , it is proposed to use a random
number generator and the density of the normal
distribution
with predetermined
mathematical
expectations and standard deviation. The standard
deviation in this algorithm is the value of safety
level control and is a decisive factor. This is due
to the fact that the stability of algorithms on
algebraic lattices is based on the solution of the
SPV problem (the problem of finding a short
lattice vector) [
algorithm allows to obtain a basis using the Gram
process [
Next, using the obtained value of the standard deviation and a mathematical expectation equal to zero a random sequence is formed according to the following algorithm:
a sequence (сn) of random numbers is generated;
divide the field of real numbers into intervals according to the following condition: І1 = (−∞, −3 ), І2 = (−3 , 0) І3 = (0,3 ) І4 = (3 , +∞);
check in what interval the generated number got сі. If сі ∈ І1, сі ∈ І4, then і - member of the sequence is equal to 0. If сі ∈ І2 , Then і member of the sequence is equal to -1. If сі ∈ І3 , then і - member of the sequence is equal to 1. This sequence is the coefficient of the polynomial r, which is used for encryption.
To find the shortest lattice vector, we use a one-way function with a trapdoor, which allows us to find the shortest lattice vector from an array based on the fast Fourier transform. Next, the 1. 2. 3.
Euclidean norm of this vector is calculated, which allows to set the density function of the normal distribution and on the basis of the calculations to obtain a polynomial r .
algorithms, as mentioned above, by applying a fast Fourier transform. = [ ]/( − 1).
According to formula 2 to determine the modulus q it is necessary to find such a simple value of q that corresponds to the condition − 1 = ∙ 27. It is proposed to apply to cryptographic transformations that provide a high level of stability the value of = 3 ∙ 27 + 1 = 769. This parameter gives possibility to apply the fast Fourier transform algorithm for polynomials of degree N. In a accordance with Dirichlet’s theorem on a prime number for a prime number 769 in the field of the class of surpluses there is a root g of degree 768 of unity. Then = 3 is a root g of degree of unity. This fact gives possibility to apply formula 3 and reduce the complexity of the calculation.
Based on the analysis of the NTRU Encrypt algorithm, the paper proposes the application of the normal distribution law to determine the coefficients of the polynomial by which encryption is performed. The application of its parameters, namely mathematical expectation and heart-square deviation, is determined and substantiated. The choice of the original root for the representation of the base vectors of the algebraic lattice using fast Fourier transform is substantiated. It allows to reduce the encryption complexity for a high level of stability of transformations based on the NTRU Encrypt algorithm. 6.References