=Paper=
{{Paper
|id=Vol-3200/paper37
|storemode=property
|title=Improving the Stability of Cryptographic Algorithms on Algebraic Lattices
|pdfUrl=https://ceur-ws.org/Vol-3200/paper37.pdf
|volume=Vol-3200
|authors=Olha Petrenko,Oleksii Petrenko
}}
==Improving the Stability of Cryptographic Algorithms on Algebraic Lattices ==
https://ceur-ws.org/Vol-3200/paper37.pdf
Improving the Stability of Cryptographic Algorithms on Algebraic
Lattices
Olha Petrenko 1, Oleksii Petrenko 2
1
Kharkiv National University of Radio Electronics, Nauky Ave. 14, Kharkiv, 61166, Ukraine
2
Ivan Kozhedub Kharkiv National Air Force University, Sumska Str. 77/79, Kharkiv, 61023, Ukraine
Abstract
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.
Keywords 1
Algebraic lattices, NTRU Encrypt algorithm, fast Fourier transform, normal distribution.
1. Introduction on solving NP-complexity problems, have
become an alternative to classical algorithms in
fields and rings.
With the constant process of improving
NP-complexity problems include the
quantum computers, which leads to increase in the
following tasks: finding the shortest lattice vector
number of qubits, the classic encryption
(SVP - Shortest Vector Problem) or finding the
algorithms can be rapidly hacked. [1] Given this,
(approximately) shortest independent vectors
there is a necessity of developing and further
(SIVP – Shortest Independent Vectors Problem)
improving of the algorithms, which are able to
[2]. The essence of these problems is to find in a
counteract cryptanalysis in the post-quantum
given basis of the algebraic lattice of a nonzero
period. The question of defining and
vector that close to a certain normal.
substantiating the size of their parameters and
The aim of this article is developing tools of
conditions of application for solving various
increasing the stability of the algorithm on
applied problems remains relevant. With the
algebraic lattices, the NTRU algorithm exactly,
practical application of the algorithms, there are
without effect on its performance
problems associated with end-to-end encryption,
such as encrypting messages between the UAV
and the ground workstation. In solving the tasks, 2. Algebraic lattices and fast Fourier
it is necessary to use fast algorithms that can work transform.
effectively in the post-quantum period. Finding
new solutions to protect information in the post-
Algebraic lattices have become a convenient
quantum period and improving existing
tool for cryptographic transformations in modern
algorithms by increasing their cryptographic
conditions. An algebraic lattice of dimension m
stability is a task that is relevant today.
means a set of all possible combinations of
Algorithms that use transformations on
linearly independent vectors from a space of
algebraic lattices, the stability of which is based
dimension n with integer coefficients. [3].
III International Scientific And Practical Conference “Information
Security And Information Technologies”, September 13–19, 2021,
Odesa, Ukraine
EMAIL: olha.petrenko@nure.ua (A. 1); alexwgs78@gmail.com
(A. 2)
ORCID: orcid.org/0000-0002-7862-5399 (A. 1); orcid.org/0000-
0001-9903-7388 (A. 2)
©️ 2021 Copyright for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
CEUR Workshop Proceedings (CEUR-WS.org)
The basis of a lattice 𝑏1 , 𝑏2 ,… , 𝑏𝑛 is a set of the formula 2. Using the inverse Fourier
linearly independent vectors that generates the transform, it is possible to determine the
specified lattice. Coordinates of basis vectors are coordinates of the basis vectors with the formula:
𝑛−1
𝑏𝑖 = {𝑥11 , 𝑥12 , . . . 𝑥1𝑚 } 𝑖 = ̅̅̅̅̅
1, 𝑛. 1 −𝑗𝑘
The lattice can be associated with a matrix 𝑎𝑗 = ∑ 𝑦𝑗 𝑤𝑛 (3)
𝑛
which rows are the coordinates of the basis 𝑗=0
vectors that form it. It is well known that any where 𝑛 is the number of basis vectors, 𝑘 is the
lattice can be defined by several bases and build a degree of the original element, is the value of
matrix of transition from one basis to another. the original root of unity, 𝑦𝑗 is the value of the
This property allows to implement stable polynomial from the degrees of the original root
algorithms on algebraic lattices by constructing a of unity.
basis that consisting of the shortest vectors. Using This mathematical apparatus allows with
polynomials of degree n, it is possible to specify a performing transformations on algebraic lattices
basic vector of dimension n, the coordinates of to reduce the number of operations due to the
which are equal to the coefficients of the properties of the original roots of unity,
polynomial. These properties allow to apply the 𝑗
such as 𝑤𝑛0 = 𝑤𝑛𝑛 = 1. In addition, 𝑤𝑛 ∙ 𝑤𝑛𝑘 =
fast Fourier transform to represent the basis 𝑗+𝑘 (𝑗+𝑘)𝑚𝑜𝑑𝑛
vectors and build cryptographic transformations 𝑤𝑛 = 𝑤𝑛 . So, it is enough to use the
with their help. According to [4], the fast Fourier condition 𝑤𝑛𝑛−1 = 𝑤𝑛−1 to find the inverse
transform can be applied when developing an element then.
algorithm on algebraic lattices in a ring of a class With the help of fast Fourier transform it is
of surpluses modulo some number q. In addition, possible to solve a problem which consists in
the fast Fourier transform can be represented in search from a numerical matrix of the big size of
matrix form, which allows in the field of surpluses extraction of the small size block with the
modulo q to move from the values of the specified properties.
polynomial from the original roots from one to its Under the block means the submatrix of the
coefficients according to formula 1. initial matrix. The idea of this algorithm, based on
𝑦0 the fast Fourier transform, is to find some pattern
𝑦1 𝑝0 , 𝑝1 , … … 𝑝𝑚−1 in a range 𝑡0 , 𝑡1 , … , 𝑡𝑛−1 , where
( ⋮ )= 𝑝𝑖 , 𝑡𝑗 are some numbers. It is well known that the
𝑦𝑛−1 subrange enters from the i-th position, if 𝑝𝑗 =
1 … 1 (1) 𝑡𝑖+𝑗 , 𝑗 = 0,1,2, … , 𝑚 − 1. Entry of the subrange
1 𝑎0
𝑛−1
1 𝑤𝑛 … 𝑤𝑛 of the i-th position is equivalent to the fulfillment
=( ⋮ ⋮ ) ( 𝑎1⋮ ),
⋮ ⋮ of the condition:
(𝑛−1)(𝑛−1) 𝑎𝑛−1
1 𝑤𝑛𝑛−1 …𝑤𝑛 𝑚−1
2
where 𝑦𝑗 is the value of the polynomial from the 𝐵𝑖 = ∑ (𝑝𝑗 − 𝑡𝑖+𝑗 ) = 0. (4)
degrees of the original root of unity, 𝑤𝑛𝑖 is the 𝑗=0
value of the original root of unity degree і, 𝑎𝑖 are Calculating the array Ві allows to determine all
polynomial coefficients that determine the entries of subranges into the range. This property
coordinates of the basis vectors. is used to construct one-sided functions with a
For any prime number 𝑞 in the field of surpluses trapdoors, which are used in cryptographic
modulo 𝑞 there is a root 𝑔 of degree (𝑞 − 1)of transformations on algebraic lattices [6].
unity, which satisfies the following formula: The algorithm for calculating Ві according to
𝑞 − 1 = 𝑚2𝑘 , (2) [6] is to perform the following steps:
𝑚
where 𝑔 is the root of degree of unity. Formula 1. Polynomial calculations are performed
2 allows the application of fast Fourier transform 𝐶 (𝑥 ) = 𝑇(𝑥 )𝑃(𝑥 ), where 𝑇(𝑥 ) = 𝑡𝑛−1 𝑥 𝑛−1 +
algorithms for polynomials of degree . It can be ⋯ + 𝑡1 𝑥 + 𝑡0 , 𝑃(𝑥 )=𝑝0 𝑥 𝑚−1 + ⋯ + 𝑝𝑚−1 the
shown that for any natural number k such a prime coefficient of the specified polynomial at 𝑥 𝑚−1+𝑖
number q exists. This follows from Dirichlet's is equal to 𝑐𝑚−1+𝑖 = 𝑝0 𝑡𝑖 + 𝑝1 𝑡𝑖+1 + ⋯ +
theorem on prime numbers [5]. To apply 𝑝𝑚−1 𝑡𝑚−1 = ∑𝑚−1 𝑗=0 𝑝𝑗 𝑡𝑗+𝑖 .
Dirichlet's theorem for cryptographic 2. Calculations of 𝑆 = ∑𝑚−1 𝑗=0 𝑝𝑗
2
are
transformations on lattices, the number 𝑞 and the performed and this addend is present in every Ві;
degree of the polynomial on which the 𝐻 = ∑𝑚−1 2
3. Calculations 𝑗=0 𝑡𝑗 are
transformations are performed must correspond to
performed;
4. Calculations of the recurrent formula: • dі (і=1,2) – distributions of polynomial
𝐵0 = 𝑆 − 2𝑐𝑚−1 + 𝐻, 𝐵1 = 𝑆 − 2𝑐𝑚 + coefficients used in the formation of the public
𝑚−1 2
∑𝑗=0 𝑡𝑗+1 = 𝐵0 − 2𝑐𝑚−1 − 2𝑐𝑚 − 𝑡12 + 𝑡𝑚 2
, and secret keys.
( ) 2 When generating keys, consider a ring of
𝐵𝑖 = 𝐵𝑖−1 + 2 𝑐𝑚−2+𝑖 + 𝑐𝑚−1+𝑖 − 𝑡𝑖−1 −
2
𝑡𝑚−1+𝑖 are performed. truncated polynomials 𝑅 = 𝑍[𝑥 ]/(𝑥 𝑁 − 1). Each
This algorithm allows to determine vectors element of the ring can be represented in
with certain properties, such as to find the shortest polynomial form 𝑓 = ∑𝑁−1 𝑠
𝑠=0 𝑓𝑠 𝑥 or in vector form
lattice vector. (𝑓1 , 𝑓2 , … , 𝑓𝑁−1 ). All coefficients of a polynomial
are integers. To reduce the complexity of
calculating the operation of multiplication of
3. NTRU algorithm polynomials in a ring of truncated polynomials is
possible by applying the operation of
NTRU Encrypt algorithm [7] today is one "convolution" according to the following rule: let
of the most researched and widespread it be necessary to multiply 2 polynomials 𝑓 =
algorithms. The asymmetric cryptosystem which ∑𝑁−1
𝑠=0 𝑓𝑠 𝑥
𝑠
and 𝑔 = ∑𝑁−1 𝑠
𝑠=0 𝑔𝑠 𝑥 in a ring of
built on its basis is based on transformations on truncated polynomials 𝑅 = 𝑍[𝑥 ]/(𝑥 𝑁 − 1). The
algebraic lattices. NTRU is a probabilistic stable result of multiplication ℎ = 𝑓⨂𝑔 is a polynomial
system, i.e. a random element is used to encrypt of the form: ℎ = ∑𝑁−1 𝑠
𝑠=0 ℎ𝑠 𝑥 , which coefficients
messages. Under this condition, each message has are calculated by the formula:
a lot of ciphertext. The stability of the ℎ𝑠 = ∑𝑠𝑖=0 𝑓𝑖 𝑔𝑠−𝑖 + ∑𝑁−1𝑖=𝑠+1 𝑓𝑖 𝑔𝑁+𝑠−𝑖 .
cryptosystem NTRU Encrypt [7] was determined This formula allows to reduce the
experimentally and is based on the fact of the computational complexity of multiplying
difficulty of finding the shortest vector of the polynomials in 𝑅 = 𝑍[𝑥 ]/(𝑥 𝑁 − 1) due to the
algebraic lattice [2]. The advantage of this system lack of a summation of 𝑚𝑜𝑑 (𝑥 𝑁 − 1) terms
is the fact that encryption and decryption of the which degree are greater than N.
message and key generation process is quick and The parameters p and q do not have to be prime
easy for implementing. NTRU Algebraic Lattice numbers, but they must satisfy the conditions:
Algorithm is an attractive algorithm for НСД (p, q) = 1 and parameter p should be much
encrypting data in the communication channel smaller than q. Using the values of the parameters
between the UAV and the ground workstation. p and q, two polynomials 𝑓 and 𝑔 are randomly
The advantage of the algorithm on the one hand is selected. A polynomial 𝑓 belongs to a ring of
the ability to perform asymmetric encryption, and truncated polynomials 𝑅 = 𝑍[𝑥 ]/(𝑥 𝑁 − 1) with
on the other to provide fast software the distribution of coefficients with the parameter
implementation. The complexity of the algorithm d1. This means that the polynomial 𝑓 contains d1
can be reduced by applying a fast Fourier coefficients equal to 1, d1 -1 coefficients equal to
transform [4] from Ο(𝑛2 ) to Ο(𝑛𝑙𝑜𝑔𝑛). The -1 and all other coefficients equal to 0. This
NTRU Encrypt algorithm depends on parameters distribution of coefficients is due to the presence
that are integers and can be represented in of an inverse polynomial to the polynomial 𝑓. A
polynomial form. In order for the parameters not polynomial 𝑔 belongs to a ring of truncated
to contribute to the occurrence of random errors polynomials 𝑅 = 𝑍[𝑥 ]/(𝑥 𝑁 − 1) with the
during decryption, it is necessary to include
distribution of coefficients with the parameter d2.
control bits in each message block.
This means that the polynomial 𝑔 contains d2
The following parameters are used to coefficients equal to 1, d2 -1 coefficients equal to
build a mathematical model of the algorithm: -1 and all other coefficients equal to 0. Using
• N – the dimension of the ring of polynomial 𝑓 coefficients, polynomials 𝑓𝑝 ≡
polynomials which used in encrypting messages; 𝑓 (𝑚𝑜𝑑 𝑝) and 𝑓𝑞 ≡ 𝑓 (𝑚𝑜𝑑 𝑞 ) are constructed.
• p – a natural number involved in The obtained polynomials have inverse
encrypting and decrypting of the message; polynomials in the ring of truncated polynomials
• q – a natural number that participates in 𝑅𝑝 = 𝑍𝑝 [𝑥 ]/(𝑥 𝑁 − 1) and 𝑅𝑞 = 𝑍𝑞 [𝑥 ]/(𝑥 𝑁 −
encrypting, decrypting of the message and
1). As for polynomials obtained by reducing a
determining the public key;
polynomial modulo p and q, they do not have
• k – the key security on which resistance
inverse polynomials in the ring of truncated
to attacks depends;
polynomials 𝑅𝑝 = 𝑍𝑝 [𝑥 ]/(𝑥 𝑁 − 1) and 𝑅𝑞 = expectations and standard deviation. The standard
𝑍𝑞 [𝑥 ]/(𝑥 𝑁 − 1). deviation in this algorithm is the value of safety
The public key is calculated according to the level control and is a decisive factor. This is due
rule: ℎ ≡ 𝑝𝑓𝑞−1 ⊗ 𝑔(𝑚𝑜𝑑 𝑞 ). It should be noted to the fact that the stability of algorithms on
algebraic lattices is based on the solution of the
that the polynomial ℎ and the numbers p and q are
SPV problem (the problem of finding a short
open parameters, and the polynomial 𝑓 and 𝑓𝑞−1
lattice vector) [11]. The specified value of the
are secret. To encrypt messages a polynomial r , parameter should be chosen under the
that has a distribution of coefficients d3 in the ring requirements of the stability of transformations,
of truncated polynomials 𝑅 = 𝑍[𝑥 ]/(𝑥 𝑁 − 1), namely the standard deviation should be equal to
and a public key ℎ are randomly selected. This the shortest vector of the algebraic lattice. As for
means that the polynomial ℎ contains d3 the mathematical expectation, it can be zero. This
coefficients equal to 1, d3 -1 coefficients equal to point is due to the fact that for successful
-1 and all other coefficients equal to 0. cryptanalysis it is necessary to find the lattice
The message m is encrypted as follows: с ≡
points within the probable radius 𝑠√𝑁, where N is
𝑟 ⊗ ℎ + 𝑚(𝑚𝑜𝑑 𝑞 ).
the degree of the polynomial, the modulus of
The message is decrypted in two stages.
which is transformed, s is the Euclidean norm of
First, calculate the polynomial p with integer
−𝑞 𝑞
the shortest lattice vector. The higher the rate of
coefficients from the interval ( , ) by the the vector, the greater the freedom of action of the
2 2
formula: 𝑎 ≡ 𝑓 ⊗ 𝑐 (𝑚𝑜𝑑 𝑞 ). Then calculate cryptanalyst to carry out attacks. In view of this,
𝑓𝑞−1 ⊗ 𝑎. it is proposed to choose the standard deviation
The specified encryption algorithm has a equal to the Euclidean norm of the shortest lattice
disadvantage, which is associated with the vector. It is possible to obtain the shortest lattice
appearance of parameters that contribute to errors. vector among the basis vectors with using the
Therefore, it is necessary to include control bits algorithm proposed in the paper [8]. This
for each message block. The cause of such errors algorithm allows to obtain a basis using the Gram-
is incorrect message centering. It is possible to get Schmidt orthogonalization process [12] with
rid of it by calculating a polynomial 𝑎 ≡ 𝑓 ⊗ predetermined restrictions on the lengths of
𝑐 (𝑚𝑜𝑑 𝑞 ) with integer coefficients in the interval vectors.
−𝑞 𝑞 Next, using the obtained value of the standard
( + 𝑥, + 𝑥) for a small value of negative or deviation and a mathematical expectation equal to
2 2
positive x. If this algorithm does not work, then zero a random sequence is formed according to
the encryption procedure is repeatable. the following algorithm:
From the decryption procedure, it can be 1. a sequence (сn) of random numbers is
concluded that the NTRU cryptosystem is generated;
probabilistic, so the plaintext is not always 2. divide the field of real numbers into
restored correctly from the encrypted text. The intervals according to the following condition:
correct choice of polynomials f, g, r allows to І1 = (−∞, −3𝜎), І2 = (−3𝜎, 0) І3 = (0,3𝜎)
reduce the probability of such an error to . І4 = (3𝜎, +∞);
3. check in what interval the generated
4. Means to increase the stability of number got сі. If сі ∈ І1 , сі ∈ І4 , then і - member
of the sequence is equal to 0. If сі ∈ І2 , Then і -
the NTRU algorithm and its speed member of the sequence is equal to -1. If сі ∈ І3 ,
then і - member of the sequence is equal to 1. This
Given the advantages and disadvantages of the sequence is the coefficient of the polynomial r,
NTRU Encrypt algorithm and the existing which is used for encryption.
specific attacks [8-10],]it is possible to increase The sequence proposed by this rule allows to
the stability of the algorithm by applying not increase the resistance of the algorithm on the
uniform but normal distribution law when algebraic lattices of NTRU Encrypt to the attack
encrypting a message, namely when choosing described in [12,13].
polynomial r coefficients. To find the shortest lattice vector, we use a
To determine the coefficients of the one-way function with a trapdoor, which allows
polynomial r , it is proposed to use a random us to find the shortest lattice vector from an array
number generator and the density of the normal based on the fast Fourier transform. Next, the
distribution with predetermined mathematical
Euclidean norm of this vector is calculated, which [4] Ju. V. Linnik, A. O. Gel'fand. Jelementarnye
allows to set the density function of the normal metody v analiticheskoj teorii chisel. —
distribution and on the basis of the calculations to Fizmatgiz, 1962.
obtain a polynomial r . [5] D. Micciancio and C. Peikert. Trapdoors for
It is possible to increase the speed of lattices: Simpler, tighter, faster, smaller. In
algorithms, as mentioned above, by applying a EUROCRYPT, 2012, pp. 700–718.
fast Fourier transform. 𝑅 = 𝑍 [𝑥 ]/(𝑥 𝑁 − 1). [6] Hoffstein J., Lieman D., Pipjer J., Silverman
According to formula 2 to determine the J. NTRU: A public key cryptosystem.
modulus q it is necessary to find such a simple Conference International Algorithmic
value of q that corresponds to the condition 𝑞 − Number Theory Symposium Springer,
1 = 𝑚 ∙ 27 . It is proposed to apply to Berlin, Heidelberg, 1998, pp. 267-288.
cryptographic transformations that provide a high [7] A. K. Lenstra, H. W. Lenstra, Jr., and L.
level of stability the value of 𝑞 = 3 ∙ 27 + 1 = Lov ́asz. Factoring polynomials with rational
769. This parameter gives possibility to apply the coefficients. Math. Ann., 261(4), 1982, pp.
fast Fourier transform algorithm for polynomials 515–534.
of degree N. In a accordance with Dirichlet’s [8] J. Hoffstein, J.H. Silverman, Protecting NTRU
theorem on a prime number for a prime number Against Chosen Ciphertext and Reaction
769 in the field of the class of surpluses there is a Attacks, NTRU Technical Report #016, June
root g of degree 768 of unity. Then 𝜔 = 𝑔3 is a 2000, www.ntru.com
root g of degree of unity. This fact gives [9] E. Jaulmes, A. Joux, A chosen-ciphertext
possibility to apply formula 3 and reduce the attack against NTRU, in Proceedings of
complexity of the calculation. CRYPTO, Lecture Notes in Comp ter
Science, Springer-Verlag, 2000.
[10]. C. Peikert. Public-key cryptosystems from
5. Conclusion the worst-case shortest vector problem. In
STOC, 2009, pp. 333–342.
Based on the analysis of the NTRU Encrypt [11] Howgrave-Graha N., Silverman J., Whyte
algorithm, the paper proposes the application of W. Meet-in-the-middle attack on an NTRU
the normal distribution law to determine the private key // NTRU Cryptosystems
coefficients of the polynomial by which Technical Report #004. Version 2.
encryption is performed. The application of its [12] Xuexin Zheng, An Wang, Wei Wei First-
parameters, namely mathematical expectation and order collision attack on protected NTRU
heart-square deviation, is determined and
cryptosystem, Affiliations Microprocessors
substantiated. The choice of the original root for
& Microsystems Volume 37, 2013, pp. 601–
the representation of the base vectors of the
algebraic lattice using fast Fourier transform is 609.
substantiated. It allows to reduce the encryption
complexity for a high level of stability of
transformations based on the NTRU Encrypt
algorithm.
6.References
[1] Gorbenko, Ju. І. Analіz shljahіv rozvitku
kriptografії pіslja pojavi kvantovih
komp’juterіv / Komp’juternі sistemi ta
merezhі: Vіsnik nacіonal'nogo unіversitetu
«L'vіvs'ka polіtehnіka» 806 (2014): 40–49.
[2] Subhash Khot. Hardness of approximating the
Shortest Vector Problem in lattices.Journalof
the AC M, 52(5) (2005) 789–808.
[3] J. M. Pollard, “The Fast Fourier Transform in
a Finite Field,” Mathematics of
Computation, vol. 25, 1971, pp. 365–374.