Алгоритм построения матриц, уменьшающих расстояние кода

Аннотация

Введение: уменьшение кодового расстояния представляет собой важный инструмент для решения некоторых задач в теории информации и криптографии. Например, в криптографических кодовых системах, таких как система Мак-Элиса, снижение кодового расстояния напрямую влияет на уменьшение длины открытого ключа, что является критически важным фактором для повышения эффективности и применимости кодовых криптосистем. Цель: разработать алгоритм построения матриц, способный эффективно уменьшать расстояние кода. Результаты: предложен итерационный алгоритм, который формирует ряд маскирующих матриц, успешно уменьшающих расстояние заданного кода. Для проверки изложенного подхода был выбран код Боуза — Чоудхури — Хоквингхема и криптографическая система Мак-Элиса. Проведен ряд экспериментов, показывающих эффективность разработанного алгоритма. Суть экспериментов заключалась в применении к коду Боуза — Чоудхури — Хоквингхема разработанного алгоритма, после чего полученный код внедрялся в систему Мак-Элиса. Полученная криптосистема подвергалась атакам на основе декодирования по информационным совокупностям. Результаты экспериментов показали, что к преобразованным кодам неприменима атака на основе декодирования по информационным совокупностям, а вес порождающей матрицы нового кода, которая является частью открытого ключа, стал меньше. Практическая значимость: невозможность применить декодирование по информационным совокупностям позволяет уменьшить объем открытого ключа в криптосистеме, что представляет значительный интерес для практики использования кодовых криптосистем. Обсуждение: приложение алгоритма не ограничивается только криптографией. Он может быть применен для преобразования каналов передачи данных, обладающих памятью. Отметим, что для полноценного внедрения матриц, уменьшающих расстояние кода, в криптографические системы необходима проверка декодируемости вектора ошибок после обратного преобразования, что является предметом дальнейших исследований.