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...
Збережено в:
Дата: | 2018 |
---|---|
Автор: | |
Формат: | Стаття |
Мова: | English |
Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2018
|
Назва видання: | Доповіді НАН України |
Теми: | |
Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/143534 |
Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
Цитувати: | On multivariate public key based on a pair of transformation with density gap / V.A. Ustimenko // Доповіді Національної академії наук України. — 2018. — № 9. — С. 21-27. — Бібліогр.: 15 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of UkraineРезюме: | 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. |
---|