В.В. Высоцкая, Эффективные алгоритмы построения невырожденных квазициклических матриц

Доклад мотивирован задачей поиска перспективного варианта постквантовой схемы электронной подписи. Среди всех схем на кодах, исправляющих ошибки, конструкции на основе квазициклических кодов выделяются своей высокой эффективностью с точки зрения хранения ключевой информации. В ряде таких схем существенным шагом алгоритма генерации ключей является построение невырожденной двоичной квазициклической матрицы. Эту задачу можно решать классическими методами, не учитывающими внутреннюю структуру матриц, либо специализированными подходами, как, например, было сделано в схеме LEDAcrypt. В последнем случае циклическая подматрица сопоставляется многочлену, и исходная задача сводится к построению невырожденной матрицы в кольце многочленов. Однако предложенный алгоритм имеет экспоненциальную сложность. В докладе будет развита идея, предложенная в LEDAcrypt: работа будет вестись с матрицами многочленов и производными от них вспомогательными матрицами. Будет разобрана связь между свойствами невырожденности матриц всех этих типов. Дадим определение обратимой матрицы в кольце многочленов и покажем, что обратимость в этом случае эквивалентна невырожденности. Также будет продемонстрирована невозможность применения в кольце алгоритма гауссового исключения и будет предложена его альтернатива. В завершение будут описаны специализированные алгоритмы построения невырожденных квазициклических матриц, которые существенно используют циклическую структуру и обеспечивают лучшие на сегодняшний день оценки трудоемкости.