On multivariate public key based on a pair of transformation with density gap
We propose an algorithm of generation of the stable families of bijective polynomial maps f(n) of the n-dimensional affine space over a commutative ring K together with their inverse transformations. All maps are given in a standard basis, in which their degrees and densities are calculated. The m...
Gespeichert in:
| Veröffentlicht in: | Доповіді НАН України |
|---|---|
| Datum: | 2018 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2018
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/143534 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | On multivariate public key based on a pair of transformation with density gap / V.A. Ustimenko // Доповіді Національної академії наук України. — 2018. — № 9. — С. 21-27. — Бібліогр.: 15 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-143534 |
|---|---|
| record_format |
dspace |
| spelling |
Ustimenko, V.A. 2018-11-05T13:03:50Z 2018-11-05T13:03:50Z 2018 On multivariate public key based on a pair of transformation with density gap / V.A. Ustimenko // Доповіді Національної академії наук України. — 2018. — № 9. — С. 21-27. — Бібліогр.: 15 назв. — англ. 1025-6415 DOI: doi.org/10.15407/dopovidi2018.09.021 https://nasplib.isofts.kiev.ua/handle/123456789/143534 519.1, 514.128 We propose an algorithm of generation of the stable families of bijective polynomial maps f(n) of the n-dimensional affine space over a commutative ring K together with their inverse transformations. All maps are given in a standard basis, in which their degrees and densities are calculated. The method allows us to generate transformations f(n) of the linear density with degree given by the prescribed linear function d(n) and with exponential density for f(n)⁻¹. In the case of K = Fq, we can select f(n) of the exponential order. The scheme of generation of public keys of multivariate cryptography of the form g(n) = T₁ f(n)T₂, where T₁ is a monomial linear transformation of K^n, and the degree of T₂ is equal to 1, is proposed. The estimates of complexity show that the time of execution of the encryption rule coincides with the time of computation of the value of a quadratic multivariate map. The decryption procedure based on the knowledge of a generation algorithm is even faster. The security rests on the idea of the insufficiency of adversary’s computational resources to restore the inverse map with exponential density and unbounded degree and on the absence of the known general polynomial algorithms to solve this task. Пропонується алгоритм породження стабільних родин взаємно однозначних відображень f(n) у n-вимірному афінному просторі над комутативним кільцем K разом з оберненими до них перетвореннями. Всі відображення подані у стандартному базисі, в якому обчислюються їх степінь та щільність. Метод дозволяє генерувати перетворення f(n) лінійної щільності зі степенем, заданим обраною лінійною функцією d(n) та зі щільністю експоненціального розміру для f(n)⁻¹. У випадку K = Fq ми можемо обрати f(n) експоненціального порядку. Пропонується схема генерування публічних ключів поліномінальної криптографії від багатьох змінних вигляду g(n) = T₁ f(n)T₂, де T₁ є мономіальним лінійним перетворенням, а степінь T₂ дорівнює 1. Оцінки складності показують, що час виконання правила шифрування збігається з часом обчислення значення квадратичного поліноміального відображення. Процедура декодування, що базується на знанні алгоритму генерації, є ще більш швидкою. Безпека ґрунтується на ідеї недостатності обчислювальних ресурсів у опонента для відновлення оберненого відображення експоненціальної щільності і необмеженого степеня та відсутності відомих поліноміальних алгоритмів для розв’язання цієї задачі. Предлагается алгоритм порождения стабильных семейств взаимно однозначных отображений f(n) в n-мерном аффинном пространстве над коммутативным кольцом K вместе с обратными к ним преобразованиями. Все отображения заданы в стандартном базисе, в котором вычисляются их степени и плотности. Метод позволяет генерировать преобразование f(n) линейной плотности со степенью, заданной выбранной линейной функцией d(n) и с плотностью экспоненциального размера для f(n)⁻¹. В случае K = Fq мы можем выбрать f(n) экспоненциального порядка. Предлагается схема генерации публичных ключей полиномиальной криптографии от многих переменных вида g(n) = T₁ f(n)T₂, где T₁ является мономиальным линейным преобразованием, а степень T₂ равна единице. Оценки сложности показывают, что время выполнения правила шифрования совпадает с временем вычисления значения квадратичного полиномиального отображения. Процедура декодирования, основывающаяся на знании алгоритма генерации, является еще более быстрой. Безопасность основывается на недостатке вычислительных ресурсов у оппонента для восстановления обратного отображения экспоненциальной плотности и неограниченной степени и на отсутствии эффективных алгоритмов для решения этой задачи. This research is partially supported by the grant PIRSESGA2013612669 of the 7th Framework Programme of the European Commission. en Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика On multivariate public key based on a pair of transformation with density gap Про криптосистеми від багатьох змінних, що ґрунтуються на парі перетворень з провалом у щільності О криптосистемах от многих переменных, основанных на паре преобразований c провалом в плотности Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
On multivariate public key based on a pair of transformation with density gap |
| spellingShingle |
On multivariate public key based on a pair of transformation with density gap Ustimenko, V.A. Інформатика |
| title_short |
On multivariate public key based on a pair of transformation with density gap |
| title_full |
On multivariate public key based on a pair of transformation with density gap |
| title_fullStr |
On multivariate public key based on a pair of transformation with density gap |
| title_full_unstemmed |
On multivariate public key based on a pair of transformation with density gap |
| title_sort |
on multivariate public key based on a pair of transformation with density gap |
| author |
Ustimenko, V.A. |
| author_facet |
Ustimenko, V.A. |
| topic |
Інформатика |
| topic_facet |
Інформатика |
| publishDate |
2018 |
| language |
English |
| container_title |
Доповіді НАН України |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| format |
Article |
| title_alt |
Про криптосистеми від багатьох змінних, що ґрунтуються на парі перетворень з провалом у щільності О криптосистемах от многих переменных, основанных на паре преобразований c провалом в плотности |
| description |
We propose an algorithm of generation of the stable families of bijective polynomial maps f(n) of the n-dimensional
affine space over a commutative ring K together with their inverse transformations. All maps are given in a standard
basis, in which their degrees and densities are calculated. The method allows us to generate transformations f(n)
of the linear density with degree given by the prescribed linear function d(n) and with exponential density for
f(n)⁻¹. In the case of K = Fq, we can select f(n) of the exponential order. The scheme of generation of public keys of
multivariate cryptography of the form g(n) = T₁ f(n)T₂, where T₁ is a monomial linear transformation of K^n, and the
degree of T₂ is equal to 1, is proposed. The estimates of complexity show that the time of execution of the encryption
rule coincides with the time of computation of the value of a quadratic multivariate map. The decryption procedure
based on the knowledge of a generation algorithm is even faster. The security rests on the idea of the insufficiency of
adversary’s computational resources to restore the inverse map with exponential density and unbounded degree and
on the absence of the known general polynomial algorithms to solve this task.
Пропонується алгоритм породження стабільних родин взаємно однозначних відображень f(n) у n-вимірному афінному просторі над комутативним кільцем K разом з оберненими до них перетвореннями. Всі
відображення подані у стандартному базисі, в якому обчислюються їх степінь та щільність. Метод дозволяє генерувати перетворення f(n) лінійної щільності зі степенем, заданим обраною лінійною функцією
d(n) та зі щільністю експоненціального розміру для f(n)⁻¹. У випадку K = Fq ми можемо обрати f(n) експоненціального порядку. Пропонується схема генерування публічних ключів поліномінальної криптографії від багатьох змінних вигляду g(n) = T₁ f(n)T₂, де T₁ є мономіальним лінійним перетворенням, а степінь
T₂ дорівнює 1. Оцінки складності показують, що час виконання правила шифрування збігається з часом
обчислення значення квадратичного поліноміального відображення. Процедура декодування, що базується на знанні алгоритму генерації, є ще більш швидкою. Безпека ґрунтується на ідеї недостатності обчислювальних ресурсів у опонента для відновлення оберненого відображення експоненціальної щільності
і необмеженого степеня та відсутності відомих поліноміальних алгоритмів для розв’язання цієї задачі.
Предлагается алгоритм порождения стабильных семейств взаимно однозначных отображений f(n) в n-мерном аффинном пространстве над коммутативным кольцом K вместе с обратными к ним преобразованиями. Все отображения заданы в стандартном базисе, в котором вычисляются их степени и плотности. Метод
позволяет генерировать преобразование f(n) линейной плотности со степенью, заданной выбранной линейной функцией d(n) и с плотностью экспоненциального размера для f(n)⁻¹. В случае K = Fq мы можем
выбрать f(n) экспоненциального порядка. Предлагается схема генерации публичных ключей полиномиальной криптографии от многих переменных вида g(n) = T₁ f(n)T₂, где T₁ является мономиальным линейным преобразованием, а степень T₂ равна единице. Оценки сложности показывают, что время выполнения правила шифрования совпадает с временем вычисления значения квадратичного полиномиального
отображения. Процедура декодирования, основывающаяся на знании алгоритма генерации, является еще
более быстрой. Безопасность основывается на недостатке вычислительных ресурсов у оппонента для восстановления обратного отображения экспоненциальной плотности и неограниченной степени и на отсутствии эффективных алгоритмов для решения этой задачи.
|
| issn |
1025-6415 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/143534 |
| citation_txt |
On multivariate public key based on a pair of transformation with density gap / V.A. Ustimenko // Доповіді Національної академії наук України. — 2018. — № 9. — С. 21-27. — Бібліогр.: 15 назв. — англ. |
| work_keys_str_mv |
AT ustimenkova onmultivariatepublickeybasedonapairoftransformationwithdensitygap AT ustimenkova prokriptosistemivídbagatʹohzmínnihŝogruntuûtʹsânaparíperetvorenʹzprovalomuŝílʹností AT ustimenkova okriptosistemahotmnogihperemennyhosnovannyhnaparepreobrazovaniicprovalomvplotnosti |
| first_indexed |
2025-12-07T17:36:30Z |
| last_indexed |
2025-12-07T17:36:30Z |
| _version_ |
1850871896858427392 |