28-08-2023
Постквантовая криптография — часть криптографии, которая остаётся актуальной и при появлении квантовых компьютеров и квантовых атак. Так как по скорости вычисления традиционных криптографических алгоритмов квантовый компьютеры значительно превосходят классические компьютерные архитектуры, поэтому современные криптографические системы становятся потенциально уязвимыми к криптографическим атакам. Большинство традиционных криптосистем опирается на проблемы факторизации целых чисел или задачи дискретного логарифмирования, которые будут легко разрешимы на достаточно больших квантовых компьютерах, использующих алгоритм Шора. Несмотря на то, что полноценный квантовый компьютер является пока гипотетическим устройством, многие криптографы ведут разработку алгоритмов, независимых от квантовых вычислений, то есть устойчивых к квантовым атакам.
Существуют классические криптосистемы, которые опираются на вычислительно сложные задачи и имеют ряд существенных отличий от систем указанных выше, из за чего их гораздо сложнее решить. Эти системы независимы от квантовых вычислений, и, следовательно, их считают квантово-устойчивыми (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).
В 1978 году документ, опубликованный разработчиками криптографического алгоритма с открытым ключом RSA (аббревиатура от фамилий Rivest, Shamir и Adleman), упоминал новый алгоритм Ричарда Шреппела «linear sieve», который факторизовал любой RSA модуль размерности , используя простых операций. Таким образом, для того чтобы этот алгоритм требовал по меньшей мере простых операций, необходимы выбирать по крайней мере не меньше чем бит. Так как означает, что что-то сходиться к при , то для выяснение правильного размера при конечных , требуется более тщательный анализ скорости «linear sieve».
В 1978 году Джон Поллард предложил новый алгоритм факторизации «number-field sieve»[уточнить]. Этот алгоритм факторизовал RSA модуль[уточнить] размерности , используя простых операций. Таким образом, требуется выбирать не меньше чем бит, чтобы алгоритму потребовалось как минимум простых операций.
Сегодня[когда?], более чем 20 лет спустя[уточнить], самые быстрые алгоритмы факторизации для классических компьютерных архитектур используют по меньшей мере простых операций. Были некоторые улучшения в в значениях и в деталях , но не трудно догадаться, что оптимально, и что выбирая примерно равное бит, позволит сопротивлятся всем возможным атакам на классических компьютерах.
В 1994 году Питер Шор предложил алгоритм, который факторизовал любой RSA модуль[уточнить] размерности , используя простых операций на квантовом компьютере размера . Пользуясь алгоритмом Шора, необходимо по крайней мере выбирать размером не меньше чем бит, что является слишком большим числом для любого интересующего нас .
В настоящее время[уточнить] примеров алгоритмов устойчивых к квантовым атакам крайне мало. Но несмотря на больший уровень криптографической устойчивости, постквантовые алгоритмы не способны вытеснить современные криптосистемы (RSA, DSA, ECDSA и др.).
Рассмотрим для сравнения[стиль!] нападения на криптосистему с открытым ключом, а именно на алгоритм шифрования McEliece, который использует двоичные коды Гоппы. Первоначально Роберт Мак-Элис представил документы, в которых коды длиной взламываются за простых операций. Таким образом, требуется выбирать не меньше чем бит, чтобы алгоритму потребовалось как минимум простых операций. Несколько последующих работ, сократили количество операций атаки до , но значительно меньше , если большое. Поэтому улучшенные атака до сих пор используют простых операций. Что касается квантовых компьютеров, то это их использование приведет только к уменьшению константы , что незначительно сократит количество операций, необходимых для взлома этого алгоритма.
Если система шифрования McEliece так хорошо защищена, то почему она не приходит на смену RSA?[стиль!] Всё дело в эффективности, в частности в размере ключа. Открытый ключ McEliece использует примерно ≈ бит, в то время как открытому ключу RSA достаточно около бит. Если , то бит для McEliece, будет меньше бит для RSA, но реальные уровни безопасности, такие как , позволяют RSA иметь открытый ключ в несколько тысяч бит, в то время как для McEliece размер ключа приближается к миллиону бит.
С 2006 года проводится серия конференций посвященных постквантовой криптографии.
Постквантовая криптография.