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

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

Существуют классические криптосистемы , которые опираются на вычислительно сложные задачи и имеют ряд существенных отличий от указанных выше систем, из-за чего их гораздо сложнее решить. Эти системы независимы от квантовых вычислений, и, следовательно, их считают квантово-устойчивыми (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$ $n$ длины $[\log _{2}n]+1$ $[\log _{2}n]+1$ бит, используя $2^{(1+o(1))(\log _{2}n)^{1/2}(\log _{2}\log _{2}n)^{1/2}}$ $2^{(1+o(1))(\log _{2}n)^{1/2}(\log _{2}\log _{2}n)^{1/2}}$ простых операций. Таким образом, для того чтобы этот алгоритм требовал по меньшей мере $2^{b}$ $2^{b}$ простых операций, необходимо выбирать $n$ $n$ длины по крайней мере не меньше чем $(0,5+o(1))b^{2}/{\log _{2}b}$ $(0,5+o(1))b^{2}/{\log _{2}b}$ бит. Так как $0{,}5+o(1)$ $0{,}5+o(1)$ означает, что что-то сходится к $0{,}5$ $0{,}5$ при $b\to \infty$ $b\to \infty$ , то для выяснения правильного размера $n$ $n$ при конечном $b$ $b$ требуется более тщательный анализ скорости «linear sieve».

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

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

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

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

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

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

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

См. также

Примечания

Peter Shor (1995-08-30), Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, arΧiv : .
↑ . (неопр.) // (Introductory chapter to book "Post-quantum cryptography"). — 2009. 20 сентября 2009 года.
, IEEE Spectrum (1 ноября 2008). 8 октября 2015 года. Дата обращения: 26 ноября 2014.
рус. обучение с ошибками
Peikert, Chris (неопр.) . IACR (2014). Дата обращения: 10 мая 2014. 12 мая 2014 года.
Guneysu, Tim (неопр.) . INRIA (2012). Дата обращения: 12 мая 2014. 18 мая 2014 года.
Zhang, jiang (неопр.) . iacr.org . IACR (2014). Дата обращения: 7 сентября 2014. 7 сентября 2014 года.
от 15 декабря 2017 на Wayback Machine стр 9
(неопр.) . Дата обращения: 19 ноября 2014. 26 октября 2014 года.
(неопр.) . Дата обращения: 19 ноября 2014. Архивировано из 19 октября 2014 года.
(неопр.) . Дата обращения: 19 ноября 2014. 9 октября 2014 года.
(неопр.) . Дата обращения: 19 ноября 2014. 27 декабря 2014 года.
(неопр.) . Дата обращения: 19 ноября 2014. 23 декабря 2014 года.
(неопр.) . Дата обращения: 19 ноября 2014. Архивировано из 26 октября 2014 года.