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

Существуют классические криптосистемы , которые опираются на вычислительно сложные задачи и имеют ряд существенных отличий от указанных выше систем, из-за чего их гораздо сложнее решить. Эти системы независимы от квантовых вычислений, и, следовательно, их считают квантово-устойчивыми (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 модуль ${\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}$ .

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

Примеров алгоритмов, устойчивых к квантовым атакам, крайне мало. Но несмотря на больший уровень криптографической устойчивости, постквантовые алгоритмы неспособны вытеснить современные криптосистемы (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 размер ключа приближается к миллиону бит.

Конференция 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

Примечания

Ссылки

• (неопр.) . — Springer, 2008. — С. 245. — ISBN 978-3-540-88701-0 .
• (англ.)
• (англ.)
• (англ.)