=Paper=
{{Paper
|id=Vol-3288/short14
|storemode=property
|title=On Multivariate Maps of High Degree for the Post Quantum Protection of Virtual Organizations (short paper)
|pdfUrl=https://ceur-ws.org/Vol-3288/short14.pdf
|volume=Vol-3288
|authors=Vasyl Ustimenko,Tymoteusz Chojecki
|dblpUrl=https://dblp.org/rec/conf/cpits/UstimenkoC22
}}
==On Multivariate Maps of High Degree for the Post Quantum Protection of Virtual Organizations (short paper)==
https://ceur-ws.org/Vol-3288/short14.pdf
On Multivariate Maps of High Degree for the Post Quantum
Protection of Virtual Organizations
Vasyl Ustimenko1,2,3 and Tymoteusz Chojecki1
1
University of Marie Curie-Sklodowska in Lublin, 5 Plac Marii Curie-Skłodowskiej str., Lublin, 20-031, Poland
2
Institute of Telecommunications and the Global Information Space of the National Academy of Sciences of
Ukraine, 13 Chokolivsky boul., Kyiv, 02000, Ukraine
3
Royal Holloway University of London, Egham Hill, Egham TW20 0EX, UK
Abstract
The intersection of Commutative and Multivariate cryptography contains studies of
cryptographic applications of subsemigroups and subgroups of affine Cremona semigroups
defined over finite commutative ring K with the unit. We consider two special families of
subsemigroups in a semigroup of all endomorphisms of K[x1, x2, …, xn]. They can be used
in Post Quantum Cryptography for the development of key exchange protocols of
Noncommutative Cryptography with output presented as multivariale map of high degree
and density. The security of these schemes is based on a complexity of Conjugacy Power
Problem. Suggested schemes can be converted in protocol based cryptosystems of El
Gamal type and used for post quantum protection of Virtual Organisations in Global
Information Space. Algorithms are implemented in the cases of finite fields of
characteristic 2 and arithmetic rings Zm, m=2n, n=8,16,32.
Keywords 1
Multivariate transformations, virtual organization, knowledge base, noncommutative
cryptography, multivariate cryptography, graph based cryptography.
1. Introduction 2. Post Quantum, Multivariate and
Noncommutative Cryptography
NIST 2017 tender starts the standardisation
process of possible Post-Quantum Public keys and Virtual Organizations
aimed for purposes to be:
Encryption tools. Noteworthy that all multivariate NIST
Tools for digital signatures [1]. candidates were presented by multivariate rule of
In July 2020 the Third round of the degree bounded by constant (2 or 3) of kind
competition was started. In the category of x1→f1(x1, x2, …, xn), x2→f2(x1, x2, …, xn), …,
Multivariate Cryptography (MC) remaining xn→fn(x1, x2, …, xn).
candidates are easy to observe [2]. In fact RUOV is given by quadratic system of
For the first task multivariate algorithm were polynomial equations. During Third Round of
not selected, single multivariate candidate is NIST project [5] some crypto analytical
Rainbow Like Unbalanced Oil and Vinegar instruments for breaking ROUV were found. So,
(RUOV) In fact RUOV algorithm is investigated all multivariate algorithms-candidates were
as appropriate instrument for the second task rejected during the project and first four winners
[3, 4]. were announced in July, 2022. All of them are
within the area of Lattice based Cryptography.
We think that these NIST outcomes motivate
investigations of alternating options in
CPITS-2022: Cybersecurity Providing in Information and Telecommunication Systems, October 13, 2022, Kyiv, Ukraine
EMAIL: vasulustimenko@yahoo.pl (V. Ustimenko); tymoteusz.chojecki@umcs.pl (T. Chojecki)
ORCID: 0000-0002-2138-2357 (V. Ustimenko); 0000-0002-3294-2794 (T. Chojecki)
©️ 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)
156
Multivariate Cryptography oriented on encryption rows Mi = (mi,1, mi,2, …, mi,n), i ϵ J for some
tools and conducting digital signatures. “potentially infinite” set J.
(a) To work with plainspace Fqn and its So, Alice and Bob can periodically compute
transformation G of linear degree cn, c > 0 on the G(Mi) and use this tuple as entrance password.
level of stream ciphers or public keys. Additionally they can use G for symmetric
(b) To use protocols of Noncommutative communication via one time pad.
Cryptography with platforms of multivariate Alice writes her plaintext P=(p1, p2, …, pn)
transformations for the secure elaboration of from Fqn. She computes P + G(Mi) and sends it to
multivariate map G from End(Fq[x1, x2, …, xn]) of Bob. He knows Mi as well. So, Bob restores the
linear or superlinear degree and density bounded plaintext.
below by function of kind cnr, where c>0 and r>1. Surely instead of one time pad correspondents
Recall that density is the number of all can use other stream cipher with periodical
monomial term in standard form xi → gi(x1, x2, …, change of password.
xn), i = 1,2,…,n of G, where polynomials g1 are It is naturally to consider more general case of
given via the lists of monomial terms in the arbitrarily commutative ring K instead of finite
lexicographical order. field Fq. We will use Algebraic Graphs to generate
Solution of task (b) can be used for the control highly nonlinear automorphisms of K[x1, x2, …,
access to the portal B of virtual organisation xn] over commutative ring.
(knowledge base, virtual decision making centre, For creation of Mi, i ϵ J ontological
etc.) via secure communications of portal technologies can be used. We use files obtained
administrator (Alice) and public user (Bob). by ontological instruments presenting for example
Assume that the information in B is presented key words of texts with the relations between
in binary alphabet. So we can identify characters them in the form of graph (trees or other
of this alphabet with elements of finite field Fq, diagrams). One can combine ontological
q=256. Portal has a search engine. So, we can extraction with hashing technologies to make
assume that the size of the information through the digests of documents of appropriate size.
portal is practically unlimited. We hope that this new application of
Assume that some secure tools are used to technologies for special ontological extractions
protect the entrance of B. To enter the system user will motivate further research in this important
need a password which is a tuple E of length n direction.
written in alphabet Fq. It has to be changed The task is new because of postquantum
regularly with the usage of certain period ∆. protocols with outputs in the form of highly
We suggest the following access control nonlinear map of affine map of K n to itself appear
scheme. Alice and Bob use several session of very recently.
Postquantum Secure Protocols of We present one of them below.
Noncommutative Cryptography based on a
subsemigroup S of End Fq [x1, x2, …, xn] to 3. Multivariate Platforms of
elaborate multivariate map G from S of kind
xi→fi(x1, x2, …, xn), i = 1,2,…,n of degree bounded Noncommutative Cryptography
below by cn, c>0 and density bounded below by and Their Applications
dnr where c, d are positive constants and r > 2.
The standard form of G can be unknown. This Regular algebraic graph A(n, q) =A(n, Fq) is an
map could be non bijective one. It has to be given important object of Extremal Graph Theory. In
with a polynomial algorithm of computation the fact we can consider more general graphs A(n, K)
value of G in given tuple P = (p1, p2, …, pn). defined over arbitrary commutative ring K.
Alice use some pseudorandom generator of This graph is a bipartite graph with the point
tuples for the creation of P = (p1, p2, …, pn) and set P=Kn and line set L=Kn (two copies of a
sends it to Bob via open channel. She enters Cartesian power of K are used). It is convenient to
password E = G(p1, p2, …, pn) to secure the use brackets and parenthesis to distinguish tuples
portal. from P and L.
Bob also computes the tuple E and enters the So, (p) = (p1, p2, …, pn) ϵ Pn and [l] = [l1, l2, …,
system. We can assume that data storage B ln] ϵ Ln. The incidence relation I = A(n,K) (or
contains a pseudorandom (or genuinely random, corresponding bipartite graph I) can be given by
obtained via quantum computations) matrix of
157
condition p I l if and only if the equations of the P=K n defined bythe rule x1 → x1 + ak, x2→f1(x1,
following kind hold: x2), x3 → f2(x1, x2, x3), …, xn→ fn-1(x1 x2, …,
p2 – l2 = l1p1 xn).This transformation is bijective map of Kn to
p3 – l3 = p1l2, itself. It is an element of affine Cremona group
p4 – l4 = l1p3, CG(Kn) of elements from Aut(K[x1, x2, …, xn])
p5 – l5 = p1l4, … , acting naturally on Kn. The inverse for this map is
pn – ln = p1ln-1 n
ή(w)-1 which coincides with nή(w’) for w’
for odd n and pn – ln = l1pn–1 for even n. =Rev(w)=(-at ,b1-at, a2-at, b2-at, …, bt-at).We refer
They were intensively used for the to Rev(w) as reverse string for w from BP(K).
constructions of LDPC codes for satellite Proposition 2.1.1 [6]. The map nή from BP(K)
communications and cryptographic algorithms. to CG(Kn) is a homomorphism of the semigroup
In the case of K=Fq, q > 2 of odd characteristic into group.
graphs A(n, Fq), n > 1 form a family of small We refer to nή as compression map and denote
world graphs because their diameter is bounded n
ή(BP(K)) as GA(n, K). Degree of element g of
by linear function in variable n. We can consider Cremona group CG(Kn) of kind xi→gi(x1, x2, …,
an infinite bipartite graph A(K) with points (p1, p2, xn) is the maximal degree of polynomials gi.
…, pn, …) and lines [l1, l2, …,ln, …]. If K, |K| > 2 Theorem 2.1.1 [7]. The maximal degree of
is an integrity then A(K) is a tree and A(n, K), multivariate element g from GA(n, K) equals 3.
n=2,3,… is its algebraic approximation of large It means that subgroup G of kind TGA(n,K)T–1
girth. where T is an element of AGLn(K) can be used
We refer to the first coordinates p1=ῤ((p)) and efficiently as a platform for the implementation of
l1=ῤ([l]) as colors of vertices of A(K) (or A(n, K)). protocols of Noncommutative Cryptography.
It is easy to check that each vertex v of the graph
has a unique neighbor Na(v) of selected colour a. 3.2. Semigroup Family
So the walk of length 2k from vertex (0,0,…) will
be given by the sequence w of colours of its
Let K be a finite commutative ring with the
elements b1, a1, b2, a2, …, bk, ak.
unit such that multiplicative group K* of regular
It will be the walk without repetition of edges
if 0 ≠ a1, ai ≠ ai+1 and bi ≠ bi+1 for i=1, 2,…, k-1. elements of the ring contains at least 2 elements.
So we can identify walks from 0 point of even We take Cartesian power nE(K) = (K*)n and
length point with sequence of kind w. Let w’=(b’1, consider an Eulerian semigroup nES(K) of
a’1, b’2, a’2, …, b’s, a’s).We define the transformations of kind
composition u of w and w’ as the sequence u=(b1, x1 → ϻ1x1 a(1,1)x2 a(1,2) … xm a(1,n),
a1, b2, a2, …,bk, ak, b’1 + ak, ak + a’1, b’2 + ak, …, x2 → ϻ2x1a(2,1)x2 a(2,2) … xn a(2,n), (1)
b’s + ak, a’s + ak). If w and w’ are paths and …
b’1 + ak ≠ bk then u is also a path. xn → ϻnx1 a(n,1) x2 a(n,2) … xn a(n,n),
Let BP(K) be a semigroup of all walks with this where a(i,j) are elements of arithmetic ring Zd,
operation. One can identify empty string with the d=|K*|, ϻiϵK*.
unity of BP(K).We use term branching semigroup
for BP(K). 3.3. Two Platforms in a Tandem
3.1. Group Family Let nEG(K) stand for Eulerian group of
invertible transformations from nES(K). It is easy
Let us take graph A(n, K) together with A(n, to see that the group of monomial linear
K[x1, x2, …, xn]). For each element w from BP(K) transformations Mn is a subgroup of nEG(K). So
we consider a walk ∆(w) in A(n, K[x1, x2, …, xn]) semigroup nES(K) is a highly noncommutative
with starting point (x1, x2, …, xn) where xi are algebraic system. Each element from nES(K) can
generic elements of K[x1, x2, …, xn] and special be considered as transformation of a free module
colors of vertices x1 + b1, x1 + a1, …, x1 + bk, Kn.
x1 + ak. Let p’=dest(∆(w)) be a destination, i. e. a 1. Twisted Diffie-Hellman protocol.
final point of this walk. The destination has Let S be an abstract semigroup which has
coordinates (x1 + ak, f1(x1, x2), f2(x1, x2, x3), …, fn- some invertible elements.
Alice and Bob share element g ϵ S and pair of
1(x1, x2, …, xn) where f1 are elements of K[x1, x2,
…, xn]. We consider the transformation nή(w) of invertible elements h, h–1 from this semigroup.
158
Alice takes positive integer t = kA and d = rA Alice enters the access password P and sends
and forms h-dghd = gA. Bob takes s = kB and p = rB. HX(P) it to Bob. He restores the P and enters B.
and forms h-pgshp = gB. They exchange gA and gB Alternatively Bob enters the access password
and compute collision element X as Ag = h-dgBthd P andsends H–1X–1(P) to Alice. She restores P and
and Bg = h-pgAs hp respectively. puts as entrance rule to the system.
2. Inverse twisted Diffie-Hellman protocol.
Let S be a group. Table 1
Correspondents follow the scheme 1 with the Density of the map HX of linear degree induced
inverse element g ϵ nEG(K) and Alice sends by the graph 𝑨(𝒏, 𝑭𝟐𝟑𝟐 ), case I
h–dg–thd = gA to Bob and she gets h–pgshp = gB from Length of the walk d(HX)
him. They use the same formulae for Ag and Bg. n 16 32 64 128 256
But in the new version these elements are mutual 16 5623 5623 5623 5623 5623
inverses. Alice has X but Bob possesses X–1. 32 53581 62252 62252 62252 62252
64 454375 680750 781087 781087 781087
Both schemes can be implemented with the 128 3607741 6237144 9519921 10826616 10826616
multivariate platforms S=TGA(n,K)T–1 and
n
ES(K).
Algorithm 2.3.1. Correspondents executes Table 2
pairs of directed twisted DH protocols with Density of the map of linear degree induced by
platforms P1 = nES(K) and P2 = TGA(n,K)T–1. the graph 𝑨(𝒏, 𝑭𝟐𝟑𝟐 ), case II
Assume that they have outputs H and X. Length of the walk d(HX)
Each of correspondents have HX of linear n 16 32 64 128 256
16 6544 6544 6544 6544 6544
degree Θ(n) and density Θ(n4). 32 50720 50720 50720 50720 50720
They can compute standard form of G=HX, or 64 399424 399424 399424 399424 399424
use two step procedure to compute G(p) as 128 3170432 3170432 3170432 3170432 3170432
1
p = H(p) and 2p = X(1p).
Remark 2.3.1 The density of HX is the Usage of transformations of kind HX as in
number of monomial terms of this map in its algorithm 2 in the form of public key was
standard form. It is function of the length of considered in [10] and [11]. Classical approach of
reimage of X under the homomorphism ή’ sending Multivariate Cryptography are presented in [12].
u from BP(K) to Tnή(u)T–1. It depends on Ideas of fast developing Noncommutative
d(HX)=d(X)=l(ή’–1 (X)). Cryptography reader can find in [13]–[28].
Parameter d(X) depends on kA, kB, rA, rB, ή’–
1
(g), ή’-1(h) and linear transformation T of the
protocol with the platform TGA(n,k)T–1 [8, 9].
4. Conclusions
Thus, adversary does not able to estimate
d(HX). Multivariate Cryptography started from
Results of computer simulation demonstrate studies of bijective transformations G of a vector
connection between d(HX) in the case of field Fq space (Fq)n. as possible encryption tools. One can
of characteristic 2. increase number of variables n in the equation of
Table 1 corresponds to the case of sparse kind G(x) = b and rewrite the condition of
matrix T eith 2n – 1 no zero entries. Table 2 existence of solution for this equation in the form
reflects the case of the matrix with n2 nonzero G’(y) = b’ where G’ is quadratic transformation
entries. of V = (Fq)m where m is essentially larger than n,
Algorithm 2.3.2. Correspondents executes y and b’ are vectors from V.
pairs of inverse twisted DH protocols with The complexity of initial and rewritten
platforms P1 = nES(K) and P2 = TGA(n,K)T–1. systems of equations are essentially differs.
Assume that Alice has outputs H and X, Bob has Anyway this possibility motivates studies of
H–1 and X–1 from P1 and P2 respectively. quadratic maps as tools for Public Key
Correspondents use space of plaintexts (K*)n and Cryptography.
space of ciphertexts Kn. All algorithms of Multivariate Cryptography
Alice and Bob encrypt via HX and H–1X–1 and under NIST investigation were based on quadratic
decrypt via XH and X–1 H–1. equations and were not selected as finalists. The
Remark 2.3.2. In the case of inverse first four winners of the NIST competition are
protocols. The access control does not use the described in term of Lattice based Cryptography.
extraction of information from knowledge base B.
159
We have to mention that NIST project International Conference on the Theoryand
compares implementations of some public keys as Applications of Cryptographic Techniques,
products of Software Engineering. On the level of part I, 2021.
Theoretical Computer Science all 5 classic [6] V. Ustimenko, On the Extremal Graph
direction of Post Quantum Cryptography Theory and Symbolic Computations,
inclusive Multivariate Cryptography have future Dopovidi National Academy of Sci, Ukraine,
perspectives because they are based on known no. 2, 2013, pp. 42–49.
NP-hard problems. One of such problems is about [7] V. Ustimenko, A. Wroblevska, On the key
finding solution of nonlinear system of m = m(n) exchange with nonlinear polynomial maps of
equations in n variables. stable degree, Annalles UMCS Informatica
We already mention that restriction on the case AI X1, 2, 2011, pp. 81–93.
of quadratic equations is not well motivated. [8] M. Klisowski, V. Ustimenko, On the
Outcomes of NIST project motivates for search of Comparison of Cryptographical Properties of
efficient and secure public keys based on Two Different Families of Graphs with Large
multivariate transformation of unbounded degrees Cycle Indicator, Mathematics in Computer
of affine space Kn defined over finite commutative Science, vol. 6, no. 2, 2012, pp. 181–198.
ring K. [9] V. Ustimenko, M. Klisowski, On
Noteworthy that some efficient public keys Noncommutative Cryptography with
over finite fields and arithmetical rings Zm are Cubical Multivariate Maps of Predictable
suggested in [10] and [11]. They use no bijective Density, in Computing Conference,
transformations of Kn of unbounded linear degree Londone, vol. 2, Part of Advances in
d(n). Crypto analytical instruments for breaking Intelligent Systems and Computing
these algorithms are not founded yet. Other idea (AISC), volume 998, 2019, pp. 654–674.
to use hard problems of Noncommutative [10] V. Ustimenko, On New Multivariate
Cryptography in case of platform-semigroups of Cryptosystems based on Hidden Eulerian
multivariate transformations is explored in this Equations, Dopov. Nath Acad of Sci,
paper. Ukraine, no. 5, 2017, pp 17–24.
[11] V. Ustimenko, On New Multivariate
5. References Cryptosystems based on Hidden Eulerian
Equations over Finite Fields, Cryptology
ePrint Archive, 093, 2017.
[1] Post-Quantum Cryptography: Call for [12] L. Goubin, J. Patarin, B.-Y. Yang,
Proposals, https://csrc.nist.gov/. Multivariate Cryptography, Encyclopedia of
[2] V. Grechaninov, et al., Formation of Cryptography and Security, 2nd ed., 2011,
Dependability and Cyber Protection Model
pp. 824–828.
in Information Systems of Situational
[13] D. Moldovyan, N. Moldovyan, A New Hard
Center, in Workshop on Emerging
Problem over Non-commutative Finite
Technology Trends on the Smart Industry Groups for Cryptographic Protocols,
and the Internet of Things, vol. 3149, 2022, International Conference on Mathematical
pp. 107–117. Methods, Models, and Architectures for
[3] A. Bessalov, et al., Analysis of 2-isogeny Computer Network Security, MMM-ACNS
properties of generalized form Edwards 2010, pp. 183–194.
curves, in: Proceedings of the Workshop on [14] L. Sakalauskas, P. Tvarijonas, A. Raulynai-
Cybersecurity Providing in Information and tis, Key Agreement Protocol (KAP) Using
Telecommunication Systems, July 7, 2020, Conjugacy and Discrete Logarithm
vol. 2746, pp. 1–13. Problema in Group Representation Level,
[4] A. Bessalov, et al., Implementation of the Informatica, vol. 18, no. 1, 2007, pp. 115–
CSIDH Algorithm Model on Supersingular 124.
Twisted and Quadratic Edwards Curves, in [15] V. Shpilrain, A. Ushakov, The Conjugacy
Workshop on Cybersecurity Providing in
Search Problem in Public Key Cryptography:
Information and Telecommunication Unnecessary and Insufficient, Applicable
Systems, vol. 3187, no. 1, 2022, pp. 302– Algebra in Engineering, Communication and
309. Computing, vol. 17, iss. 3–4, 2006, pp 285–
[5] A. C. François, Xavier Standaert, Eurocrypt 289.
2021, LNCS 12696, 40th Annual
160
[16] D. Kahrobaei, B. Khan, A non-commutative
generalization of ElGamal key exchange
using polycyclic groups, in IEEE
GLOBECOM Global Telecommunications
Conference [4150920], 2006. doi:
10.1109/glocom.2006.
[17] Z. Cao, New Directions of Modern
Cryptography. Boca Raton: CRC Press,
Taylor & Francis Group, 2012.
[18] B. Fine, et al., Aspects of Non abelian Group
Based Cryptography: A Survey and Open
Problems, arXiv:1103.4093.
[19] A. Myasnikov, V. Shpilrain, A. Ushakov,
Non-commutative Cryptography and
Complexity of Group-theoretic Problems.
American Mathematical Society, 2011.
[20] I. Anshel, M. Anshel, D. Goldfeld, An
Algebraic Method for Public-Key
Cryptography, Math. Res. Lett. 6(3–4), 1999,
pp. 287–291.
[21] S. R. Blackburn, S. D. Galbraith,
Cryptanalysis of Two Cryptosystems based
on Group Actions, in Advances in
Cryptology—ASIACRYPT’99. Lecture
Notes in Computer Science, vol. 1716, 1999,
pp. 52–61.
[22] P. H. Kropholler, et al., Properties of Certain
Semigroups and Their Potential as Platforms
for Cryptosystems, Semigroup Forum 81,
2010, pp. 172–186.
[23] J. A. Lopez Ramos, et al., Group Key
Management based on Semigroup Actions,
Journal of Algebra and Its Applications,
vol. 16, 2019.
[24] A. G. Myasnikov, A. Roman'kov, A Linear
Decomposition Attack, Groups Complex.
Cryptol., vol. 7, no. 1, 2015, pp. 81–94.
[25] V. A. Roman'kov, A Nonlinear Decompo-
sition Attack, Groups Complex. Cryptol.,
vol. 8, no. 2, 2016, pp. 197–207.
[26] V. Roman'kov, An improved version of the
AAG cryptographic protocol, Groups,
Complex., Cryptol, 11, No. 1 (2019), 35-42.
[27] A. Ben-Zvi, A. Kalka, B. Tsaban,
Cryptanalysis via Algebraic Span, in
Advances in Cryptology, CRYPTO, 38th
Annual International Cryptology
Conference, part I, vol. 10991, 2018,
pp. 255–274.
[28] B. Tsaban, Polynomial-time solutions of
computational problems in noncommutative-
algebraic cryptography, J. Cryptol. 28, No. 3
(2015), 601-622.
161