Skip to content
Назад к результатам поиска

Криптография на основе решёток

Автор метода
Miklós Ajtai
Год
1996
Тип
public-key cryptosystem based on lattice hardness
Семейство
Post-quantum cryptography

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Криптография на основе решёток — это класс криптосистем, безопасность которых основана на вычислительной сложности задач, связанных с решётками, в частности, задачи о кратчайшем векторе (SVP) и задачи обучения с ошибками (LWE).

Предложенные впервые Миклошем Аждаи в 1996 году, подходы на основе решёток стали ведущими кандидатами для постквантовой криптографии. В отличие от RSA и ECC, уязвимых для квантовых компьютеров, задачи на решётках считаются сложными даже для квантовых алгоритмов.

Интуиция метода

Решётка — это дискретная подгруппа евклидова пространства, образованная целочисленными линейными комбинациями базисных векторов. Криптография на основе решёток использует разрыв между двумя задачами: найти короткий вектор в решётке вычислительно сложно, но с дополнительной информацией (секретным базисом) короткий вектор можно найти быстро. Криптография с открытым ключом строится путём публикации сложного базиса и сохранения секретности простого базиса. Добавление небольшого случайного шума (парадигма обучения с ошибками) дополнительно усиливает безопасность, делая задачу похожей на решение зашумлённой линейной системы, которую сложно решить.

История

Фундаментальная работа Аждаи 1996 года связала сложность решёток с криптографией. Структура обучения с ошибками (LWE) Регева в 2005 году послужила практической и универсальной основой для криптографии на решётках. Область ускорила своё развитие после того, как академические и правительственные учреждения осознали угрозу квантовых вычислений для существующей криптографической инфраструктуры. В 2022 году NIST стандартизировал постквантовые криптографические алгоритмы, выбрав схемы на основе решёток (CRYSTALS-Kyber для шифрования, CRYSTALS-Dilithium для подписей) в качестве основных рекомендаций.

Когда применять

Криптография на основе решёток необходима для систем, разработанных для сохранения безопасности от будущих квантовых компьютеров. Она рекомендуется для долгосрочной конфиденциальности конфиденциальных данных, правительственной и военной связи, а также инфраструктуры, которая должна оставаться безопасной десятилетиями. По мере созревания стандартизированных постквантовых алгоритмов (NIST недавно стандартизировал ML-KEM и ML-DSA) методы на основе решёток становятся мейнстримом в современных криптографических системах.

Ограничения и замечания

  • Большие размеры ключей и шифротекстов по сравнению с традиционными RSA или ECC, что увеличивает накладные расходы на хранение и передачу
  • Более новые и менее широко развёрнутые, чем RSA или ECC, поэтому опыт реального развёртывания ограничен
  • Некоторые схемы на основе решёток имеют тонкие параметры выбора, которые значительно влияют на безопасность; неправильные параметры могут быть катастрофическими

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Считается устойчивой к атакам квантовых компьютеров, включая алгоритм Шора
  • Прочные математические основы, основанные на хорошо изученных задачах на решётках
  • Поддерживает как шифрование, так и цифровые подписи в рамках одной системы
  • Доступны практические реализации с разумными вычислительными затратами для современного оборудования

Применение

  • Постквантовая защита транспортных соединений для защиты связи от будущего квантового дешифрования
  • Долгосрочное архивное шифрование документов и данных, которые должны оставаться секретными десятилетиями
  • Правительственные и военные системы связи, устойчивые к квантовым угрозам
  • Блокчейн и криптовалютные системы, разработанные для квантово-устойчивой безопасности
  • IoT и встраиваемые системы, где квантовая устойчивость является требованием к проектированию
  • Гибридные криптографические системы, объединяющие решётки и традиционные алгоритмы в переходный период криптографии

Как это работает

Как это работает

1

Выберите размерность решётки n, модуль q и распределение ошибок. Сгенерируйте секретный короткий базис и выведите из него открытый базис с помощью преобразований решётки.

2

Открытый ключ выводится из сложного базиса решётки; он не даёт информации о секретном базисе с вычислительной точки зрения.

3

Для шифрования добавьте открытый текст к зашумлённой линейной комбинации векторов открытого базиса, создавая точку решётки плюс шум.

4

Используя секретный короткий базис, редуцируйте зашумлённую точку решётки и извлеките открытый текст.

Частые ошибки

  • Выбор параметров решётки (размерность, модуль, распределение ошибок) нетривиален; настоятельно рекомендуется использовать стандартные параметры, одобренные NIST
  • Атаки по побочным каналам (по времени, по анализу энергопотребления) на операции с решётками требуют тщательной реализации; алгоритмы с постоянным временем выполнения имеют решающее значение
  • Неправильное смешивание алгоритмов на основе решёток и классических алгоритмов может привести к созданию гибридных систем с неожиданными слабостями

Часто задаваемые вопросы

Что такое задача обучения с ошибками (LWE)?

LWE — это вычислительная задача, в которой даны зашумлённые линейные уравнения над конечным полем. Восстановить секретный x из уравнений вида a·x + e (mod q), где a — случайное, x — секретное, а e — небольшой шум, вычислительно сложно.

Почему ключи на основе решёток больше ключей RSA?

Базисы решёток и матрицы, которые их кодируют, содержат больше информации, чем одно составное число. Криптографическое кодирование базиса решётки требует больше бит, хотя последние схемы оптимизировали представления.

Являются ли задачи на решётках квантово-устойчивыми?

Неизвестно ни одного квантового алгоритма, который был бы быстрее классических алгоритмов для задач на решётках, таких как SVP или LWE, хотя это остаётся активной областью исследований. Предполагается, что сложность решёток переживёт квантовые компьютеры.

Каковы рекомендации NIST по криптографии на решётках?

NIST стандартизировал ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism) для шифрования и ML-DSA (Module-Lattice-Based Digital Signature Algorithm) для подписей в качестве основных постквантовых алгоритмов в FIPS 203 и FIPS 204.

Могу ли я использовать криптографию на решётках сегодня?

Да. Многие современные криптографические библиотеки теперь поддерживают стандартизированные NIST алгоритмы на решётках. Организации, обрабатывающие конфиденциальные данные с длительными сроками хранения, должны начать планирование миграции.

Похожие методы

Источники

  1. Ajtai, M. (1996). Generating hard instances of the short basis problem. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 99-108.

    Открыть ссылку на публикацию
    Скопировано.
  2. Regev, O. (2005). On lattices, learning with errors, hard instances, and public key cryptography. In Proceedings of STOC 2005, pp. 84-93.

    Открыть ссылку на публикацию
    Скопировано.