Существование в коде некоторой структуры может привести к снижению стойкости всей построенной на нем системы. Часто для сокрытия структуры используются подкоды известных кодов. Стойкость подкодов, квадрат Адамара которых равен квадрату полного кода, сводится к его стойкости. В работе найдены предельные условия на количество векторов степени r, удаление которых сохраняет описанную уязвимость. Найдены также условия, которые позволяют устранить её. Для r = 2 найдена точная структура всех стойких в данном смысле подкодов. Для произвольного кода RM(r, m) искомое количество векторов, удаление которых позволяет добиться стойкости, оценено с двух сторон. Доказано, что доля подкодов, квадрат Адамара которых не равен квадрату исходного кода, стремится к нулю (при m стремящемся к бесконечности), если наложить дополнительные условия на коразмерность подкода и параметр r. Таким образом, некоторые нестойкие подкоды могут быть сразу же выявлены в результате выполнения проверок, предложенных в работе.
Скачать электронную версию публикации
Загружен, раз: 38
- Title Характеристики квадрата Адамара специальных подкодов кода Рида - Маллера
- Headline Характеристики квадрата Адамара специальных подкодов кода Рида - Маллера
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 53
- Date:
- DOI 10.17223/20710410/53/5
Ключевые слова
произведение Адамара, криптосистема Мак-Элиса, подкоды Рида - Маллера, коды Рида - Маллера, кодовая криптография, постквантовая криптографияАвторы
Ссылки
Rodl V. On a Packing and Covering Problem. European J. Combinatorics, 1985, vol. 6, no. 1, pp.69-78.
Erdos P. and Spencer J. Probabilistic Methods in Combinatorics. Budapest, Akademiai Kiado, 1974. 106 p.
Couvreur A., Gaborit P., Gauthier-Umana V., et al. Distinguisher-based attacks on public-key cryptosystems using Reed - Solomon codes. Designs, Codes, Cryptogr., 2014, vol. 73, no. 2, pp.641-666.
Chizhov I. V. and Borodin M. A. Hadamard products classification of subcodes of Reed - Muller codes codimension 1. Discr. Math. Appl., 2020, vol.32, no. 1, pp. 115-134.
Borodin M. A. and Chizhov I. V. Effective attack on the McEliece cryptosystem based on Reed - Muller codes. Discr. Math. Appl., 2014, vol. 24, no. 5, pp. 273-280.
Minder L. and Shokrollahi A. Cryptanalysis of the Sidelnikov cryptosystem. LNCS, vol. 4515, pp. 347-360.
Couvreur A., Marquez-Corbella I., and Pellikaan R. Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes. Coding Theory Appl.ications. CIM Ser. Math. Sci., 2015, vol. 3, pp. 133-140.
Lee Y., Lee W., Kim Y. S., and No J.-S. Modified pqsig RM: RM code-based signature scheme. IEEE Access, 2020, vol. 8, pp. 177506-177518.
Berger T. P. and Loidreau P. How to mask the structure of codes. Designs, Codes, Cryptogr., 2005, vol. 35, no. 1, pp. 63-79.
Wieschebrink C. Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes. LNCS, 2010, vol. 6061, pp. 61-72.
Wieschebrink C. An attack on a modified Niederreiter encryption scheme. LNCS, 2006, vol. 3958, pp. 14-26.
Niederreiter H. Knapsack-type cryptosystems and algebraic coding theory. Problems Control Inform. Theory, 1986, vol. 15, no. 2, pp. 159-166.
https://csrc.nist.gov/Projects/post-quantum-cryptography/Post-Quantum-Crypto graphy-Standardization/Call-for-Proposals - NIST Call for Proposals, 2016.
McEliece R. J. A public-key cryptosystem based on algebraic coding theory. DSN Progress Report, 1978, vol.4244, pp. 114-116.
Shor P. V. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Computing, 1997, vol.26, no. 5, pp. 1484-1509.
Характеристики квадрата Адамара специальных подкодов кода Рида - Маллера | Прикладная дискретная математика. 2021. № 53. DOI: 10.17223/20710410/53/5
Скачать полнотекстовую версию
Загружен, раз: 110