On Eulerian Transformations and Postquantum Access Control
Protocol-Based Algorithms
Vasyl Ustimenko1,2 and Oleksandr Pustovit2
1
    University of Marie Curie-Sklodowska in Lublin, 5 Plac Marii Curie-Skłodowskiej, Lublin, 20-031, Poland
2
    Institute of Telecommunications and the Global Information Space, 13 Chokolivsky bul., Kyiv, 02000, Ukraine

                 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.

                 Keywords 1
                 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 , x 2 ,..., x n ] 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  f i ( x1 , x 2 ,..., x n ), 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
with the MPC property. We assume that there is homomorphism  n,m : S n  S m .


CPITS-II-2021: Cybersecurity Providing in Information and Telecommunication Systems, October 26, 2021, Kyiv, Ukraine
EMAIL: vasulustimenko@yahoo.pl (V. Ustimenko); sanyk_set@ukr.net (O. Pustovit)
ORCID: 0000-0002-2138-2357 (V. Ustimenko); 0000-0002-3232-1787 (O. Pustovit)
              ©️ 2022 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)



                                                                                251
    At the entrance of protocol we have elements g1 , g 2 ,..., g k , k  2 from CSn(K) conjugated with
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)


                                                      252
   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 x1  a(m,1) a(m,2)
                        x2      …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)+rq1rq2x2a(1,2,r)+rq1rqmxma(1,m,r)
       g2(r)=rq2rq1x1a(1,1,r)+rq2rq2x2a(1,2,r)+rq2rqmxma(1,m,r)
                                      …
                r   r     a(m,1,r)
        gm,(r)= qm q1x1              +rqmrq2x2a(m,2,r)+rq1rqmxma(m,m,r)



                                                             253
   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
[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.



                                                 255
[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)




                                                256