Лінійні коди клітин Шуберта та імплементації нових квадратичних публічних ключів криптографії від багатьох змінних
Multivariate Cryptography and Code Base Cryptography together with three other directions form the list of core areas of Poat Quantum Cryptography. Secure quadratic multivariate cryptosystem from are able to establish the shortest digital signatures. An idea of multivariate cryptography algorithms w...
Збережено в:
| Дата: | 2023 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Теми: | |
| Онлайн доступ: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/270 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
| Завантажити файл: |  |
Репозитарії
Physico-mathematical modeling and informational technologies| _version_ | 1867479637645328384 |
|---|---|
| author | Ustimenko, Vasyl Pustovit, Oleksandr |
| author_facet | Ustimenko, Vasyl Pustovit, Oleksandr |
| author_institution_txt_mv | [
{
"author": "Vasyl Ustimenko",
"institution": "Professor, Doctor of Physical and Mathematical Sciences, University of Royal Holloway (London), Egham Hill, Egham TW20 0EX, United Kingdom and Institute of Telecommunications and Global Information Space of the National Academy of Sciences of Ukraine, Chokolivsky Boulevard 13, 03186, Kyiv"
},
{
"author": "Oleksandr Pustovit",
"institution": "Candidate of Technical Sciences, Institute of Telecommunications and Global Information Space of the National Academy of Sciences of Ukraine, Chokolivsky Boulevard 13, 03186, Kyiv"
}
] |
| author_sort | Ustimenko, Vasyl |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:32:19Z |
| description | Multivariate Cryptography and Code Base Cryptography together with three other directions form the list of core areas of Poat Quantum Cryptography. Secure quadratic multivariate cryptosystem from are able to establish the shortest digital signatures. An idea of multivariate cryptography algorithms with quadratic transformation induced by walks on Cellular Schubert Graphs was proposed recently. These graphs are defined via restriction of the incidence relations of finite projective geometry on two distinct Schubert cells. The method defines nonlinear transformation of the vector space of vertexes of one of this cells. In this paper the implementations of these multivariate cryptosystems are considered in the case of large finite fields of characteristic 2. Quadratic map of large order is combined with two affine transformations. The lower bound of polynomial degree of the inverse map and complexity estimates for private key decryption are introduced. |
| first_indexed | 2026-06-09T01:09:26Z |
| format | Article |
| fulltext |
27
doi.org/10.15407/fmmit2023.36.027
Linear codes of Schubert cells and implementations of new
quadratic public keys of Multivariate Cryptography
Vasyl Ustimenko1, Oleksandr Pustovit2
1 Professor, Doctor of Physical and Mathematical Sciences, University of Royal Holloway (London), Egham Hill,
Egham TW20 0EX, United Kingdom and Institute of Telecommunications and Global Information Space of the
National Academy of Sciences of Ukraine, Chokolivsky Boulevard 13, 03186, Kyiv, e-mail: vasylustimenko@yahoo.pl
2 Candidate of Technical Sciences, Institute of Telecommunications and Global Information Space of the National
Academy of Sciences of Ukraine, Chokolivsky Boulevard 13, 03186, Kyiv, e-mail: sanyk_set@ukr.net
Multivariate Cryptography and Code Base Cryptography together with three other directions form
the list of core areas of Poat Quantum Cryptography. Secure quadratic multivariate cryptosystem
from are able to establish the shortest digital signatures. An idea of multivariate cryptography
algorithms with quadratic transformation induced by walks on Cellular Schubert Graphs was
proposed recently. These graphs are defined via restriction of the incidence relations of finite
projective geometry on two distinct Schubert cells. The method defines nonlinear transformation
of the vector space of vertexes of one of this cells. In this paper the implementations of these
multivariate cryptosystems are considered in the case of large finite fields of characteristic 2.
Quadratic map of large order is combined with two affine transformations. The lower bound of
polynomial degree of the inverse map and complexity estimates for private key decryption are
introduced.
Keywords: Multivariate Cryptography, Code Base Cryptography, Projective
Geometries, Largest Schubert Cells, Symbolic Computations
Introduction. It is well known that Coding based Cryptography, Multivariate
Cryptography and Lattice based Cryptography are among five core areas of Post-
Quantum Cryptography. Each of these areas is based on the complexity of certain NP
hard problem. Noteworthy that fundamental assumption of cryptography that there are
no polynomial-time algorithms for solving any NP-hard problem remains valid. So all
five directions are well justified theoretically. The tender of US National Institute of
Standardisation Technology (NIST, 2017) is dedicated to the standardisation process
of possible real life Post-Quantum Public keys. Already selected in July of 2022 four
cryptosystems are developed via methods of Lattice based Cryptography. This fact
motivates researchers from other four core areas of Post Quantum Cryptography to
continue design of new cryptographical primitives. Graph based multivariate public
keys with bijective encryption maps generated via special walks on incidence graph of
projective geometry were proposed in [1]. It can be count as attempt to combine
methods of Coding based and Multivariate Cryptographies.
UDC 519.1, 514.128
mailto:sanyk_set@ukr.net
Vasyl Ustimenko, Oleksandr Pustovit
Linear codes of Schubert cells and implementations of new quadratic public …
28
Classical multivariate public rule is a transformation of n-dimensional vector
space over finite field qF which move vector ),...,,( 21 nxxx to the tuple
)),...,,(),...,,...,,(),,...,,(( 21212211 nnnn xxxgxxxgxxxg , where polynomials ig are
given in their standard form, i. e. lists of monomial terms in the lexicographical order.
The degree of this transformation is the maximal value of )deg( ig . Traditionally
public rule has degree 2 or 3.
1. Projective geometries and Schubert cellular graphs
The incidence structure is the set V with partition sets P (points) and L (lines) and
symmetric binary relation I (graph) such that the incidence of two elements implies
that one of them is a point and another one is a line.
Projective geometry )(1
q
n FPG of dimension n-1 over the finite field qF ,
where q is a prime power, is a totality of proper subspaces of the vector space
n
qFV )( of nonzero dimension. This is the incidence system with type function
t(W)=dim(W), )(1
q
n FPGW and incidence relation I defined by the condition
21IWW if and only if one of these subspaces is embedded in another one.
We can select standard base neee ,...,, 21 of V and identify )(1
q
n FPG with the
totality of linear codes in n
qF )( . The geometry )()( 1
q
nn FPGqG is a partition of
subsets )(qGi
n consisting of elements of selected type i, i=1, 2,…, n-1. Let U stands
for the unipotent subgroup of automorphism group )( qn FPGL consisting of lower
unitriangular matrices.
Let us consider largest orbits )(qLSm of the natural action of U on )(qGm
n They
are known as largest Schubert cells. We consider the bipartite graph )(,
qn
km FCS of
the restriction of I onto disjoint union )( q
m FLS and )( q
k FLS . It is bipartite graph
with bidegrees rq and sq . We refer to )(,
qn
km FCS as Cellular Schubert graph.
In particular case n=2m+1, k=m these graphs are known as Double Schubert
graphs (see [2] or [1] and further references). Fact that unipotent subgroup U can be
defined in the case of affine spaces nK allows to define cellular Schubert graphs
)(, KCSn
km
over commutative ring K (see [2] or [1] and further references).
2. Linguistic graphs and symbolic computations
Let K be a commutative ring. We refer to an incidence structure with a point set
ms
ms KPP , and a line set mr
mr KLL , as linguistic incidence structure
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 27-31
29
)(KIm of type (s, r, m) if point ),...,,,,...,,( 2121 mssss xxxxxxx is incident to
line ],...,,,,...,,[ 2121 mrrrr yyyyyyy if and only if the following relations hold
),,...,,,...,,,,...,,,...,,(
...),,,...,,,,,...,,(
),,...,,,...,,(
121121
12112122222
212111111
mrrrmsssmmrmmsm
rrssrs
rsrs
yyyyyxxxxxfybxa
yyyyxxxxfybxa
yyyxxxfybxa
where ja and jb , j=1,2, …,m are not zero divisors, and jf are multivariate
polynomials with coefficients from K.
The colour ῤ(x)=ῤ((x)) (ῤ(y)=ῤ([y])) of point (x) (line [y]) is defined as
projection of an element (x) (respectively [y]) from a free module on its initial s
(relatively r) coordinates. As it follows from the definition of linguistic incidence
structure for each vertex of incidence graph there exists the unique neighbour of a
chosen colour.
For each rKb and ),...,,( 21 mspppp there is the unique neighbour of the
point )(][ pNl b with the colour b. Similarly for each sKc and line
],...,,[ 21 mrllll there is the unique neighbour of the line ])([)( lNp c with the
colour c.On the sets P and L of points and lines of linguistic graph we define jump
operators ),...,,,,...,,()( 2121 mssssb pppbbbpJJ , where s
s Kbbb ),...,,( 21
and ],...,,,,...,,[])([ 2121 mrrrrb lllbbblJJ , where r
r Kbbb ),...,,( 21 for the
point ),...,,( 21 msppp and the line ],...,,[ 21 mrlll .
Noteworthy, that the path in kvvv ,...,, 10 the linguistic graph mI is determined
by starting vertex 0v and colours of vertexes kvvv ,...,, 21 . We can take commutative
ring ],...,,[ 21 lyyyKR and consider graph )(KIm together with infinite graph
]),...,,[()( 21 lmm yyyKIRI defined by the same polynomials mifi ,...,2,1, with
coefficients from K but with partition sets msR and mrR .
Assume that l=m+s. We can consider the path in )(RIm of length 2k in with
starting point ),...,,,,...,,( 2121 mssss yyyyyy and consecutive colours
kk HGHGHG ,,...,,,, 2211
such that
s
si xxxKG ],...,[ 21 and
r
si xxxKH ],...,,[ 21 .
The last vertex of this path will be a point (p) with consecutive coordinates
mssss fffhhh ,...,,,,, 2121 where msfff ,...,, 21 are elements of
s
mssss xxxxxxK ],...,,,,...,,[ 2121 .
Finally we consider )(pJu H where ),...,,( 21 sgggH is the element of
s
sxxxK ],...,,[ 21 . We define passage transformation
),,...,,,,...,,( 2121 HHHHGGGPas kk of srK
Vasyl Ustimenko, Oleksandr Pustovit
Linear codes of Schubert cells and implementations of new quadratic public …
30
(space of points) with symbolic colours kk HGHG ,,...,, 21 and H via multivariate rule
.),...,,(
),...,,...,,(),,...,,(
),,...,,(),...,,...,,(),,...,,(
21
21222111
2121222111
msmsms
msssmsss
sssss
yyyfy
yyyfyyyyfy
yyygyyyygyyyygy
It is easy to see that this transformation is bijective if the map ),...,,( 21 sii yyyhy ,
i=1, 2, … , s is bijective on sK .
We define degree of tuple d
ld xxxKggg ],...,,[),...,,( 2121 as maximal degree
of polynomials ig , i=1, 2, …, d. The following two statements are proven in [2].
Theorem 1. Let K be a commutative ring. Cellular Schubert graph )(, KСSm
km
is a linguistic graph of degree 2 of type (s, r, p). Then transformations
1),,,...,,,,...,,( 2121 jHHHHGGGPas jj of the affine space psK such that
jiGH ii ...,,2,1,1)deg(,1)deg( and H are quadratic multivariate tuples is a
quadratic map on psK .
Conclusions. We are working on the algorithms for the generation of standard form of
the map of kind TTG21 where ),,...,,,,...,,( 2121 HHHHGGGPasG jj is a map of
Theorem 1, T1 is bijective affine transformation of spdFV d
q ,)( (element of
)( qd FAGL ) and T2 is injective linear map from V to vector space U of dimension l,
l≥d. This standard form liyyyfy dii ,...,2,1),,...,,( 21 can be used as encryption
tool or instrument for digital signatures.
We implement the generation in the case
322, qFK q . Let us assume that
m, k, n, s, r, p, j are parameters of Theorem 1 and 2 and d=s+p. For the generation of
transformation G as above we select iH and jiGi ,...,2,1, of degree 1 with
pseudorandom coefficients and take
))(,...,)(,)(,,...,,( 22
2
2
121 stststs yyylllH ,
where t, 1 <t<s is the constant, ),...,,( 21 tsi yyyl are linear forms and rule
),...,,( 21 tsii yyyly is bijective transformation D of V of order 1tsq , i. e. D is
a Singer cycle. Accordingly [1] this choice insures that polynomial degree of 1G is at
least 312 and its order is multiple of 1tsq .We assume that l=O(d) and m-k is a
constant and m=an for 0<a<1. Under this condition public user can encrypt in time
)( 3dO and key owner can use his/her knowledge on ii GH , and H and decrypt in
time )( 2dO .
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 27-31
31
Acknowledgements. This research is partially supported by British Academy
Fellowship for Researchers under Risk 2022.
References
[1] Vasyl Ustimenko, Linear codes of Schubert type and quadratic public keys of Multivariate
Cryptography, IACR e-print archive, 2023/175.
[2] V. Ustimenko, Graphs in terms of Algebraic Geometry, symbolic computations and secure
communications in Post-Quantum world, UMCS Editorial House, Lublin, 2022, 198 p.
Лінійні коди клітин Шуберта та імплементації нових
квадратичних публічних ключів криптографії від багатьох
змінних
Василь Устименко, Олександр Пустовіт
Криптографія від багатьох змінних та Криптографія, що базується на кодах разом з
трьома іншими напрямками, становлять список основних галузей Постквантової
Криптографії. Безпечні квадратичні криптосистеми від багатьох змінних здатні
реалізувати найкоротші цифрові підписи. Нещодавно була запропонована ідея алгоритмів
криптографії від багатьох змінних з квадратичними перетвореннями, що індуковані
блуканнями у клітинах графа Шуберта. Ці графи визначаються через обмеження
відношення інидентності скінченної проективної геометрії на дві різні найбільші клітини
Шуберта. Метод визначає нелінійне пертворення на векторному просторі вершин однієї з
клітин. У цій статті ми розглядаємо імплементацію цієї схеми для декількох сімейств
графів, визначених над великими скінченними полями характеристики два. Квадратичне
відображення великого порядку комбінується з двома афінними перетвореннями.
Наводиться оцінка поліноміальної степені оберненого відображення та оцінка швидкодії
приватного ключа.
Received 06.03.23
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-270 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:09:26Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/4c/82b3801c90d60c8c250ab77bf268ac4c.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-2702025-02-21T17:32:19Z Linear codes of Schubert cells and implementations of new quadratic public keys of Multivariate Cryptography Лінійні коди клітин Шуберта та імплементації нових квадратичних публічних ключів криптографії від багатьох змінних Ustimenko, Vasyl Pustovit, Oleksandr Multivariate Cryptography, Code Base Cryptography, Projective Geometries, Largest Schubert Cells, Symbolic Computations Multivariate Cryptography and Code Base Cryptography together with three other directions form the list of core areas of Poat Quantum Cryptography. Secure quadratic multivariate cryptosystem from are able to establish the shortest digital signatures. An idea of multivariate cryptography algorithms with quadratic transformation induced by walks on Cellular Schubert Graphs was proposed recently. These graphs are defined via restriction of the incidence relations of finite projective geometry on two distinct Schubert cells. The method defines nonlinear transformation of the vector space of vertexes of one of this cells. In this paper the implementations of these multivariate cryptosystems are considered in the case of large finite fields of characteristic 2. Quadratic map of large order is combined with two affine transformations. The lower bound of polynomial degree of the inverse map and complexity estimates for private key decryption are introduced. Криптографія від багатьох змінних та Криптографія, що базується на кодах разом з трьома іншими напрямками, становлять список основних галузей Постквантової Криптографії. Безпечні квадратичні криптосистеми від багатьох змінних здатні реалізувати найкоротші цифрові підписи. Нещодавно була запропонована ідея алгоритмів криптографії від багатьох змінних з квадратичними перетвореннями, що індуковані блуканнями у клітинах графа Шуберта. Ці графи визначаються через обмеження відношення інидентності скінченної проективної геометрії на дві різні найбільші клітини Шуберта. Метод визначає нелінійне пертворення на векторному просторі вершин однієї з клітин. У цій статті ми розглядаємо імплементацію цієї схеми для декількох сімейств графів, визначених над великими скінченними полями характеристики два. Квадратичне відображення великого порядку комбінується з двома афінними перетвореннями. Наводиться оцінка поліноміальної степені оберненого відображення та оцінка швидкодії приватного ключа. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-13 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/270 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 27-31 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 27-31 2617-5258 1816-1545 10.15407/fmmit2023.36 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/270/259 Авторське право (c) 2023 Vasyl Ustimenko, Oleksandr Pustovit (Автор) |
| spellingShingle | Multivariate Cryptography Code Base Cryptography Projective Geometries Largest Schubert Cells Symbolic Computations Ustimenko, Vasyl Pustovit, Oleksandr Лінійні коди клітин Шуберта та імплементації нових квадратичних публічних ключів криптографії від багатьох змінних |
| title | Лінійні коди клітин Шуберта та імплементації нових квадратичних публічних ключів криптографії від багатьох змінних |
| title_alt | Linear codes of Schubert cells and implementations of new quadratic public keys of Multivariate Cryptography |
| title_full | Лінійні коди клітин Шуберта та імплементації нових квадратичних публічних ключів криптографії від багатьох змінних |
| title_fullStr | Лінійні коди клітин Шуберта та імплементації нових квадратичних публічних ключів криптографії від багатьох змінних |
| title_full_unstemmed | Лінійні коди клітин Шуберта та імплементації нових квадратичних публічних ключів криптографії від багатьох змінних |
| title_short | Лінійні коди клітин Шуберта та імплементації нових квадратичних публічних ключів криптографії від багатьох змінних |
| title_sort | лінійні коди клітин шуберта та імплементації нових квадратичних публічних ключів криптографії від багатьох змінних |
| topic | Multivariate Cryptography Code Base Cryptography Projective Geometries Largest Schubert Cells Symbolic Computations |
| topic_facet | Multivariate Cryptography Code Base Cryptography Projective Geometries Largest Schubert Cells Symbolic Computations |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/270 |
| work_keys_str_mv | AT ustimenkovasyl linearcodesofschubertcellsandimplementationsofnewquadraticpublickeysofmultivariatecryptography AT pustovitoleksandr linearcodesofschubertcellsandimplementationsofnewquadraticpublickeysofmultivariatecryptography AT ustimenkovasyl líníjníkodiklítinšubertataímplementacíínovihkvadratičnihpublíčnihklûčívkriptografíívídbagatʹohzmínnih AT pustovitoleksandr líníjníkodiklítinšubertataímplementacíínovihkvadratičnihpublíčnihklûčívkriptografíívídbagatʹohzmínnih |