Complexity в криптографии и ML

В 2024 году NIST опубликовал три первых пост-квантовых стандарта (FIPS 203, 204, 205) и начал отсчёт миграции мировой инфраструктуры с RSA и ECDSA на решёточную криптографию. За этим переходом стоит не страх перед каким-то конкретным квантовым компьютером, а понимание теоретической complexity. Алгоритм Шора (1994) показал: задачи, на которых стоит современная защита данных, ломаются квантово полиномиально. А Аджтай (1996) и Регев (2005) построили альтернативу из задач, для которых даже квантовое преимущество subexponential. Theoretical complexity не абстракция - она прямо определяет, какие криптосистемы переживут следующие 50 лет.

• **NIST FIPS 203/204:** Kyber (KEM) и Dilithium (signatures) - первые квантово-устойчивые стандарты на основе Module-LWE
• **Zcash / Ethereum L2:** zk-SNARK и zk-STARK защищают конфиденциальные транзакции и scaling-rollups
• **Signal / WhatsApp:** Hybrid handshake (X25519 + Kyber-768) для защиты от 'harvest now, decrypt later' атак

Односторонние функции: фундамент криптографии

Криптография держится на одной гипотезе: существуют функции, которые легко считаются вперёд и трудно обращаются. Одностороннюю функцию f: {0,1}* -> {0,1}* строго определяет Леонид Левин и Рассел Импальяццо: f вычислима за полиномиальное время, но для любого вероятностного полиномиального противника вероятность найти x по f(x) пренебрежимо мала. Существование one-way functions (OWF) - открытая проблема, эквивалентная P != NP по силе следствий, но независимая: P != NP не влечёт автоматически OWF. Без OWF не существует криптографии с открытым ключом, цифровой подписи, псевдослучайных генераторов - всей современной защиты данных.

Кандидаты в OWF: целочисленная факторизация (основа RSA), дискретный логарифм в мультипликативной группе (Diffie-Hellman, ElGamal), дискретный логарифм на эллиптической кривой (ECDSA). У каждого best classical algorithm имеет subexponential или exponential сложность - но никаких доказательств отсутствия polynomial алгоритма не существует. Алгоритм Шора (1994) ломает все эти кандидаты на квантовом компьютере за полиномиальное время - именно поэтому индустрия мигрирует на post-quantum криптографию.

Zero-Knowledge Proofs: доказательство без раскрытия

Доказательства с нулевым разглашением (Zero-Knowledge Proofs, ZKP) - концепция Голдвассера, Микали и Ракоффа (1985). Прувер хочет убедить верификатора, что знает решение задачи x, не раскрывая решения. Формально протокол должен удовлетворять трём свойствам: completeness (честный прувер всегда убедит верификатора), soundness (нечестный прувер не пройдёт с пренебрежимой вероятностью), zero-knowledge (верификатор после взаимодействия знает не больше, чем до него). Существование non-trivial ZKP для всех NP - теорема Goldreich-Micali-Wigderson (1991): они построили ZKP для 3-раскраски графа на основе обязательной схемы (commitment scheme), которая существует при условии OWF.

Современные ZKP: zk-SNARKs (Succinct Non-interactive ARguments of Knowledge) - доказательство любого NP-утверждения умещается в ~200 байт и проверяется за миллисекунды. Используются в Zcash для конфиденциальных транзакций, в Ethereum L2 (StarkNet, zkSync, Scroll) для масштабирования и в идентификационных протоколах (anonymous credentials, KYC без раскрытия данных). zk-STARKs - вариант без trusted setup, post-quantum secure, но с большими доказательствами (~50 KB).

Hardness of Learning: сложность ML с теоретической точки зрения

Теория PAC-обучения (Probably Approximately Correct, Лесли Валиант, 1984) задаёт формальную постановку: класс гипотез H обучаем, если существует алгоритм, который по полиномиальному числу примеров возвращает гипотезу с малой ошибкой и высокой вероятностью. Большие классы гипотез вычислительно необучаемы - даже если статистически данных достаточно. Klivans-Sherstov показали: обучение пересечений полупространств NP-трудно. Daniely, Linial, Shalev-Shwartz: глубокие нейросети с ReLU - вычислительно необучаемы в худшем случае при стандартных криптогипотезах. Это объясняет, почему градиентный спуск работает не для произвольных функций, а лишь для тех, что обладают структурой реальных данных.

Связь криптографии и ML двунаправленная. С одной стороны, hard learning problems - кандидаты в OWF: если функция вычислима, но не обучаема по парам (x, f(x)), она односторонняя в практическом смысле. С другой, успехи в ML (особенно LLM) ставят вопрос о пересмотре теоретических оценок: модели достигают обобщения там, где worst-case bounds давно предсказали невозможность. Это противоречие разрешается тем, что реальные данные лежат на низкоразмерных многообразиях - и average-case задача легче worst-case.

Решёточная криптография: пост-квантовая основа

Решётка - дискретная аддитивная подгруппа в R^n: множество всех целочисленных линейных комбинаций n базисных векторов. Задача Shortest Vector Problem (SVP) - найти кратчайший ненулевой вектор в решётке - NP-trudna в худшем случае (Ajtai, 1996). Closest Vector Problem (CVP) - найти ближайший к данной точке вектор решётки - также NP-trudna. Эти проблемы трудны и для квантовых алгоритмов: best known даёт лишь exponential speedup, в отличие от факторизации, которую Шор ломает полиномиально. Именно поэтому NIST в 2024 году стандартизировал Kyber (key encapsulation) и Dilithium (signature), оба основанные на Module-LWE - решёточной задаче.

Learning With Errors (LWE) - центральная задача решёточной криптографии (Регев, 2005). Дано: матрица A, вектор b = As + e mod q, где s - секрет, e - малая ошибка. Восстановить s. Регев доказал worst-case to average-case reduction: если SVP труден в худшем случае, LWE труден в среднем случае. Это уникальное свойство - доказательство трудности на случайных инстансах, опирающееся на трудность в худшем случае. Из LWE строятся: схемы шифрования (Kyber), цифровые подписи (Dilithium), Fully Homomorphic Encryption (BGV, BFV, CKKS), identity-based encryption.

Ключевые идеи

• **Одностронние функции - фундамент криптографии:** OWF сильнее P != NP, требуют average-case hardness.
• **Zero-Knowledge Proofs** позволяют доказать знание решения без его разглашения; zk-SNARK достигают succinctness 200 байт.
• **Learning-hardness ML** имеет глубокую связь с криптографией: necheckno-обучаемые классы порождают OWF, а реальные данные лежат на структурированных многообразиях.
• **Решёточная криптография (LWE/SVP)** даёт пост-квантовую безопасность: best quantum атака subexponential, NIST стандартизировал Kyber и Dilithium в 2024.

Связанные темы

Complexity-theoretic основания пронизывают всю современную криптографию и теоретический ML.

• Параметризованная сложность — Worst-case to average-case reductions в решёточной криптографии используют параметризованные оценки
• P vs NP — OWF - усиление гипотезы P != NP с переносом на average-case

Вопросы для размышления

• NIST стандартизировал решёточные схемы в 2024. Какие риски остаются - что если SVP окажется полиномиально решаема классически (как уже случалось с некоторыми knapsack-based схемами)?
• Hardness of learning в худшем случае не мешает нейросетям обобщать на практике. Какие свойства реальных данных делают average-case задачу обучения резко легче worst-case?
• Zero-Knowledge Proofs позволяют доказать KYC без раскрытия данных. Какие классы регуляторных задач это меняет, и что мешает массовому внедрению ZKP в финтехе?

Связанные уроки

• cplx-07 — NP-полнота - базовая концепция для криптографической стойкости
• crypto-07-computational-complexity — Вычислительная сложность в криптографии - углублённое рассмотрение
• ml-55-ml-system-design — Алгоритмическая сложность ML-пайплайнов - практика из этого урока
• alg-34-approximation — Аппроксимация и криптографические допущения - оба обходят NP-барьер
• alg-01-big-o