Постквантовая криптография

Постквантовая криптография — часть криптографии, которая остаётся актуальной и при появлении квантовых компьютеров и квантовых атак. Так как по скорости вычисления традиционных криптографических алгоритмов квантовые компьютеры значительно превосходят классические компьютерные архитектуры, современные криптографические системы становятся потенциально уязвимыми для криптографических атак. Большинство традиционных криптосистем опирается на проблемы факторизации целых чисел или задачи дискретного логарифмирования, которые будут легко разрешимы на достаточно больших квантовых компьютерах, использующих алгоритм Шора. Многие криптографы в настоящее время ведут разработку алгоритмов, независимых от квантовых вычислений, то есть устойчивых к квантовым атакам.

Существуют классические криптосистемы, которые опираются на вычислительно сложные задачи и имеют ряд существенных отличий от указанных выше систем, из-за чего их гораздо сложнее решить. Эти системы независимы от квантовых вычислений, и, следовательно, их считают квантово-устойчивыми (quantum-resistant), или «постквантовыми» криптосистемами.

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

Алгоритмы

Постквантовые криптографические конструкции способны спасти криптографический мир от квантовых атак. Хотя квантовый компьютер и уничтожит большинство традиционных алгоритмов (RSA, DSA, ECDSA), но сверхбыстрыми вычислениями не получится полностью избавиться от криптографии, так как постквантовая криптография, в основном, сосредоточена на пяти различных подходах, решающих проблему квантовых атак.

Криптография, основанная на хеш-функциях

Классическим примером является подпись Меркла с открытым ключом на основе хеш-дерева. Ральф Чарльз Меркл предложил этот алгоритм цифровой подписи в 1979 году как интересную альтернативу цифровым подписям RSA и DSA. Основной недостаток схемы Меркла состоит в том, что для любого открытого ключа на основе хеш-функции существует ограничение на количество подписей, которые могут быть получены из соответствующего набора закрытых ключей. Этот факт и снижал уровень интереса к подписям такого типа, пока не появилась потребность в криптографии, устойчивой к воздействию квантовых компьютеров.

Криптография, основанная на кодах исправления ошибок

Является одним из наиболее перспективных кандидатов на пост-квантовые криптосистемы. Классическим примером является схемы шифрования McEliece и Niederreiter.

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

Классическим примером схем шифрования являются Ring-Learning with Errors или более старые NTRU, GGH и криптосистема Миччанчо.

Криптография, основанная на многомерных квадратичных системах

Одной из самых интересных схем является подпись с открытым ключом Жака Патарина HFE, предложенная им в 1996 году как обобщение предложений Matsumoto и Imai.

Шифрование с секретным ключом

Ярким примером является шифр Rijndael, предложенный в 1998 году, впоследствии переименованный в AES (Advanced Encryption Standard).

Шифрование с использованием суперсингулярной изогении

Основная статья: Протокол обмена ключами с использованием суперсингулярных изогений

Это аналог протокола Диффи-Хеллмана, основанный на блуждании в суперсингулярном изогенном графе, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищённый от прослушивания канал связи. Считается небезопасным: известна эффективная атака на криптосистемы этого типа.

Примеры криптографических атак на RSA

В 1978 году документ, опубликованный разработчиками криптографического алгоритма с открытым ключом RSA (аббревиатура от фамилий Rivest, Shamir и Adleman), упоминал новый алгоритм Ричарда Шреппеля «linear sieve», который факторизовал любой RSA модуль $n$ длины $[\log _{2}n]+1$ бит, используя $2^{(1+o(1))(\log _{2}n)^{1/2}(\log _{2}\log _{2}n)^{1/2}}$ простых операций. Таким образом, для того чтобы этот алгоритм требовал по меньшей мере $2^{b}$ простых операций, необходимо выбирать $n$ длины по крайней мере не меньше чем $(0,5+o(1))b^{2}/{\log _{2}b}$ бит. Так как $0{,}5+o(1)$ означает, что что-то сходится к $0{,}5$ при $b\to \infty$, то для выяснения правильного размера $n$ при конечном $b$ требуется более тщательный анализ скорости «linear sieve».

В 1988 году Джон Поллард предложил новый алгоритм факторизации, который называется Общий метод решета числового поля. Этот алгоритм факторизовал RSA-модуль $n$ размерности $\log _{2}n$ бит, используя $2^{(1,9\dotso +o(1))(\log _{2}n)^{1/3}(\log _{2}\log _{2}n)^{2/3}}$ простых операций. Таким образом, требуется выбирать $n$ длины не меньше чем $(0,016\dotso +o(1))b^{3}/(\log _{2}b)^{2}$ бит, чтобы алгоритму потребовалось как минимум $2^{b}$ простых операций.

С 2008 года самые быстрые алгоритмы факторизации для классических компьютерных архитектур используют по меньшей мере $2^{(const+o(1))(\log _{2}n)^{1/3}(\log _{2}\log _{2}n)^{2/3}}$ простых операций. Были некоторые улучшения в значениях $const$ и в деталях $o(1)$, но не трудно догадаться, что $1/3$ оптимально, и что выбор модуля $n$ длиной примерно равной $b^{3}$ бит, позволит сопротивляться всем возможным атакам на классических компьютерах.

В 1994 году Питер Шор предложил алгоритм, который факторизовал любой RSA-модуль $n$ размерности $b=\log _{2}n$ бит, используя $b^{2+o(1)}$ (точнее $b^{2}\cdot \log(b)\cdot \log(\log(b))$) кубитовых операций на квантовом компьютере размера порядка $2\cdot b^{1+o(1)}$ кубит (и небольшого количества вспомогательных вычислений на классическом компьютере). Пользуясь алгоритмом Шора, необходимо по крайней мере выбирать модуль $n$ битовым размером не меньше чем $2^{(0,5+o(1))b}$ бит, что является слишком большим числом для любого интересующего нас $b$.

Практические применения криптографических конструкций

Примеров алгоритмов, устойчивых к квантовым атакам, крайне мало. Но несмотря на больший уровень криптографической устойчивости, постквантовые алгоритмы неспособны вытеснить современные криптосистемы (RSA, DSA, ECDSA и др.).

Рассмотрим нападения на криптосистему с открытым ключом, а именно на алгоритм шифрования McEliece, который использует двоичные коды Гоппы. Первоначально Роберт Мак-Элис представил документы, в которых коды длиной $n$ взламываются за $2^{(0,5+o(1))n/{\log _{2}n}}$ простых операций. Таким образом, требуется выбирать $n$ не меньше чем $(2+o(1))b\log _{2}b$ бит, чтобы алгоритму потребовалось как минимум $2^{b}$ простых операций. Несколько последующих работ сократили количество операций атаки до $n^{\log _{2}n}=2^{(\log _{2}n)^{2}}$, но $(\log _{2}n)^{2}$ значительно меньше $0{,}5n/{\log _{2}n}$, если $n$ большое. Поэтому улучшенные атаки до сих пор используют $2^{(0,5+o(1))n/{\log _{2}n}}$ простых операций. Что касается квантовых компьютеров, то их использование приведёт лишь к уменьшению константы $0,5$, что совсем незначительно сократит количество операций, необходимых для взлома этого алгоритма.

Если система шифрования McEliece так хорошо защищена, то почему она не приходит на смену RSA? Всё дело в эффективности — в частности, в размере ключа. Открытый ключ McEliece использует примерно ${n^{2}}/4$ ≈ ${b^{2}}(\log _{2}b)^{2}$ бит, в то время как открытому ключу RSA достаточно около $(0{,}016\dots )b^{3}/(\log _{2}b)^{2}$ бит. Если $b\to \infty$, то $b^{2+o(1)}$ бит для McEliece, будет меньше $b^{3+o(1)}$ бит для RSA, но реальные уровни безопасности, такие как $b=128$, позволяют RSA иметь открытый ключ в несколько тысяч бит, в то время как для McEliece размер ключа приближается к миллиону бит.

Конференция PQCrypto

С 2006 года проводится серия конференций, посвящённых постквантовой криптографии.

• PQCrypto 2006. Лёвенский католический университет, Бельгия, с 23 по 26 мая
• PQCrypto 2008. Университет Цинциннати, США, с 17 по 19 октября
• PQCrypto 2010. Дармштадт, Германия, с 25 по 28 мая
• PQCrypto 2011. Тайбэй, Тайвань, с 29 ноября по 2 декабря
• PQCrypto 2013. Лимож, Франция, с 4 по 7 июня
• PQCrypto 2014. Университет Ватерлоо, Канада, с 1 по 3 октября
• PQCrypto 2016. Предварительный план: Фукуока, Япония, февраль 2016

См. также

• Криптография на решётках
• Алгоритм Шора
• Falcon

Ссылки

• PQCrypto, the post-quantum cryptography conference
• Post-Quantum Cryptography (неопр.). — Springer, 2008. — С. 245. — ISBN 978-3-540-88701-0.
• ETSI Квантовая безопасность  (англ.)
• NIST’s Постквантовый криптопроект (англ.)
• PQCrypto Использование и развертывание (англ.)