Исследуются характеристики кодовой системы шифрования типа Мак-Элиса на специальной сумме тензорных произведений базовых кодов, называемой D-кодом. В качестве базовых выбраны двоичные коды Рида - Маллера. Ранее были найдены условия на эти D-коды, при выполнении которых соответствующая система шифрования устойчива к известным структурным атакам на основе произведения Шура - Адамара. Однако при использовании декодера, работающего в пределах половины кодового расстояния, система типа Мак-Элиса на D-кодах обеспечивает стойкость, сравнимую со стойкостью классической системы шифрования Мак-Элиса на кодах Гоппы, при существенно большем размере ключа. В настоящей работе построены два вероятностных декодера для D-кодов. В случае использования этих декодеров найдены параметры некоторых D-кодов, которые при меньшем размере ключа, чем в классической системе, обеспечивают сравнимую стойкость к атаке декодированием по информационным совокупностям. Однако наличие непренебрежимой вероятности ошибочного декодирования пока ограничивает область применения системы шифрования на D-кодах эфемерными механизмами защищённой передачи сеансового ключа (IND-CPA KEM).
Скачать электронную версию публикации
Загружен, раз: 14
- Title О параметрах системы шифрования типа Мак-Элиса на D-кодах, основанных на двоичных кодах Рида-Маллера
- Headline О параметрах системы шифрования типа Мак-Элиса на D-кодах, основанных на двоичных кодах Рида-Маллера
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 67
- Date:
- DOI 10.17223/20710410/67/1
Ключевые слова
механизм защищённой передачи сеансового ключа, Схема Мак-Элиса, D-КодыАвторы
Ссылки
Чижов И. В., Бородин М. А. Классификация произведений Адамара подкодов коразмерности 1 кодов Рида - Маллера // Дискретная математика. 2020. T.32. №1. С. 115-134.
Давлетшина А. М. Поиск эквивалентных ключей криптосистемы Мак-Элиса - Сидельникова, построенной на двоичных кодах Рида - Маллера // Прикладная дискретная математика. Приложение. 2019. №12. С. 98-100.
Высоцкая В. В. О структурных особенностях пространства ключей криптосистемы Мак-Элиса - Сидельникова на обобщенных кодах Рида - Соломона // Дискретная математика. 2024. Т. 36. №4. С. 28-43.
Высоцкая В. В. Квадрат кода Рида - Маллера и классы эквивалентности секретных ключей криптосистемы Мак-Элиса - Сидельникова // Прикладная дискретная математика. Приложение. 2017. №10. С. 66-68.
Бородин М. А., Чижов И. В. Эффективная атака на криптосистему Мак-Элиса, построенную на основе кодов Рида - Маллера // Дискретная математика. 2014. Т. 26. №1. С. 10-20.
Minder L. and Shokrollahi A. Cryptanalysis of the Sidelnikov cryptosystem // LNCS. 2007. V. 4515. P. 347-360. О параметрах системы шифрования типа Мак-Элиса на D-кодах.
Egorova E., Kabatiansky G., Krouk E., and Tavernier C. A new code-based public-key cryptosystem resistant to quantum computer attacks // J. Phys. Conf. Ser. 2019. V. 1163. P. 1-5.
Kabatiansky G. and Tavernier C. A new code-based cryptosystem via pseudorepetition of codes // 16th Intern. Workshop Algebraic Combinat. Coding Theory. Svetlogorsk, Russia, 2018. P.189-191.
Kasami T. and Lin S. On the construction of a class of majority-logic decodable codes // IEEE Trans. Inform. Theory. 1971. V. 17. No.5. P.600-610.
Сидельников В. М. Открытое шифрование на основе двоичных кодов Рида - Маллера // Дискретная математика. 1994. Т. 6. №2. С. 3-20.
Циммерман К.-Х. Методы теории модулярных представлений в алгебраической теории кодирования. М.: МЦНМО, 2011.
Сидельников В. М., Першаков А. С. Декодирование кодов Рида - Маллера при большом числе ошибок // Пробл. передачи информ. 1992. Т. 28. №3. С. 80-94.
Reed I. S. A class of multiple-error-correcting codes and the decoding scheme // IEEE Trans. Inform. Theory. 1954. V. 4. No. 4. P. 38-492.
Massey J. L. Threshold Decoding. Cambridge, MA: MIT Press, 1963.
Abbe E. and Sandon C. A proof that Reed - Muller codes achieve Shannon capacity on symmetric channels // IEEE 64th Ann. Symp. FOCS. Santa Cruz, CA, USA, 2023. P. 177-193.
May A. and Ozerov I., On computing nearest neighbors with applications to decoding of binary linear codes // LNCS. 2015. V. 9056. P.203-228.
Kudekar S., Kumar S., Mondelli M., et al. Reed - Muller codes achieve capacity on erasure channels // Proc. STOC'16. N.Y.: ACM, 2016. P.658-669.
Both L. and May A. Decoding linear codes with high error rate and its impact for LPN security // LNCS. 2018. V. 10786. P.25-46.
Prange E. The use of information sets in decoding cyclic codes // IRE Trans. Inform. Theory. 1962. V.8. No.5. P.5-9.
Baldi M., Barenghi A., Chiaraluce F., et al. LEDAcrypt: Low-dEnsity parity-check coDebAsed cryptographic systems. https://www.ledacrypt.org/documents/LEDAcrypt_v3.pdf.2019.
Campagna M. and Crockett E. Hybrid Post-Quantum Key Encapsulation Methods (PQ KEM) for Transport Layer Security 1.2 (TLS). https://www.ietf.org/archive/id/draft-campagna-tls-bike-sike-hybrid-07.html. 2021.
Drucker N., Gueron S., and Kostic D. A Lean BIKE KEM Design for Ephemeral Key Agreement. https://csrc.nist.gov/csrc/media/Events/2024/fifth-pqc-standar dization-conference/documents/papers/a-lean-bike-kem.pdf. 2024.
Vedenev K. V. and Kosolapov Y. V. A reaction attack against cryptosystems based on quasigroup MDPC codes // 2023 XVIII Intern. Symp. REDUNDANCY. Moscow, Russia, 2023. P. 70-75.
Joux A., Loss J., and Wagner B. Kleptographic Attacks against Implicit Rejection. https: //eprint.iacr.org/2024/260. 2024.
Guo Q., Johansson T., and Wagner P. S. A key recovery reaction attack on QC-MDPC // IEEE Trans. Inform. Theory. 2018. V. 65. No. 3. P. 1845-1861.
Arago N., Barreto P., Bettaieb S., et al. BIKE: Bit Flipping Key Encapsulation. https://hal.science/hal-01671903/document.2017.
Hofheinz D., Hovelmanns K., and Kiltz E. A modular analysis of the Fujisaki - Okamoto transformation // LNCS. 2017. V. 10677. P.341-371.
Ye M. and Abbe E. Recursive projection-aggregation decoding of Reed - Muller codes // IEEE Trans. Inform. Theory. 2020. V. 66. No. 8. P.4948-4965.
Abbe E., Sberlo O., Shpilka A., and Ye M. Reed - Muller codes // Foundations and Trends in Commun. Inform. Theory. 2023. V. 20. No. 1-2. P. 1-156.
Деундяк В. М., Лелюк Е. А. Теоретико-графовый метод декодирования некоторых групповых MLD-кодов // Дискретн. анализ и исслед. опер. 2020. Т. 27. №2. С. 17-42.
Косолапов Ю. В., Лелюк Е. А. Криптосистема типа Мак-Элиса на D-кодах // Математические вопросы криптографии. 2024. Т. 15. №.2. С. 69-90.
Косолапов Ю. В., Лелюк Е. А. О структурной стойкости криптосистемы типа Мак-Элиса на сумме тензорных произведений бинарных кодов Рида - Маллера // Прикладная дискретная математика. 2022. №57. С. 22-39.
Krouk E., Kabatiansky G., and Tavernier C. McEliece-type cryptosystem based on correction of errors and erasures // 2023 XVIII Intern. Symp. REDUNDANCY. Moscow, Russia, 2023. P. 173-177.
Lau T. Sh. C., Ivanov F., Ariffin M. R. K., et al. New code-based cryptosystems via the IKKR framework // J. Inform. Security Appl. 2023. V. 76. Article 103530.
Ivanov F., Kabatiansky G., Krouk E., and Rumenko N. A new code-based cryptosystem // LNCS. 2020. V. 12087. P.41-49.
Mora R. and Tillich J.-P. On the dimension and structure of the square of the dual of a Goppa code // Des. Codes Cryptogr. 2023. No. 91. P.1351-1372.
Couvreur A., Mora R., and Tillich J.-P. A New Approach Based on Quadratic Forms to Attack the McEliece Cryptosystem. Cryptology ePrint Archive. 2023. Paper 2023/950.
Bardet M., Mora R., and Tillich J.-P. Polynomial Time Key-Recovery Attack on High Rate Random Alternant Codes. arXiv: 2304.14757, 2023.
Niederreiter H. Knapsack-type cryptosystems and algebraic coding theory // Prob. Contr. Inform. Theory. 1986. V. 15. No. 2. P.157-166.
Albrecht M., Cid C., Paterson K. G., et al. Nts-kem // NIST PQC Round. 2019. V. 2. P. 4-13.
Alagic G., Apon D., Cooper D., et al. Status Report on the Third Round of the NIST PostQuantum Cryptography Standardization Process. NIST, 2022. https://csrc.nist.gov/pubs/ir/8413/upd1/final.
McEliece R. J. A public-key cryptosystem based on algebraic coding theory // Deep Space Network Progress Report. 1978. No. 44. P. 114-116.
Albrecht M. R., Bernstein D. J., Chou T., et al. Classic McEliece: Conservative Code-Based Cryptography. NIST PQC Call for Proposals, 2022. Round 4 Submission. https://classic.mceliece.org/nist/mceliece-20201010.pdf.
Weger V., Gassner N., and Rosenthal J. A Survey on Code-Based Cryptography. arXiv: 2201.07119, 2024. 168p.
О параметрах системы шифрования типа Мак-Элиса на D-кодах, основанных на двоичных кодах Рида-Маллера | Прикладная дискретная математика. 2025. № 67. DOI: 10.17223/20710410/67/1
Скачать полнотекстовую версию
Загружен, раз: 206