On Eulerian Transformations and Postquantum Access Control Protocol-Based Algorithms

Abstract

The paper is dedicated to applications of Noncomutative Cryptography to access control algorithms for Information Systems. The example of usage of the protocol based on multivariate transformations to access control tasks is given. The platforms for such protocols are subsemigroups of affine Cremona semigroup acting on affine space of dimension n with Multicomposition property, i.e. ability to make computation of the composition of n elements from subsemigroup in polynomial time T(n).The implementation of the algorithm is given in the case of platform of Eulerian transformations. The modification of main algorithm is based on the idea of combination of Eulerian Transformations with elements of affine Cremona group of bounded degree and polynomial density. Access control, noncommutative cryptography, multivariate cryptography, multicomposition property, Eulerian transformations, one-time pad.

1. Introduction

Protocol based approach to control access to information systems in information space is a very

popular one. With the appearance of the first samples of quantum computers it is very important to investigate potential of this approach. We study new postquantum resistant multivariate protocols which can substitute unresistable to quantum computer based attacks Diffie-Hellman algorithm. Current state of research in Postquantum Multivariate Cryptography is presented on the web page of the future Satellite Conference “Mathematical Aspects of Post Quantum

Cryptography” of the

Mathematical Congress 2022 (see https://icm2022.org/satellites). One of the sixth main directions of the Post Quantum Cryptography is Multivariate Cryptography for which affine Cremona semigroup named after Luigi Cremona [1] and its multivariate transformations are the main instruments to create cryptographical algorithms. These transformations are induced by endomorphisms of polynomial ring K[x1, x2 ,..., xn ] over commutative ring K. The case K=Fq of finite field is very popular in classical

Multivariate

Cryptography. We discover large subgroups of

CSn(K), n=2,3,… with the Multicomposition property (MCP) which means possibility to compute the composition of N arbitrary chosen elements of CSn(K) in polynomial time T(n). We assume that each element of CSn(K) is given in its standard polynomial form xi  fi (x1, x2 ,..., xn ), i=1,2,…n. 2. On

Multivariate

Protocols of

Noncommutative

CRYPTOGRAPHY and Access Control

Tahoma protocol was introduced in [2]. It uses two semigroups Sn<SCn(K) and Sm<CSm(K), m<n

2022 Copyright for this paper by its authors. elements g'1 , g'2 ,..., g'k from Sn together with elements h1, h2 ,..., hk from Sm conjugated with  (g'1 ), (g'2 ),..., (g'k ).

Alice sends pair (gi, hi), i=1, 2,…,k to Bob.

Bob selects sequences w( 1 )=(i( 1,1 ), i( 2,1 ), …, i(l( 1 ),1), w( 2 )=(i( 1,2 ), i( 2,2 ), …, i(l( 2 ),2),, …., w(s)=(i(1,s), i(2,s), …, i(l(s),s) of elements from {1,2,…,k}

He sends g(j)=gi(1,j)gi(2,j), … gi(l(j),j), j=1,2,…,s to Alice. Bob keeps z(j)=hi(1,j)hi(2,j), … hi(l(j),j), j=1,2,…,s in his private storage.

Alice restores z(j) because of her knowledge on the input data. Postquantum seсurity of the

protocol rests on the problem of decomposition of w(i) into generators gi .

Access control algorithm.

Alice (administrator of information system) forms pseudorandom or genuine random system (p1,

p2,…,pm) from Km and word w in the alphabet z( 1 ), z( 2 ),…,z(s). Alice sets password as w(p). Bob enters w(p) and gets access to the system.

Algorithm is implemented with various platforms Sn, Sm and homomorphism between them (see

[3–5]).

3. Case of Eulerian Platform

Let us consider the case when Sn and Sm are subsemigroups of semigroups ESn(K) and ESm(K) of

Eulerian transformations, i.e. transformations moving each variable xi into monomial term qix1α(i,1)x2α(i,2)…xnα(i,n) (t=n or t=m) where qi are regular elements of K and a(i,j) from Zd ,d=|K*|. These transformations were used for the development of public key algorithms [6, 7] and key exchange protocols [8] and key generation algorithm of one time pad encryption [9].

For simplicity we assume that algorithm has two outputs z(1) and z(2) with coefficients qi, a(i,j) and q’i, a’(i,j) respectively. Alice and Bob use generator of pseudorandom sequence (r1, r2 ,…,rm)=r where ri, are from K*.

They form formal word w of kind z( 1 ) α( 1 ) z( 2 ) α( 2 ) z( 1 ) α( 3 ) … or z( 2 ) b( 1 )z( 1 ) b( 2 )z( 2 ) b( 3 ) … of length k, k=O( 1 ) and use w(r) as entrance password.

It is clear that the execution time of the protocol is O(n 3) which is the time to compute the

composition of the elements from ESn(K).

The computation of the entrance password costs O(m2) because Alice and Bob use publicly known

decomposition of w into hidden z( 1 ) and z( 2 ).

Assume that Alice and Bob use word w without change and the adversary is able to intercept some

pairs (r, w(r)) where unknown w is of kind xi →yi x1 y(i,1) x2 y(i,2)… xm y(i,m) , i=1,2, …, n .The word depends on m2+m unknowns. So Alice and Bob can use unchanged word safely <m+1 times.

With this restrictions the only option for adversary is to break postquantum safe protocol. So Alice

and Bob can use various words w during practically unlimited time. Noteworthy that they can change the size of parameter m via new session of the protocol with the same or new platform.

Alternative usage. In this case correspondents can use the protocol with several outputs for the

generation of password for “multiplicative” one time pad with plainspace (K*) m and encryption function (x1 , x2 ,…, xm )→( x1p1, x2p2 , …, xmpm) where p=(p1, p2 ,…, pm) is the password.

They form password via described above process of generation pairs (w , r) and setting p=w(r).

Password has to be used only one time.

Noteworthy that in the case K=Fq correspondents can use plainspace Kn and additive one time pad with encryption function (x1 , x2 ,…, xm )→( x1 + p1, x2 + p2 , …, xm + pm).

4. An Example of Implementation

Let us consider an Eulerian semigroup ESn(K), which is a subsemigroup of CSn(K) of transformations of kind xi→ti(x1,x2,…,xn), where ti are monomial terms in K[x1,x2,…,xn]. Let LEn(K) be a subsemigroup of ESn(K) of kind

x1→q1x1a( 1,1 ) L: x2→q2a21x1a( 2,1 )x2a( 2,2 )

… xn→qnan1x1a(n,1)x2a(n,2)…xna(n,n) where qi are regular element of K together with subgroups UEn(K) of transformations of kind x1→q1x1a( 1,1 )x2a( 1,2 )…xna(1,n) U: x2→q2x1a( 2,1 )x2a( 2,2 )…xn-1a(2,n-1) … xn→qnx1a(n,1)

Notice that in the case of finite K map L is invertible transformation of (K*)n if a(1,1), a(2,2),…,

a(n,n) are mutually prime with d=|K*|. Similarly U induces a bijection of K* if a(n,1), a(n

1,1),…,a(1,1) are mutualy prime with d.

Assume that m<n. We consider a parabolic semigroup Pn,m(K) of all transformations of kind x1→q1x1a( 1,1 )x2a( 1,2 )…xma(1,m) x2→q2x1a( 2,1 )x2a( 2,2 )…xma(2,m)

… xm→qm x1a(m,1)x2a(m,2)…xma(n,m) xm+1→qm+1x1a(m+1,1)x2a(m+1,2)…xma(m+1,n) xm+2→qm+2x1a(m+2,1) x2a(m+2,2)… xma(m+2,n)

… xn→qnx1a(n,1) x2a(n,2) …xna(n,n)

Let φn,m(g) be the restriction of g є Pn,m(K) onto variables x1, x2,…,xm. It is easy to see that φn,m is a

homomorphism of Pn,m(K) onto ESm(K). We consider a special case of Tahoma protocol presented in [2].

Alice takes transformations p1, p2,…, pt є Pn,m(K) with pseudorandom coefficient for pi given by

list iq1, iq2,…, iqn, from K* and ia(i,j) from Zd., d=|K*|. Alice takes L є LEn(K) given by coefficients b(i,j), i≤j, qi є K*, i=1,2,…,n and U є UEn(K) with coefficients c(i,j), j≤i and qi’ є K*, i=1,2,…,n. We assume that b( 1,1 ), b( 2,2 ),…, b(n,n) and c(1,n), c(2,n),…, c(n,n) are mutually prime with d=|K*|.

Alice forms elements p1, p2,…, pt ai=ULpiU-1L-1 , i=1,2,…n where U-1 and L-1 are inverse automorphisms for U and L from AutK[x1,x2,…,xn]. She computes bi=φ(pi) and takes automorphism U’ є UEm(K) and L’ є LEm(K).

Alice computes bi=U’L’φ(pi)(U’L’)-1, where U’єUEm(K), L’єULm(K) and sends pairs (ai,bi) to Bob.

Bob takes sequences rj(1,r), rj(2,r),…, rj(l(r),r)є{1,2,…,t}, r є{1,2,…, k} and forms wr=aj(1,r)aj(2,r)…aj(l®, r) and wr’= bj(1, r)bj(2,r)…bj(l®, r). He sends wr to Alice and keeps wr’ for himself.

Alice restores w’r via computation of L-1(U’)-1wr’LU=v, φ(v) and U’L’φ(v)(U’L’)-1. zr=w’r are collision elements (outputs) of the protocol. The complexity of algorithm is established by the complexity of composition of two elements from ESn(K) which is O(n3).

The protocol can be used for the presented access control algorithm. Correspondents can use

strings (r1,r2,…,rm)є(K*)n to form entrance password to the system.

5. Algorithm Modification

Assume that zr is given by the rule x1→rq1x1 a(1,1,r)x2a(1,2,r)…xm a(1,m,r) x2→rq2x2a(2,1,r) x2a(2,2,r)… xm a(2,m,r)

… xn→rqmxm a(m,1.r)x2a(m,2,r)… xn a(m,m,r) … … We form zr via consideration of g1(r)=rq1rq1x1a(1,1,r)+ q1rq2x2a(1,2,r)+rq1rqmxma(1,m,r) r g2(r)=rq2rq1x1a(1,1,r)+rq2rq2x2a(1,2,r)+rq2rqmxma(1,m,r) … and the map

x1→g1(r),x2→g2(r), …,xn→gn(r)

We define Gi(1)i(2)…i(k) as the rule

x1→g1(i( 1 ))g1(i( 2 ))…g1(i(k)), x2→g2(i( 1 ))g2(i( 2 ))…g2(i(k)), … xm→gm(i( 1 ))gm(i( 2 ))…gm(i(k)).

5.1. Modified Access Control Algorithm Based on Protocol

Alice and Bob selects two strings (j( 1 ), j( 2 ),…j(k( 1 )))є{1,2,…,t}k( 1 ) and (i( 1 ), i( 2 ),…i(k( 2 )) є{1,2,…,t}k( 2 ).

They form composition Zj( 1 ),j( 2 ),…,j(k( 1 )) of Zj( 1 ), Zj( 2 ), …, Zj(k( 1 )) from ESm(K) and compose it with Gi( 1 )i( 2 )…i(k( 2 )) єCSm(K). They will use this composition C=C(j( 1 ),j( 2 ),…j(k( 1 )),i( 1 ),i( 2 ),…,i(k( 2 )) of Zj( 1 ),j( 2 ),…,j(k( 1 )) and Gi( 1 )i( 2 )…i(k( 2 )) in affine Cremona group formally, i. e. without computation of the standard form.

In fact they create string r=(r1,r2,…,rm)є(K*)m and compute C=C(r) with the usage of decomposition C into Z= Zj( 1 ),j( 2 ),…,j(k( 1 )) and G= Gi( 1 )i( 2 )…i(k) and given above formula in the definitions of Z and G.

Notice that standard forms C are of degree αm for some constant α, the density of C, i.e total

number of monomials in its standard form is O(mk( 2 )+1). So the task of adversary to interpolate C via interceptions of pairs of kind r, c(r) is impossible task.

So the only option for adversary is to break the suggested above postquantum protocol.

5.2. On the Symbiotic Combination with One Time Pad

Classical one time pad over additive group K+ of the ring K is encryption function on the

plainspace Kn given by the rule (x1,x2,…xm →(x1,x2,…xm)+(p1,p2,…,pm)= (y1,y2,…,ym) where password (p1,p2,…,pm) and ciphertext (y1,y2,…,ym).

Alice and Bob can use it via generation of passwords C(j( 1 ),j( 2 ),…j(k( 1 )),i( 1 ),i( 2 ),…,i(k( 2 ))(r) generated via suggested above protocol based scheme.

Complexity remarks

1) The complexity of protocol is O(m3)

2) The computation of Z(i) in the point (r1,r2,…,rm) takes O(m2)

3) Generation of g(m) takes O(m2)

The complexity of algorithm is O(m2(k(1)))+O(m2(k(2))). Suggestion: correspondents can select

k( 1 ) and k( 2 ) of size O(m). Then complexity of entire algorithm is O(m3).

The algorithm is implemented in the cases of finite fields and arithmetical rings of residues

modulo q. q>2.

6. Conclusion

The paper gives an example of application of protocols of Noncommutative Cryptography (see [10–23]) to the problems of Access Control for Information Systems.

The general scheme can be the following one. Alice and Bob use protocol based on the input (IAS)

and output algebraic systems (OAS) given by some generators a1, a2,…, an and b1, b2, …, bm respectively. Correspondents elaborate in a secure way some elements c1, c2,…, ct which generates the special subsystem (RIS) of OIS. They take element w=w(c1, c2,…,ct) which is known function from hidden generators ci.

Finally they use some ‘’deformation rule” d to form entrance password d(w) for some Information

System IS. 254

For the selection of appropriate protocol recent cryptanalytical results [24–26] can be used.

Flexibility of the method allows generalization for the case of multiuser mode. Descriptions of cryptographical problems in access control technology and alternative solutions reader can find in [27, 28].

7. References

[20] G. Kumar, H. Saini, Novel Noncommutative Cryptography Scheme Using Extra Special Group,

Security and Communication Networks ,Volume 2017, Article ID 9036382, 21 pages,

https://doi.org/10.1155/2017/9036382. [21] A. Bessalov, et al., Analysis of 2-isogeny properties of generalized form Edwards curves, in:

Proceedings of the Workshop on Cybersecurity Providing in Information and

Telecommunication Systems, July 7, 2020, vol. 2746, pp. 1–13.

[22] A. Bessalov, V. Sokolov, P. Skladannyi, Modeling of 3- and 5-isogenies of supersingular

Edwards curves, in: Proceedings of the 2nd International Workshop on Modern Machine

Learning Technologies and Data Science, June 2–3, 2020, no. I, vol. 2631, pp. 30–39.

[23] A. Bessalov, et al., Computing of odd degree isogenies on supersingular twisted edwards curves, in: Proceedings of the Workshop on Cybersecurity Providing in Information and

Telecommunication Systems, January 28, 2021 vol. 2923, 1–11.

[24] V. Roman'kov, An improved version of the AAG cryptographic protocol, Groups, Complex.,

Cryptol, 11, No. 1 (2019), 35-42. [25] A. Ben-Zvi, A. Kalka, B. Tsaban, Cryptanalysis via algebraic span, in: Shacham H. and

Boldyreva A. (eds.) Advances in Cryptology, CRYPTO 2018. 38th Annual International

Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part I, Vol.

10991, 255{274, Springer, Cham (2018). [26] B. Tsaban, Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography, J. Cryptol., 28, no. 3, 601-622, 2015. [27] S. Contiu, et al., IBBE-SGX: cryptographic group access control using trusted execution environments. In 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2018, Luxembourg City, Luxembourg, June 25-28, 2018, 207–218, 2018.2222 [28] J. Kim, S. Nepal, A Cryptographically Enforced Access Control with a Flexible User Revocation on Untrusted Cloud Storage Data Science and Engineering, vol. 1, 149–160 (2016)

References

[1] Max Noether , Luigi Cremona, Mathematische Annalen 59 , 1904 , 1 - 19 .

[2] V. Ustimenko , On new symbolic key exchange protocols and cryptosystems based on hidden tame homomorphism , Dopovidi NAS of Ukraine , no 10 , 26 - 36 , 2018 .

[3] V. Ustimenko , M. Klisowski , On Noncommutative Cryptography with cubical multivariate maps of predictable density , in: Intelligent Computing, Proceedings of the 2019 Computing Conference , Volume 2 , Part of Advances in Intelligent Systems and Computing (AISC , volume 998 ), pp. 654 - 674 .

[4] V. Ustimenko , M. Klisowski , On Noncommutative Cryptography and homomorphism of stable cubical multivariate transformation groups of infinite dimensional affine spaces , Cryptology ePrint Archive , 593 , 2019 .

[5] V. Ustimenko , On the usage of postquantum protocols defined in terms of transformation semigroups and their homomophisms , Theoretical and Applied Cybersecurity, National Technical University of Ukraine "Igor Sikorsky Kiev Polytechnic Institute" , vol. 1 , no. 2 , 32 - 44 , 2020 .

[6] V. Ustimenko , On new multivariate cryptosystems based on hidden Eulerian equations , Reports of Nath. Acad of Sci, Ukraine , 5 , 17 - 24 , 2017 .

[7] V. Ustimenko , On new multivariate cryptosystems based on hidden Eulerian equations over finite fields , ePrint Archive , 093 , 2017 .

[8] V. Ustimenko , On semigroups of multiplicative Cremona transformations and new solutions of Post Quantum Cryptography , IACR Cryptol, ePrint Arch , 133 , 2019 .

[9] V. Ustimenko , O. Pustovit , New Cryptosystems of Noncommutative Cryptography based on Eulerian Semigroups of Multivariate Transformations , CPITS 2021 , 18 - 26 .

[10] D. N. Moldovyan , N. A. Moldovyan , A New Hard Problem over Non-commutative Finite Groups for Cryptographic Protocols , International Conference on Mathematical Methods , Models, and Architectures for Computer Network Security, MMM-ACNS 2010 : Computer Network Security pp 183 - 194 .

[11] L. Sakalauskas , P. Tvarijonas , A. Raulynaitis , Key Agreement Protocol (KAP) Using Conjugacy and Discrete Logarithm Problem in Group Representation Level , INFORMATICA , 2007 , vol. 18 , No 1, 115 - 124 .

[12] V. Shpilrain , A. Ushakov , The conjugacy search problem in public key cryptography: unnecessary and insufficient , Applicable Algebra in Engineering, Communication and Computing , August 2006 , vol. 17 , iss . 3- 4 , 285 - 289 .

[13] Delaram Kahrobaei , Bilal Khan , A non-commutative generalization of ElGamal key exchange using polycyclic groups , In IEEE GLOBECOM 2006 - 2006 Global Telecommunications Conference [ 4150920 ] https://doi.org/10.1109/GLOCOM. 2006 .lications

[14] A. Myasnikov , V. Shpilrain , A. Ushakov , Group-based Cryptography . Berlin: Birkhäuser Verlag, 2008 .

[15] A. G. Myasnikov; Vladimir Shpilrain and Alexander Ush akov ( 2011 ), Noncommutative Cryptography and Complexity of Group-theoretic Problems , American Mathematical Society

[16] Zhenfu Cao ( 2012 ). New Directions of Modern Cryptography . Boca Raton: CRC Press, Taylor & Francis Group. ISBN 978-1-4665-0140-9.

[17] G. Maze , C. Monico , J. Rosenthal , Public key cryptography based on semigroup actions . Adv. Math. Commun . 1 ( 4 ), 489 - 507 , 2007 .

[18] P. H. Kropholler , et al., Properties of certain semigroups and their potential as platforms for cryptosystems , Semigroup Forum , 81 : 172 - 186 , 2010 .

[19] J. A. Lopez Ramos , et al., Group key management based on semigroup actions , Journal of Algebra and its applications , vol. 16 ( 08 ): 1750148 , 2017 .