Криптография на основе многочленов от многих переменных
На английском языке: Multivariate cryptography
Коротко
Семейство квантово-устойчивых криптографических алгоритмов, стойкость которых основывается на предположении о вычислительной сложности задачи решения системы нелинейных уравнений от многих переменных над конечным полем. Криптографические алгоритмы данного семейства отличаются относительно высокой эффективностью и небольшой длиной подписи при большой длине ключей. В то же время, наличие заведомо известной внутренней структуры делает такие алгоритмы уязвимыми для специфических методов криптоанализа
Семейство квантово-устойчивых криптографических алгоритмов, стойкость которых основывается на предположении о вычислительной сложности задачи решения системы нелинейных уравнений от многих переменных над конечным полем. Криптографические алгоритмы данного семейства отличаются относительно высокой эффективностью и небольшой длиной подписи при большой длине ключей. В то же время, наличие заведомо известной внутренней структуры делает такие алгоритмы уязвимыми для специфических методов криптоанализа
Подробно
Перспектива появления квантового компьютера достаточной производительности для реализации алгоритма Шора делает нестойкими традиционные схемы цифровой подписи, основанные на задаче факторизации, либо дискретного логарифмирования. Для решения этой проблемы было предложено использовать в том числе механизмы, использующие системы уравнений от многих переменных (multivariate cryptography).
Трудная задача, лежащая в основе данного класса криптографических алгоритмов – решение системы полиномиальных уравнений над конечным полем. В общем случае эта задача NP-полна. Существуют различные методы ее решения, в том числе методы линеаризации (XL-метод), методы, основанные на использовании базисов Грёбнера (F4, F5 и другие), но с увеличением числа переменных они очень быстро становятся неэффективными.
Перспектива появления квантового компьютера достаточной производительности для реализации алгоритма Шора делает нестойкими традиционные схемы цифровой подписи, основанные на задаче факторизации, либо дискретного логарифмирования. Для решения этой проблемы было предложено использовать в том числе механизмы, использующие системы уравнений от многих переменных (multivariate cryptography).
Трудная задача, лежащая в основе данного класса криптографических алгоритмов – решение системы полиномиальных уравнений над конечным полем. В общем случае эта задача NP-полна. Существуют различные методы ее решения, в том числе методы линеаризации (XL-метод), методы, основанные на использовании базисов Грёбнера (F4, F5 и другие), но с увеличением числа переменных они очень быстро становятся неэффективными.
Первая криптографическая схема на основе многочленов от многих переменных была предложена Т. Мацумото и Х. Имаи в 1988 году, в 1995 году она была взломана Ж. Патарином.
В свою очередь, Ж. Патарин в 1996 году разработал так называемую схему HFE (Hidden Field Equations), однако, в 2005 году А. Шамир предложил эффективную атаку и на нее.
Стоит также упомянуть схему цифровой подписи SFLASH, которая в 2003 году стала победителем европейского конкурса NESSIE, но уже в 2007 году была полностью взломана.
В свою очередь, Ж. Патарин в 1996 году разработал так называемую схему HFE (Hidden Field Equations), однако, в 2005 году А. Шамир предложил эффективную атаку и на нее.
Стоит также упомянуть схему цифровой подписи SFLASH, которая в 2003 году стала победителем европейского конкурса NESSIE, но уже в 2007 году была полностью взломана.
Помимо HFE, Ж. Патарин разработал оригинальную схему цифровой подписи UOV (Unbalanced Oil and Vinegar), которая и стала прообразом многих современных схем этого класса, например, выбывших из конкурса NIST участников: LUOV, GeMSS, Rainbow.
Секретным ключом схемы, основанной на многочленах от многих переменных, является тройка преобразований — легкообратимое квадратичное отображение и два обратимых линейных отображения, а открытым ключом — их композиция, которая выглядит как случайное нелинейное преобразование. Для зашифрования сообщения к нему применяется преобразование, соответствующее открытому ключу, для расшифрования — поочередно обратные к секретным преобразования.
Основными проблемами, связанными с криптографическими алгоритмами на основе многочленов от многих переменных, являются:
Результаты многолетнего успешного криптоанализа алгоритмов этого класса показывают необходимость особенно тщательного выбора параметров при их синтезе.
При этом к к потенциальным преимуществам таких алгоритмов относятся простота и эффективность реализации, а также небольшой размер подписи.
По состоянию на 2022 год, ни один из алгоритмов, основанных на системах многочленов от многих переменных, не выдержал испытаний конкурсом NIST. Наиболее перспективный алгоритм Rainbow был успешно взломан уже после того, как его объявили финалистом конкурса, серьезно подорвав репутацию этого синтезного направления.
Секретным ключом схемы, основанной на многочленах от многих переменных, является тройка преобразований — легкообратимое квадратичное отображение и два обратимых линейных отображения, а открытым ключом — их композиция, которая выглядит как случайное нелинейное преобразование. Для зашифрования сообщения к нему применяется преобразование, соответствующее открытому ключу, для расшифрования — поочередно обратные к секретным преобразования.
Основными проблемами, связанными с криптографическими алгоритмами на основе многочленов от многих переменных, являются:
- наличие в секретном преобразовании определенной структуры, необходимой для его эффективного обращения, но, в то же время, дающей возможность построения специфических алгебраических атак;
- относительно большие размеры ключей, которые задаются системами квадратичных уравнений над конечным полем.
Результаты многолетнего успешного криптоанализа алгоритмов этого класса показывают необходимость особенно тщательного выбора параметров при их синтезе.
При этом к к потенциальным преимуществам таких алгоритмов относятся простота и эффективность реализации, а также небольшой размер подписи.
По состоянию на 2022 год, ни один из алгоритмов, основанных на системах многочленов от многих переменных, не выдержал испытаний конкурсом NIST. Наиболее перспективный алгоритм Rainbow был успешно взломан уже после того, как его объявили финалистом конкурса, серьезно подорвав репутацию этого синтезного направления.
Как уже сегодня использовать постквантовую криптографию для защиты данных вашего бизнеса?
- Получить больше информации о квантовых угрозах и методах защиты именно для своей индустрии;
- Провести аудит текущей инфраструктуры кибербезопасности вашей компании, подобрать оптимальные решения защиты от квантовых угроз и разработать стратегию защиты;
- Провести пилотирование квантово-устойчивых решений и масштабировать полученный опыт.