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

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

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

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

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

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

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

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

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

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

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

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

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