Вычислительные допущения о сложности

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

Definition

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

Scope

Эта тема охватывает допущения, на которых основывается криптография: существование односторонних функций, теоретико-числовые задачи (факторизация, RSA, дискретный логарифм), а также решёточные и кодовые задачи, используемые в постквантовой криптографии. В ней рассматривается иерархия допущений, различие между сложностью в худшем и среднем случае, а также методы проверки допущений. Она не включает механизмы редукции, связывающие допущения со схемами, и сами определения безопасности, которые рассматриваются в смежных темах.

Core questions

• Почему криптографическая безопасность должна основываться на недоказанных допущениях о сложности?
• Каковы основные допущения (односторонние функции, факторизация, дискретный логарифм, решётки)?
• Как допущения соотносятся друг с другом по силе?
• В чём разница между сложностью в худшем и среднем случае?
• Как проверяются кандидатные сложные задачи и что происходит, когда одна из них оказывается нарушенной?

Key concepts

• односторонняя функция
• функция с лазейкой
• допущение о факторизации целых чисел
• допущение о дискретном логарифме
• допущения RSA и Диффи-Хеллмана
• обучение с ошибками (LWE)
• сложность в худшем случае против сложности в среднем случае
• P против NP
• иерархия допущений

Key theories

Односторонние функции как минимальное допущение

Существование односторонних функций — легко вычисляемых, трудно обратимых — необходимо и достаточно для большей части симметричной криптографии и является самым базовым допущением; почти вся криптография предполагает как минимум это.

Теоретико-числовые и решёточные допущения

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

Mechanisms

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

Clinical relevance

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

Evidence & guidelines

Стандартные организации отдают предпочтение допущениям с длительным криптоаналитическим опытом; процесс постквантовой стандартизации NIST явно оценивал зрелость и надёжность базовых решёточных, кодовых и хеш-допущений. Передовая практика избегает экзотических или недавно предложенных допущений для систем с высокой степенью надёжности и предпочитает консервативные, хорошо проверенные задачи, с размерами ключей, установленными с учётом наилучших известных атак.

History

Зависимость от сложности возникла с появлением криптографии с открытым ключом в 1976 году, когда Диффи и Хеллман связали безопасность с дискретным логарифмом, а RSA — с факторизацией. В 1980-х годах были формализованы односторонние функции и различие между худшим и средним случаем. Редукции Аджтая от худшего случая к среднему (1996) и задача обучения с ошибками Регева (2005) установили решёточные допущения, которые приобрели известность как квантово-устойчивые основы и лежат в основе новых постквантовых стандартов.

Key figures

• Whitfield Diffie
• Martin Hellman
• Oded Goldreich
• Oded Regev
• Andrew Yao

Seminal works

• diffie1976
• goldreich2001
• katz2020

Frequently asked questions

Почему мы не можем просто доказать, что эти проблемы сложны?

Доказательство того, что проблема требует сверхполиномиального времени, решило бы глубокие открытые вопросы в теории сложности (в частности, P против NP), которые остаются нерешёнными. Поэтому криптография опирается на допущения, правдоподобность которых проистекает из десятилетий безуспешных попыток эффективно их решить.

Что произойдёт, если допущение о сложности будет нарушено?

Каждая схема, безопасность которой сводится к этому допущению, потенциально становится небезопасной и должна быть заменена. Именно поэтому квантовая угроза факторизации и дискретным логарифмам вызвала глобальный переход к схемам, основанным на других, квантово-устойчивых допущениях.