Про криптосистеми від багатьох змінних, що ґрунтуються на парі перетворень з провалом у щільності
DOI:
https://doi.org/10.15407/dopovidi2018.09.021Ключові слова:
алгебраїчні графи, криптографія від багатьох змінних, оцінки складності, постквантова криптографія, публічні ключіАнотація
Пропонується алгоритм породження стабільних родин взаємно однозначних відображень f(n) у n-вимірному афінному просторі над комутативним кільцем K разом з оберненими до них перетвореннями. Всі відображення подані у стандартному базисі, в якому обчислюються їх степінь та щільність. Метод дозволяє генерувати перетворення f(n) лінійної щільності зі степенем, заданим обраною лінійною функцією d(n) та зі щільністю експоненціального розміру для f(n)–1. У випадку K = Fq ми можемо обрати f(n) екс-поненціального порядку. Пропонується схема генерування публічних ключів поліномінальної криптографії від багатьох змінних вигляду g(n) = T1f(n)T2, де T1 є мономіальним лінійним перетворенням, а степінь T2 дорівнює 1. Оцінки складності показують, що час виконання правила шифрування збігається з часом обчислення значення квадратичного поліноміального відображення. Процедура декодування, що базується на знанні алгоритму генерації, є ще більш швидкою. Безпека ґрунтується на ідеї недостатності обчислювальних ресурсів у опонента для відновлення оберненого відображення експоненціальної щільності і необмеженого степеня та відсутності відомих поліноміальних алгоритмів для розв’язання цієї задачі.
Завантаження
Посилання
Machi, A. (2012). Algebra for symbolic computation. Springer. doi: https://doi.org/10.1007/978-88-470-2397-0
Ding, J., Gower, J. E. & Schmidt, D. S. (2006). Multivariate public key cryptosystems. Advances in Information Security, Vol. 25. Springer.
Goubin, L., Patarin, J. & Yang, Bo-Yin. (2011). Multivariate cryptography. In Encyclopedia of Cryptography and Security. 2nd ed. (pp. 824-828). Springer.
Ustimenko, V. (2017). On the families of stable multivariate transformations of large order and their cryptographical applications. Tatra Mt. Math. Publ., 70, pp. 107-117. doi: https://doi.org/10.1515/tmmp-2017-0021
Ustimenko, V. A. (2015). On Schubert cells in Grassmannians and new algorithm of multivariate cryptography. Tr. Inst. Mat., 23, No. 2, pp. 137-148.
Ustimenko, V. A. (1998). On the varieties of parabolic subgroups, their generalizations and combinatorial applications. Acta Appl. Math., 52, pp. 223-238. doi: https://doi.org/10.1023/A:1005919327201
Ustimenko, V. (2017). On desynchronised multivariate El Gamal algorithm. Retrieved from https://eprint.iacr.org/2017/712.pdf
Cossidente, A. & de Ressmine, M. J. (2004). Remarks on Singer cycle groups and their normalizers. Designs Codes Cryptogr., 32, pp. 97-102. doi: https://doi.org/10.1023/B:DESI.0000029214.50635.17
Kantor, W. (1982). Linear groups containing a Singer cycle. J. Algebra, 62, pp. 232-234. doi: https://doi.org/10.1016/0021-8693(80)90214-8
Ustimenko, V. (2015). On algebraic graph theory and non–bijective maps in cryptography. Algebra Discrete Math., 20, No. 1, pp. 152-170.
Ustimenko, V. (2017). On new multivariate cryptosystems with nonlinearity gap. Algebra Discrete Math., 23, No. 2, pp. 331-348.
Ustimenko, V. (2017). On new multivariate cryptosystems based on hidden Eulerian equations. Dopov. Nac. akad. nauk Ukr., No. 5, pp. 17-24. doi: https://doi.org/10.15407/dopovidi2017.05.017
Romańczuk-Polubiec, U. & Ustimenko, V. (2015). On two windows multivariate cryptosystem depending on random parameters. Algebra Discrete Math., 19, No. 1, pp. 101-129.
Ustimenko, V. & Romańczuk, U. (2013). On dynamical systems of large girth or cycle indicator and their applications to multivariate cryptography. In Artificial Intelligence, Evolutionary Computing and Metaheuristics (pp. 257-285). Berlin: Springer. doi: https://doi.org/10.1007/978-3-642-29694-9_11
Polak, M., Romańczuk, U., Ustimenko, V. & Wróblewska, A. (2013). On the applications of extremal graph theory to coding theory and cryptography. Electron. Notes Discrete Math., 43, pp. 329-342. doi: https://doi.org/10.1016/j.endm.2013.07.051
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2024 Доповіді Національної академії наук України
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.
