LINE: Cryptosystem based on linear equations for logarithmic signatures

Abstract

The discourse herein pertains to a directional encryption cryptosystem predicated upon logarithmic signatures interconnected via a system of linear equations (henceforth referred to as LINE). A logarithmic signature serves as a foundational cryptographic primitive within the algorithm, characterized by distinct cryptographic attributes including nonlinearity, non-commutativity, unidirectionality, and factorizability by key. The confidentiality of the cryptosystem is contingent upon the presence of an incomplete system of equations and the substantial ambiguity inherent in the matrix transformations integral to the algorithm. Classical cryptanalysis endeavors are constrained by the potency of the secret matrix transformation and the indeterminacy surrounding solutions to the system of linear equations featuring logarithmic signatures. Such cryptanalysis methodologies, being exhaustive in nature, invariably exhibit exponential complexity. The absence of inherent group computations within the algorithm, and by extension, the inability to exploit group properties associated with the periodicity of group elements, serves to mitigate quantum cryptanalysis to Grover's search algorithm. LINE, predicated upon an incomplete system of linear equations, embodies security levels ranging from 1 to 5, as stipulated by the National Institute of Standards and Technology (NIST), and thus presents a promising candidate for the construction of post-quantum cryptosystems.

Keywords

• eol>LINE
• Post-quantum cryptosystem
• Logarithmic signature
• Directional encryption
• 1

1. Introduction

Computationally complex problems, commonly referred to as "hard problems," encompass a wide array of issues for which a substantial, preferably insurmountable, allocation of resources is necessitated for resolution. Within the realm of cryptography, these problems serve as the foundational bedrock for secure cryptographic schemes. Typically, this is achieved by establishing a correlation between the scheme's security and the infeasibility of solving the associated complex problem. Historically, two predominant complex problems, or their derivatives, have held sway in public-key cryptography: integer factorization and discrete logarithmization. RSA integers and discrete logarithms within finite cyclic groups (DLOG) form the corner-stone of numerous cryptographic constructions [ 1,2,3,4,5 ]. Practical implementations of cryptographic schemes reliant on RSA and DLOG dilemmas are orchestrated such that the selection of parameters introduces convolution into the corresponding crypt-analysis endeavor. In 1994, Shor [ 6 ] elucidated that these conventionally arduous problems can be effortlessly resolved through the utilization of large-scale quantum computers. The trajectory of quantum computing development has increasingly materialized, with prognostications from entities such as Microsoft and IBM anticipating the advent of large-scale quantum computers boasting several thousand qubits by 2030. Such advancements portend a tangible menace to the efficacy of contemporary public-key cryptography in upholding security. Consequently, the cryptographic community, industry stakeholders, and numerous standardization bodies have initiated strategic maneuvers toward the adoption of a quantumresistant alternative: post-quantum cryptography. Post-quantum cryptography, also known as quantum-resistant cryptography, emerges as a pivotal response to the impending vulnerability of classical cryptographic systems in the face of quantum computational prowess. We delve into the fundamental principles, challenges, and promising avenues of post-quantum cryptographic research, elucidating its pivotal role in fortifying the security posture of digital communications and transactions. Amidst the exigency posed by the impending advent of quantum computing, the quest for cryptographic primitives impervious to quantum attacks has garnered substantial impetus. The landscape of quantum-resistant cryptographic primitives, spanning lattice-based, code-based, hashbased, and multivariate polynomial cryptographic schemes is changing almost day by day. Through a comprehensive analysis of their underlying mathematical structures, security properties, and implementation considerations, we aim to furnish readers with insights into the diverse arsenal of cryptographic tools poised to withstand the disruptive potential of quantum adversaries.

2. Motivation

Quantum-resistant cryptosystems, predicated on lattice-based structures, error-correcting linear codes, multidimensional polynomial equations, one-way functions, elliptic curve isogenies, and noncommutative groups, actively leverage computationally complex problems. This mosaic of cryptographic techniques engenders resilience against quantum threats, underpinning a diverse array of cryptographic schemes. The first category encompasses schemes such as FrodoKEM, Kyber, Saber, along with Dilithium, Falcon, and qTESLA signatures, which hinge on the arduous task of training with LWE errors and the short integer solution of SIS. These schemes find application in key encapsulation and directed encryption scenarios. The complexity of decoding linear noisy codes with a secret code is pivotal in schemes like BIKE, Classic McEliece, HQC, NTS-KEM, ROLLO, and CFS, Durandal, WAVE signatures. These schemes rely on the intricate process of deciphering linear noisy codes, thereby fortifying their cryptographic underpinnings [ 7,8,9,10 ]. Furthermore, the complexity inherent in solving multidimensional equations forms the cornerstone of signature schemes such as LUOV, MQDSS, Rainbow, and GeMSS. These schemes exploit the intricacies of multidimensional equations to bolster cryptographic robustness. Likewise, the challenges posed by unidirectional functions are harnessed in signature schemes like XMSS, SPHINCS+, and Picnic, contributing to their quantum resistance [ 11,12,13 ]. Moreover, the complexity entailed in searching for isogenic elliptic curves underscores the security of directional encryption schemes like SIKE and CSIDH, along with signature schemes such as CSI-FiSh and SQISign. Lastly, the complexity arising from the group factorization problem serves as a linchpin in directional encryption schemes. These schemes, spanning from [ 17,18,19,20,21,22,23,24 ], derive cryptographic strength from the intractability of the group factorization problem. The evaluation of quantum security for cryptosystems, submitted to the NIST competition and earmarked as candidates for post-quantum cryptography, undergoes continuous scrutiny and refinement. Recent advancements, detailed in literature [ 25 ], elucidate the construction of polynomial quantum algorithms for solving the LWE problem with polynomial modulus-noise relations. Despite identified algorithmic flaws, novel insights into leveraging complex Gaussian functions and windowed quantum Fourier transforms portend promising avenues for quantum computing applications or novel LWE problem-solving methodologies. As underscored by Bart Prinell's commentary, while the absence of large-scale quantum computers impedes empirical validation of quantum algorithms, the imperative of postquantum encryption remains paramount to ensuring resilience against prospective quantum adversaries [ 26 ]. The current slate of NIST-standard candidates appears robust, albeit subject to refinement through parameter optimization and technological advancements. A fundamental reimagining of cryptosystem design is proposed, wherein the traditional paradigm of leveraging hard-to-solve problems is supplanted by a novel approach predicated on problems boasting a constellation of equivalent solutions devoid of regularities. Such a framework obviates vulnerability to quantum cryptanalysis, relegating adversaries to Grover's algorithm with exponential complexity. Exemplifying this approach, the Shamir threshold secret sharing scheme capitalizes on classical algebraic principles, wherein secrecy is predicated on the unavailability of a critical mass of function values required to reconstruct the overarching secret.

3. Our contribution

Definition of an incomplete cryptosystem of linear equations

The construction of the cryptosystem is predicated upon a well-established algebraic problem, wherein the existence of a unique solution is contingent upon a fully defined system of linear equations. However, when confronted with an incompletely defined system of equations, the enumeration of solutions is governed by the cardinality of the set of potential solutions. In our formulation, we establish linear equations relative to unknowns, utilizing values denoted by logarithmic subscripts. Notably, the number of equations pertaining to secret values of logarithmic signatures is typically fewer than the total number of unknowns. Consequently, this engenders an incomplete system of linear equations vis-à-vis the unknowns, precluding polynomial-time resolution. The crux of any potential attack on such a cryptosystem boils down to the task of sorting and defining variables. The security of a cryptosystem hinged upon a problem featuring incompletely defined equations is contingent upon the robustness of the set of solutions. Central to the algorithm is the concept of logarithmic signature, serving as a foundational cryptographic primitive imbued with distinctive cryptographic attributes, including non-linearity, non-commutativity, unidirectionality, and factorizability by key. Subsequently, we shall delve into a comprehensive exposition elucidating the salient aspects of cryptosystems integrating logarithmic signatures. 3.2

Logarithmic signature

The representation of logarithmic signatures is intricately linked to the positional numbering system, wherein the data array, constituting the logarithmic signature, is structured into subblocks. Each subblock comprises vectors or strings, which can be construed as numerical entities. The encryption process, or cryptogram, is determined by the summation of vectors selected by a designated key (numeric value). The computational security of the cipher hinges upon the formidable challenge of decomposing the cryptogram into constituent vectors in the absence of knowledge regarding the correspondence between vector positions and their respective values. An early instantiation of logarithmic signatures for finite permutation groups was introduced in [ 18 ] within the context of constructing a symmetric cryptosystem. A defining characteristic of such constructions lies in their susceptibility to factorization by key. Subsequent discourse on the algebraic properties of logarithmic signatures and associated cryptosystems was deliberated in depth in [ 19,20 ]. In 2002, Magliveras et al. [ 21 ] devised two public key cryptosystems, MST1 and MST2. Building upon this foundation, Lempken et al. [ 22 ] leveraged logarithmic signatures and random coverages to devise a generalized MST3 encryption scheme. Notably, the public key in this scheme encompasses ordinary logarithmic signatures alongside random numerical entities, while the secret key is constituted by random coverages and sandwich transformations [ 21 ]. The presumed intractability of this scheme hinges upon the group factorization problem within non-Abelian groups. Furthermore, spurred by insights gleaned from attacks detailed in [ 23 ], Svaba and van Trung refined an extended variant of the generalized scheme [ 24 ], denoted as eMST3 cryptosystems. This iteration incorporates a clandestine homomorphism to obfuscate the secret logarithmic signature via a random cover transformation. Subsequent advancements in the MST3 cryptosystem were predicated upon high-order groups encompassing generalized Suzuki groups, small Ree groups, three-parametric groups, automorphism groups of the Suzuki functional field, and automorphisms of the Ree functional field [ 27,28,29,30,31,32,33,34 ]. The efficacy of logarithmic signatures lies in their simplicity, as the computation of text ciphers is facilitated through elementary addition operations utilizing bitwise XOR. However, a notable drawback is the substantial size of logarithmic arrays, necessitating the employment of masking arrays to ensure a commensurately high level of secrecy.

Within the purview of the presented cryptosystem, the logarithmic signature assumes a pivotal role as a fundamental cryptographic primitive facilitating keyless encryption and factorization by means of the logarithmic signature's key. 3.3

Our proposal

Let's consider the main steps of the algorithm.

Step 1. Here we construct of a secret logarithmic signature over a field F (2m ) . The implementation of secret homomorphic transformations with calculations over the field F (2m ) presented in [ 35 ] . Let's construct a logarithmic signature using the following set of secret homomorphic transformations:

1 ⎯⎯1→ 2 ⎯⎯2→3 ⎯⎯3→ 4 ⎯⎯4→5 ⎯⎯5→ , where 1 - simple factorization logarithmic signature type (r1,..., rs )1 ;

Transformation 1 ( 1 ). In this step we make a noise of s blocks of the 1 signature. In this case the signature type does not change. As a result, we get  2 signature. Transformation 2 (  2 ). Next, we shuffling secretly all blocks of  2 signature. As a result, we get  3 signature. Transformation 3 (  3 ). Then, we mix all records in signature blocks  3 . As a result, we get  4 signature. Transformation 4 (  4 ). Next, we proceed with secret homomorphic transformation of array strings in this way:  4 (i) =   3 (i) , i = 1, r1 + r2 + ... + rs ,   F (2m ) . As a result, we get  5 signature. Transformation 5 (  5 ). Finally, we use secret homomorphic transformation of string array  (i) =  4 (i) mm , i = 1, r1 + r2 + ... + rs . As a result, we get  signature. Note, that mm is an invertible binary matrix of dimension m m .

We have a logarithmic signature  =  (i) over m - bit strings as a result of all steps. The security estimation is determined taking to the account a high entropy of secret transformations. These estimates are discussed in [24,35 ÷ 37].

Step 2. Here we construct general parameters, public and secret keys. Let's construct K = k  k logarithmic signatures  K . We present logarithmic signatures  K in the form of a two-dimensional set of arrays with index  k1,k2   K , k1 = 1, k , k2 = 1, k for given types rk1,k2 = (r1,..., rs(k1,k2 ) )k1,k2 , rk1,k2  rK .

 k1,k2 = [B1, B2 ,..., Bs(k1,k2 ) ]k1,k2 := (i, j )k1,k2 , j = 1, s(k1, k2 ) , i = 1, rj .

The index j determines the number of the block and the index i determines the number of the record in j the block. Records of arrays i, j are defined m - bitwise strings that we identify with the elements of the finite field F (2m ) . Let the set  K consist of L factorizable logarithmic signatures  L , L  K i K − L non-factorizable signatures  K −L . Factorized logarithmic signatures  L will be constructed using secret transformations 1  5 . In two-dimensional indexing  k1,k2 , k1 y k2 we determine whether the logarithmic signature belongs to the set  k1,k2   L . We construct nonm factorizable logarithmic signatures  K −L for type (2, 2,..., 2) by filling them with random m -bit strings  1( j) and  2 ( j) , j = 1, m of each block of the logarithmic signature  k1,k2 K −L . Values and indexes k1 and k2 determine belonging to a set of non-factorizable logarithmic signatures  K −L . For logarithmic signatures  k1,k2   L , we generate arrays  k1,k2  L with random records  k1,k2 = [A1, A2 ,..., As(k1,k2 ) ]k1,k2 := (ai, j )k1,k2 , ai, j  F (2m ) / 0 , j = 1, s(k1, k2 ) , i = 1, rj , (r1,..., rs(k1,k2 ) )k1,k2 . the values of the string  1, j , 2, j k1,k2   k1,k2 , ( i, j )k1,k2  F (2m ) / 0 j = 1, m , k1, k2 for each block in  k1,k2 K −L satisfy the following conditions: ( 1, j + 2, j )k1,k2 =  , where i = 1, 2 , j = 1, m ,   F (2m ) / 0 . We generate random sets tk1,k2  tK , tk1,k2 = (t1,..., ts(k1,k2 ) )k1,k2  F (2m ) / 0  k1,k2  K , k1,k2 = ( 1,..., s(k1,k2 ) )k1,k2  F (2m ) / 0 and let (ti, j )k1,k2  ( i, j )k1,k2 , (t j )k1,k2  0 , ( j )k1,k2  0 , i = 1, rj - the number of the record in j = 1, s(k1, k2 ) the block of the array, for the logarithmic  k1,k2 type signature (r1,..., rs(k1,k2 ) )k1,k2

Let's set a secret binary matrix with m m dimensions and let's determine the arrays  k1,k2  K and k1,k2 K . For factorizable logarithmic signatures,  k1,k2   L we define arrays  k1,k2  L and k1,k2 L by following expressions: and similarly, for non-factorable  k1,k2 K −L we define the arrays  k1,k2  GK −L and k1,k2  K −L by following expressions:

( i, j )k1,k2 = (i, j )k1,k2 + (t j )k1,k2 , (i, j )k1,k2 = (i, j )k1,k2 + ( j )k1,k2 for j = 1, s(k1, k2 ) , i = 1, rj . All calculations by  k1,k2  K and k1,k2 K are determined by the rule below. Let the argument for  k1,k2 be m -bit string R . Let's decompose the string R into values according to the type (r1,..., rs(k1,k2 ) )k1,k2 s(k1,k2 ) j−1 logri R = (R1, R2 ,..., Rs(k1,k2 ) ) = 20 R1 + 2logr1 R2 + 2logr1r2 R3 + ... = R1 +  2 i=1 j=2

Rj .

The values R j show the number of the record in j the block of the array  k1,k2  K . Calculations for the argument R are determined by bitwise summation of the array of strings k1,k2  K s(k1,k2 )  k1,k2 (R) =  k1,k2 (R1, R2 ,..., Rs(k1,k2 ) ) =   Rj , j j=1 construction of the cryptosystem is to compute L linear sums  k1,k2 (Rk1,k2 ) = Ul by values  k1,k2 (Rk1,k2 ) . l = 1, L . Let's determine the sums U l by expressions of the form k  ij ( Rij ) = Ui , i = 1, k , j=1 k  ji ( Rji ) = Uk+i , i = 1, k , j=1 k  j ( Rj ) = U2k+i ,  = (k − j + i) mod k +1 , i = 1, k j=1 k   j ( R j ) = U3k+i ,  = (k − i + j) mod k +1 , i = 1, k j=1 Values  ij ( Rij ) are calculated by Rij .

All expressions for U l include only one value  k1,k2 (Rk1,k2 ) from string and/or array column  k1,k2  K . The number of such expressions equal to 4k . Relatively to ij ( Rij ) we get a system of linear equations. Since the number of unknowns  k1,k2 (Rk1,k2 ) is equal to K = k 2 , and the number of knowns U l is equal to L  K , the system of linear equations will be incomplete with respect to the unknowns  k1,k2 (Rk1,k2 ) . For K values of logarithmic signatures,  k1,k2 (Rk1,k2 ) it is easy to calculate L  K the values of U l . The solution of the inverse problem regarding the finding  k1,k2 (Rk1,k2 ) has an uncertainty of 2(K −L)m possible solutions. The cryptosystem has potential (K − L)m bit security.

Example. Let k = 4 . The arrays  k1,k2 which define expressions forU i i = 1, 4k are marked in orange. Please see Fig. 1.). We form L equations of UL that are linearly independent relative to the desired ones  k1,k2  L . We do it to construct the cryptosystem with (K − L)m bits security. Let L = 8 . Let's choose the following eight equations UL = U1,U2 ,U3 ,U5 ,U9 U12 .

Expressions for relatively unknown amounts  k1,k2  K have the following form  11 ( R11 ) + 21 ( R21 ) + 31 ( R31 ) + 41 ( R41 ) = U1  12 ( R12 ) + 22 ( R22 ) + 32 ( R32 ) + 42 ( R42 ) = U2  13 ( R13 ) + 23 ( R23 ) + 33 ( R33 ) + 43 ( R43 ) = U3  11 ( R11 ) + 12 ( R12 ) + 13 ( R13 ) + 14 ( R14 ) = U5 The solution for the unknowns  k1,k2  L can be expressed in the following expressions:  11 ( R11 ) = U9 + 24 ( R24 ) + 33 ( R33 ) + 42 ( R42 )  12 ( R12 ) = (U3 +U5 +U9 +U12 ) + 24 ( R24 ) + 32 ( R32 ) + 41 ( R41 ) + 42 ( R42 ) + 43 ( R43 )  13 ( R13 ) = (U1 +U2 +U9 +U10 +U11) + 24 ( R24 ) + 32 ( R32 ) + 33 ( R33 ) + 34 ( R34 ) + 41 ( R41 ) + 43 ( R43 ) + 44 ( R44 )  14 ( R14 ) = (U1 +U2 +U3 +U9 +U10 +U11 +U12 ) + 24 ( R24 ) + 34 ( R34 ) + 44 ( R44 )  21 ( R21 ) = (U3 +U5 +U9 +U10 +U12 ) + 24 ( R24 ) + 32 ( R32 ) + 34 ( R34 ) + 41 ( R41 ) + 42 ( R42 )  22 ( R22 ) = (U2 +U3 +U5 +U9 +U12 ) + 24 ( R24 ) + 41 ( R41 ) + 43 ( R43 )  23 ( R23 ) = (U1 +U2 +U3 +U9 +U10 +U11) + 24 ( R24 ) + 32 ( R32 ) + 34 ( R34 ) + 41 ( R41 ) + 44 ( R44 )  31 ( R31 ) = (U1 +U3 +U5 +U10 +U12 ) + 32 ( R32 ) + 33 ( R33 ) + 34 ( R34 ) Thus, to calculate the values,  11, 12 , 13, 14 , 21, 22 , 23, 31  L one should define  24 , 32 , 33, 34 , 41, 42 , 43, 44  GK−L .

Step 4. Encryption. To implement encryption we consider the following input parameters: x long Lm bit message, public keys  K , K , hash function h . Encryption step consists of the following routines. We divide the message x into m -bit strings, which are converted into a set of L input parameters Rij for L factorizable logarithmic signatures  k1,k2   L according to their type (r1,..., rs(k1,k2 ) )k1,k2 . Next, we calculate the hash value h(x) for Lm the bit string of the message x that can be present with K − L m -bit strings with subsequent transformation  (h(x)) = Rk1,k2 into a set of input parameters Rij for K − L non- factorable logarithmic signatures k1,k2 K−L in accordance with m the type (2, 2,..., 2) . The hash function h(x) is unidirectional and sensitive to bit changes in the message x . We can also add a session key to the display  (h(x)) = Rk1,k2 to randomize the cipher text in the case of low entropy of the message x . Then, we calculate the values of  k1,k2 (Rk1,k2 ) and k1,k2 (Rk1,k2 ) k1 = 1, k , k2 = 1, k . Then, we calculate L the values of linear sums for  k1,k2 (Rk1,k2 ) = Ul , Ul UL . Finally, we calculate L sums of k1,k2 (Rk1,k2 ) = Vl , Vl VL using similar expressions for UL .

The encryption result is recognized as a L m -bit values Ul UL and Vl VL .

Step 5. Decryption. To implement decryption we consider the following input parameters: a cipher text Ul U L , Vl VL , secret keys  K , tK ,  K , . It is necessary to calculate  k1,k2  L and to calculate Rk1,k2  RL and restore x through the factorizable signatures  k1,k2   L . To calculate,  k1k2 ( Rk1k2 )  L you need to subtract the values  k1,k2  GK −L from the sums of the set UL . Decryption consists of the following steps. First, we calculate Dl = Ul + Vl + tl + l , l = 1, L . The values U l contain sums for subsets of factorizable and non-factorizable signatures k1,k2  L  k1,k2  L .

The values Vl contain similar sums for subsets k1,k2 L and k1,k2 L

Ul = Vl =

  k1,k2 (Rk1,k2 ) +   k1,k2 (Rk1,k2 )  k1,k2 L  k1,k2 L

 k1,k2 (Rk1,k2 ) +  k1,k2 (Rk1,k2 ) k1,k2L k1,k2L

Finally, we find factorization Rk1,k2 =  k−11,k2 (Rk1,k2 ) and restore the message x . 3.4

Security analysis

There are several brute force attacks are considered as follows. First one is a brute-force of the input message x within an encryption and verification for the coincidence of ciphertexts. The complexity of this attack equals N1 = 2Lm . Next is a brute-force of ciphertexts U l , Vl , l = 1, L via solving of a system of linear equations relative to logarithmic signatures and the subsequent attack on logarithmic signatures. The complexity of this attack equals N2 = 22Lm . Then, we consider brute-force of a secret homomorphic transformation  , calculation Dl and attack on logarithmic signatures. The secret transformation  is based on matrix multiplication. A brute force attack by selection  has a complexity 2m2 where m the dimension of the matrix is  mm . Also, analytical attacks on secret transformation  can be proposed as follows: Arrays of  k1,k2  L and k1,k2 L for factorizable logarithmic signatures  k1,k2   L are defined by expressions: where (i, j )k1,k2  0 , (t j )k1,k2  0 , ( j )k1,k2  0 i = 1, rj is the record`s number in j = 1, s(k1, k2 ) the array block, for a logarithmic signature  k1,k2 of the type (r1,..., rs(k1,k2 ) )k1,k2 . Let (i, j )k1,k2 + (t j )k1,k2  0 . The values ( i, j )k1,k2 , (t j )k1,k2 , ( j )k1,k2 are considered secret and there is no mapping

( i, j )k1,k2 = ( i, j )k1,k2 + (i, j )k1,k2 + (t j )k1,k2 and it is impossible to construct equations relatively

(i, j )k1,k2 = ( i, j )k1,k2 + (i, j )k1,k2 + (t j )k1,k2 .

It is possible to try to strengthen the attack based on the addition of records ( i, j )k1,k2 within (i, j )k1,k2 the block of arrays. Since the value of the secret parameter (t j )k1,k2 is constant for the entries ( i, j )k1,k2 in j the block of the array  k1,k2 and the secret parameter ( j )k1,k2 is constant for the entries (i, j )k1,k2 in the corresponding j block of the array, k1,k2 it is possible to consider the sums ( i, j )k1,k2 and (i, j )k1,k2 ( i1, j )k1,k2 + ( i2 , j )k1,k2 = (i1, j )k1,k2 + (i2 , j )k1,k2 + (( i1, j )k1,k2 + ( i1, j )k1,k2 ) without (t j )k1,k2 , (i1, j )k1,k2 + (i2 , j )k1,k2 = ( i1, j )k1,k2 + ( i1, j )k1,k2 without ( j )k1,k2 .

Since (i1, j )k1,k2  (i2 , j )k1,k2 , there is no mapping

(( i1, j )k1,k2 + ( i1, j )k1,k2 ) = ( i1, j )k1,k2 + ( i2 , j )k1,k2 + (i1, j )k1,k2 + (i2 , j )k1,k2 and it is impossible to obtain a solution to the equation

((i1, j )k1,k2 + (i1, j )k1,k2 ) = ( i1, j )k1,k2 + ( i2 , j )k1,k2 + (i1, j )k1,k2 + (i2 , j )k1,k2 relatively to  . Also, there are following analytical attacks on  non-factorizable logarithmic signatures  k1,k2   L are considered. The first attack on  is based on the analysis of records in arrays  k1,k2  L and k1,k2 L ( i, j )k1,k2 = (i, j )k1,k2 + (ti, j )k1,k2 , (i, j )k1,k2 = (i, j )k1,k2 + ( i, j )k1,k2 , i = 1, 2 . The values (ti, j )k1,k2 and ( i, j )k1,k2 are considered as a secret ones (t1, j )k1,k2 = (t2, j )k1,k2 = (t j )k1,k2 , ( 1, j )k1,k2 = ( 2, j )k1,k2 = ( j )k1,k2 and it is impossible to obtain ratios (i, j )k1,k2 + ( i, j )k1,k2 = ( i, j )k1,k2 + (ti, j )k1,k2 to compute  . The second attack on  is based on the observation that the values of the secret parameters (t j )k1,k2 and ( j )k1,k2 are constant in each j block of the array of records ( i, j )k1,k2 and (i, j )k1,k2 . It is possible to strengthen the attack on  , if we consider the sum of records ( 1, j )k1,k2 + ( 1, j )k1,k2 and (1, j )k1,k2 + (2, j )k1,k2 within blocks of arrays ( i, j )k1,k2 and (i, j )k1,k2 ( i, j )k1,k2

It is possible to obtain an equation for calculation ( 1, j )k1,k2 + ( 2, j )k1,k2 = ((1, j )k1,k2 + (1, j )k1,k2 + (1, j )k1,k2 + (1, j )k1,k2 ) , (1, j )k1,k2 + (2, j )k1,k2 = (1, j )k1,k2 + (1, j )k1,k2 + (1, j )k1,k2 + (1, j )k1,k2 .

((1, j )k1,k2 + (2, j )k1,k2 ) = ( 1, j )k1,k2 + ( 2, j )k1,k2 .

Taking into account the requirement ( 1, j + 2, j )k1,k2 =  for the values of the strings  1, j , 2, j k1,k2   k1,k2 , j = 1, m , k1, k2 we obtain a unique equation for all blocks of the array of records  = ( 1, j )k1,k2 + ( 2, j )k1,k2 z .

Since the equation is written only for one m bit string, and the number of required values of the binary matrix  is equal to m2 , there remains uncertainty in m2 − m bits regarding the coefficients of the matrix  . Complexity of the attack N3 = 2m2 −m . arrays of logarithmic signatures  k1,k2   L , so that then we obtain a relatively solvable  equation (ti, j )k1,k2 = 0 and

 i1,2, j( j1,..., jn ) ( i, j )k1,k2 = 0 , The third attack on  is determined by the possibility of constructing sums from n  2 entries on  i1,2, j( j1,..., jn ) cases of equality of zero

 i1,2, j( j1,..., jn )

 (i, j )k1,k2 =  (i, j )k1,k2 .

i1,2, j( j1,..., jn 0 i1,2, j( j1,..., jn ) A system of m linear equations allows you to find a solution relatively

 (i, j )k1,k2 =  ( i, j )k1,k2 .

i1,2, j( j1,..., jn ) i1,2, j( j1,..., jn )

The system of equations is based on the selection of m bit records from the arrays of values of logarithmic signatures in the sets ( i, j )k1,k2 (i, j )k1,k2 , the sums of the entries in which contain  (ti, j )k1,k2 = 0  i1,2, j( j1,..., jn ) i1,2, j( j1,..., jn ) secret, the values of the sums

 (ti, j )k1,k2 cannot  i1,2, j( j1,..., jn ) i1,2, j( j1,..., jn ) assumed with probability 2−2m , what the selected entries in sets ( i, j )k1,k2 = 0 . Since the values of (ti, j )k1,k2 and ( i, j )k1,k2 are considered ( i, j )k1,k2 be predicted and can be

 i1,2, j( j1,..., jn ) ( i, j )k1,k2 and (i, j )k1,k2 will be equal to zero. To build a system of equations,  it is necessary to have m  i1,2, j( j1,..., jn ) (ti, j )k1,k2 both

 i1,2, j( j1,..., jn ) ( i, j )k1,k2 in the sums

 i1,2, j( j1,..., jn ) ( i, j )k1,k2 and (i, j )k1,k2 for each calculation  . The probability of such an event can be estimated by the value of 2−2m2 . An important issue is establishing the fact that the matrix calculated  by the system of equations for a random set (i, j )k1,k2 the desired one. ( i, j )k1,k2 is Representations of arrays  k1,k2  L and k1,k2 L do not allow verification (i, j )k1,k2 = ( i, j )k1,k2 due to  i1,2, j( j1,..., jn )

 i1,2, j( j1,..., jn ) secrecy (ti, j )k1,k2 , ( i, j )k1,k2 .

Finally, we can evaluate of the quantum secrecy of directional encryption based on a cryptosystem with an incomplete system of linear equations. The cryptosystem security for directional encryption is based on the secrecy of the homomorphic matrix transformation and the incompleteness of the linear equations relative to the values of the logarithmic signatures. The impossibility of an algebraic solution regarding the uncertainty of the matrix transformation is determined by the incomplete definition of systems of linear equations for matrix equations and a probabilistic assessment of the possibility of constructing such a system of equations. The absence of a mechanism for verifying the truth of solutions for an attack on a secret matrix transformation based on random samples of records of logarithmic signatures indicates a probabilistic assessment of the success of the attack. It is not possible to formulate a target function for a quantum algorithm for such an attack. A similar attack on the algebraic solution relative to the values of the logarithmic signatures due to the indeterminacy of the linear equations also cannot be formalized with a target function for the quantum algorithm. A quantum attack based on Grover's algorithm with exponential complexity is possible for the search attack of the input text based on the given cipher text. It appears that polynomial attacks on the algorithm are not possible, since the data in the algorithm (records of arrays  k1,k2 and k1,k2 ) are structured as random sets without regularities. Simple logarithmic signatures are well structured, however, secret transformations used to construct protected logarithmic signatures introduce strong randomization in array records. 3.5

Security parameters evaluation

We consider the general parameters of the cryptosystem as follows: m -bit length of logarithmic signatures; K as a number of logarithmic signatures in the cryptosystem; L as a number of factorizable logarithmic signatures in the cryptosystem; rK types of logarithmic signatures. Below 4. Conclusions A cryptosystem based on an incomplete system of linear equations with respect to logarithmic signatures is a good candidate for post-quantum cryptography. The incompleteness implemented in the algorithm for systems of linear equations guarantees undecidability with respect to secret logarithmic signatures and secret matrix transformation. Quantum secrecy is based on the high randomization of records in arrays of logarithmic signatures and the absence of regularities in the structured data of the algorithm. The directional encryption algorithm is well-scalable with respect to computing costs, memory, and limitations of hardware platforms without reducing the high level of secrecy. Due to the selection of the general parameters of the cryptosystem, the declared NIST levels of secrecy of 128, 192, 256 bits are realized. The cost of public keys when calculating over words of 16, 32 bits is in the range of 1 ÷ 4 Kbytes and is comparable to implementations for the best candidates for post-quantum cryptography. The basic computational operation of the algorithm is bitwise XOR over the words of logarithmic arrays.

References

[1] R. L. Rivest , A. Shamir , L. M. Adleman A method for obtaining digital signatures and publickey cryptosystems . Communications of the Association for Computing Machinery, 21 2 ( 1978 ) 120 126 .

[2] M. O. Rabin , Digital signatures and public key functions as intractable as factorization . Technical Rep

[3] H. C. Williams , Some public key crypto-functions as intractable as factorization, in: GR Blakley and David Chaum , editors, CRYPTO'84 , Springer, Heidelberg, volume 196 of LNCS , 1984 , pp. 66 70 .

[4] S. Goldwasser , S. Micali , Probabilistic encryption and how to play mental poker keeping secret all partial information , in :14th ACM STOC , ACM Press, 1982 , pp. 365 377 .

[5] P. Paillier , Public-key cryptosystems based on composite degree residue classes , in Jacques Springer, Heidelberg, volume 1592 of LNCS , 1999 , pp. 223 238 .

[6] P.W. Shor , Algorithms for quantum computation: Discrete logarithms and factoring , in: 35th FOCS IEEE Computer Society Press, 1994 , pp. 124 134 .

[7] R. J. McEliece , A public-key cryptosystem based on algebraic coding theory . The deep space January/February 1978 .

[8] N. Aragon , P. Barreto , S. Bettaieb , L. Bidoux , O. Blazy , J.-C. Deneuville , P. Gaborit , S. Gueron , T. Guneysu , C. A. Melchor , R. Misoczki , E. Persichetti , N. Sendrier , J.-P. Tillich , G. Zémo , V. Vasseur , S. Ghosh, BIKE. Technical report, National Institute of Standards and Technology , 2020 .

[9] C. A. Melchor , N. Aragon , S. Bettaieb , L. Bidoux , O. Blazy , J.-C. Deneuville , P. Gaborit , E. Persichetti, G. Zémor, J. Bos, HQC. Technical report, National Institute of Standards and Technology , 2020 .

[10] M. R. Albrecht , D. J. Bernstein , T. Chou , C. Cid , J. Gilcher , T. Lange , V. Maram , I. rich, R. Misoczki, R. Niederhagen , K. G. Paterson , E. Persichetti , C. Peters , P. Schwabe , N. Sendrier , J. Szefer , C. Jung Tjhai , M. Tomlinson , W. Wang , Classic McEliece . Technical report, National Institute of Standards and Technology , 2020 .

[11] L. Lamport , Constructing digital signatures from a one8 , SRI International Computer Science Laboratory, October 1979 .

[12] R. C. Merkle , A certified digital signature , in: Gilles Brassard, editor, CRYPTO'89 , Springer, Heidelberg, volume 435 of LNCS , 1990 , pp. 218 238 .

[13] J. Rompel , One-way functions are necessary and sufficient for secure signatures , in: 22nd ACM STOC , ACM Press, 1990 , pp. 387 394 .

[14] D. Jao , R. Azarderakhsh , M. Campagna , C. Costello , L. De Feo, B. Hess , A. Jalali , B. Koziel , B. LaMacchia, P. Longa, M. Naehrig , J. Renes , V. Soukharev , D. Urbanik , G. Pereira, K. Karabina A. Hutchinson , SIKE. Technical report, National Institute of Standards and Technology , 2020 .

[15] W. Beullens , T. Kleinjung , F. Vercauteren , class group computations, in: Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019 , Springer, Heidelberg, Part I , volume 11921 of LNCS , 2019 , pp. 227 247 .

[16] L. De Feo , D. Kohel , A. Leroux , C. Petit , B. Wesolowski, signatures from quaternions and isogenies , in: Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020 , Springer, Heidelberg, Part I , volume 12491 of LNCS , 2020 , pp. 64 93 .

[17] N.R. Wagner , M.R. Magyarik , A public-key cryptosystem based on the word problem , in: Proc. Advances in Cryptology - CRYPTO 1984 , LNCS 196, Springer-Verlag, 1985 , pp. 19 36 .

[18] S.S. Magliveras , A cryptosystem from logarithmic signatures of finite groups , in: Proceedings of the 29th Midwest Symposium on Circuits and Systems , Elsevier Publishing, Amsterdam, The Netherlands, 1986 , pp. 972 975 .

[19] S. S. Magliveras , N.D. Memon , Algebraic properties of cryptosystem PGM , Journal of Cryptology 5 3 ( 1992 )167 183 .

[20] A. Caranti , F. Dalla Volta , The round functions of cryptosystem PGM generate the symmetric group , Designs, Codes and Cryptography 38 1 ( 2006 ) 147 155 .

[21] S. Magliveras , D. Stinson , T. van Trung, New approaches to designing public key cryptosystems using one-way functions and trapdoors in finite groups , Journal of Cryptology 15 4 ( 2002 ) 285 297 .

[22] W. Lempken , S.S. Magliveras , T. van Trung and W. Wei , A public key cryptosystem based on non-abelian finite groups , J. of Cryptology , 22 ( 2009 ) 62 74 .

[23] S. S. Magliveras , P. Svaba , T. van Trung, P. Zajac , On the security of a realization of cryptosystem MST3 , Tatra Mountains Mathematical [16 1] Publications 41 ( 2008 ) 65 78 .

[24] P. Svaba , T. van Trung, Public key cryptosystem MST3 cryptanalysis and realization , Journal of Mathematical Cryptology 4 3 ( 2010 ) 271 315 .

[25] Y. Chen Quantum Algorithms for Lattice Problems April 18, 2024 . URL: https://eprint.iacr.org/ 2024 /555.pdf.

[26] B. Prinell , Social Network Post. URL: https://www.linkedin.com/posts/bart-preneel4451412_ lattice-based-cryptography-no-panic-but-activity-7184684082159603713- pxkX?utm_source=share&utm_medium=member_desktop.

[27] G. Khalimov , Y. Kotukh , S. Khalimova , Encryption scheme based on the automorphism group of the Ree function field , in: 2020 7th International Conference on Internet of Things: Systems, Management and Security (IOTSMS) , IEEE, 2020 , pp. 1 8 .

[28] G. Khalimov , I. Didmanidze , O. Sievierinov , Y. Kotukh , O. Shonia , Encryption scheme based on the automorphism group of the Suzuki function field , in: 2020 IEEE International Conference on PROBLEMS OF INFOCOMMUNICATIONS. SCIENCE AND TECHNOLOGY PIC ST2020 October 6-9 , 2020 .

[29] G. Khalimov , Y. Kotukh , S. Khalimova , Improved encryption scheme based on the automorphism group of the Ree function field , in: 2021 IEEE International IOT , Electronics and Mechatronics Conference (IEMTRONICS) , IEEE Xplore: 14 May 2021 , DOI: 10.1109/ IEMTRONICS52119. 2021 . 9422514 .

[30] G. Khalimov , Y. Kotukh , O. Sievierinov , S. Khalimova , S.- Y. Chang , Y. Balytskyi , Strong Encryption Based on the small Ree groups , in: 12 , 2022 .

[31] G. Khalimov , Y. Kotukh , S. Khalimova , O. Marukhnenko , D. Tsyplakov , Towards advance encryption based on a Generalized Suzuki 2-groups , in: International Conference on Electrical, Computer, Communications and Mechatronics Engineering, ICECCME 2021 , 2021 .

[32] G. Khalimov , Y. Kotukh , S. Khalimova , Encryption scheme based on the automorphism group of the Ree function field , in: 2020 7th International Conference on Internet of Things: Systems, Management and Security (IOTSMS) , 2020 , pp. 1 8 .

[33] G. Khalimov , Y. Kotukh , S. Khalimova, MST3 cryptosystem based on a generalized Suzuki 2 groups , in : CEUR Workshop Proceedings , 2020 , 2711 , 2020 , pp. 1 15 .

[34] G. Khalimov , Y. Kotukh , S. Khalimova, MST3 cryptosystem based on the automorphism group of the Hermitian function field , in: 2019 IEEE International Scientific-Practical Conference Problems of Infocommunications, Science and Technology (PIC S&T) , 2019 , pp. 865 868 .

[35] P. Svaba , Covers and logarithmic signatures of finite groups in cryptography , Dissertation , 2022 .

[36] S. R. Blackburn , C. Cid , C. Mullan , Cryptanalysis of the mst3 public key cryptosystem . Journal of Mathematical Cryptology , 3 4 ( 2009 ) 321 .

[37] W. Lempken , T. van Tran, S. S. Magliveras , W. Wei , A public key cryptosystem based on nonabelian finite groups . Journal of Cryptology, 22 1 ( 2009 ) 62 74 .