Постквантовая криптография: основные подходы и причины использования

Источник: http://praktik.study/lekczii/fizika/kak-ustroena-kvantovaya-fizika-kot-shredingera,-atomyi-i-princzip-neopredelennosti.html
Источник: http://praktik.study/lekczii/fizika/kak-ustroena-kvantovaya-fizika-kot-shredingera,-atomyi-i-princzip-neopredelennosti.html

Доброго времени суток! Из года в год квантовые компьютеры становятся все более производительными и дешевыми в производстве – например, Zuchongzi использует 56 кубита и способен решать задачи, предполагающие возможность квантового ускорения, за несколько часов, в то время как классические суперкомпьютеры требуют нескольких десятков тысяч лет. На данный момент обычному пользователю даже доступна работа на реальном квантовом компьютере IBM, пусть и с ограничением в несколько кубит. Большинство современных криптосистем основаны на сложности факторизации целых чисел и дискретного логарифмирования классическими алгоритмами, но данные задачи легко решаются с использованием алгоритма Шора. Одни из самых популярных криптографических систем – RSA (факторизация целых чисел), DH (дискретное логарифмирование), и ECDSA (эллиптические кривые над конечными полями) – с приходом достаточно производительных квантовых компьютеров перестанут являться надежным средством шифрования данных. В данной статье мы рассмотрим, каким образом квантовые компьютеры решают задачи, используемые в современных криптографических системах, и какие существуют пост-квантовые криптографические системы. Эта статья подразумевает наличия у читателя базового понимания физических основ квантовых вычислений.

Алгоритм Шора

Квантовый алгоритм Шора позволяет выполнить факторизацию числа M за времяO(log^3 M),используяO(logM) кубитов. При использовании квантового компьютера с несколькими тысячами кубитов становится возможным взлом криптографических систем с открытым ключом (например, RSA, использующий открытый ключ, являющийся произведением двух больших простых чисел). Одним из методов взлома таких систем является как раз разложение открытого ключа на простые множители. Классические алгоритмы для обычных компьютеров позволяют произвести взлом такой системы за времяO(M^{\frac{1}{4}}). Алгоритм Шора же способен произвести взлом не просто за полиномиальное время, а за время, сравнимое со временем умножения простых чисел.

Чтобы не нагружать статью математическими выкладками, я опишу принцип работы этого алгоритма простыми словами, но вы можете ознакомиться с полным описанием на соответствующей странице Википедии.

Принцип работы:

Алгоритм Шора, как и многие другие квантовые алгоритмы, состоит из непосредственно квантовой части и классической части, выполняемой на обычном компьютере. Квантовая часть алгоритма Шора заключается в поиске периода некой функции, который выполняется с помощью квантового преобразования Фурье (QFT). Суть его работы покажем на аналогии. Представим, что есть человек, живущий не 24-часовой день, а, например, 26-часовой. Нам нужно определить, сколько именно часов в сутках у этого человека. В его спальне есть большое количество настенных часов, каждые из которых делают полный оборот за определенное количество времени (одни за 15 за, другие за 17 и так далее, для простоты будем считать, что минутной стрелки нет). Под каждыми часами есть лист, в середине которого прикреплена канцелярская кнопка.

Источник: https://www.quora.com/How-does-Shors-algorithm-work-in-laymans-terms

Источник: https://www.quora.com/How-does-Shors-algorithm-work-in-laymans-terms

Каждое утро человек встает и переставляет эту кнопку на один сантиметр в направлении стрелки соответствующих часов. Спустя достаточное количество времени мы можем понять, сколько именно часов в сутках у этого человека – на часах, делающих полный оборот за 26 часов, кнопка будет смещена на значительное расстояние от центра, так как каждое утро стрелка этих часов указывает в одном направлении, все же кнопки под остальными часами будут находиться в окрестности центра листа. Таким образом, мы узнали период функции пробуждения этого человека. QFT работает аналогичным образом и может быть эффективно применено на квантовом компьютере, так как он позволяет иметь несколько кубитов (“настенных часов” в рамках описанного выше эксперимента) в состоянии суперпозиции и производить операции над ними одновременно. Амплитуда|1\rangle состояний кубитов, соответствующих искомому периоду, будет расти ввиду интерференции, остальных же сохраняться около нуля (так как изначально все кубиты выставляются в нулевое булево состояние|0\rangle.

Теперь перейдем к классической части алгоритма Шора. Допустим, мы хотим факторизовать числоN. Для этого мы берем случайное числоaи ищем период\omegaфункции f(x) = a^{x}modN.В результате получим, что наибольшим делителемNбудет число a^{\frac{\omega}{2}} - 1

Стоит заметить, что не всегда случайный выбор числаaприводит к получению делителейN.В таком случаеaвыбирается еще раз, и с большой долей вероятности делительNбудет найден после проверки небольшого количества значенийa.

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

Преимуществами квантовых вычислений не позволят воспользоваться постквантовые алгоритмы – они используют в своей основе задачи, которые сложно решить и обычным, и квантовым компьютерам. Не стоит путать постквантовую и квантовую криптографию – вторая пользуется законами квантовой механики для отправки сообщений, и взломать квантовые системы невозможно. В постквантовой криптографии выделяется 5 различных подходов, исключающих возможность квантовых атак:

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

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

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

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

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

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

Рассмотрим наиболее перспективные из них. Часть подходов рассматривать не будем в силу их сложности для понимания.

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

Классическим примером такого подходя является подпись Меркла – алгоритм многоразовой цифровой подписи, основанный на использовании дерева Меркла, и любой одноразовой подписи, основанной на криптостойкой хеш-функции.

Принцип работы алгоритма состоит из 3 шагов:

  1. Генерируются массивы секретных ключейXи публичныхY.Пары(X_{i}; Y_{i})используются как пары открытый-закрытый ключ для одноразовой подписи. Для генерацииYиспользуется дерево Меркла: для каждогоY_{i}с использованием криптостойкой хэш-функцииHвычисляетсяH(Y_{i})– нулевой слой дереваa_{0}.Каждый следующий слой вычисляется какH(a_{i, 2n} || a_{i, 2n+1})(где||– конкатенация) до того момента, пока в слое не останется один ключ, который называется открытым и обозначается pub\_key

  2. Для генерации подписи выбирается пара ключей (X_i;Y_i). Для сообщенияdвычисляется одноразовая подписьb, а также вычисляется путь отY_iдо корня дерева. В подпись входит верификационный ключ Y_i, подписьbи путь до корня дерева

  3. Проверка подписи производится в 2 этапа: сначала получатель проверяет соответствие подписиbсообщениюd. Если проверка пройдена, строится путьH(Y_i)до корня дерева. При совпадении полученного корня дерева сpub\_keyпроверка подписи считается успешной

    Источник: https://ru.wikipedia.org/wiki/Подпись_Меркла

    Источник: https://ru.wikipedia.org/wiki/Подпись_Меркла

В отличие от алгоритмов наподобие RSA, подпись Меркла является постквантовой, так как опирается на стойкость криптографической хеш-функцииHи одноразовой подписи. Существенным недостатком данного алгоритма и схожих, основанных на хеш-функциях, является ограниченное количество подписей, используемых один раз для каждого сообщения, что препятствует массовому использованию такого подхода. Однако уже существуют методы создания аналогичным способом многоразовых подписей.

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

Одним из примеров таких систем является McEliece – криптосистема с открытыми ключами, основанная на сложности декодирования полных линейных кодов и использующая в процессе шифрования элемент случайности. В этой системе всеми пользователями совместно используются параметры безопасности n, k, t. На данный момент предложено использование следующего набора параметров: n = 2048, k = 1751, t = 27, при этом размер открытого ключа достигает 520.047 бит. Для устойчивости против квантовых атак предлагается использовать n = 6960, k = 5413, t = 119, размер открытого ключа в этом случае достигает 8.373.911 бит. Главными недостатками систем наподобие McEliece являются большой размер открытого ключа и значительное увеличение длины зашифрованного сообщения в сравнении с исходным. Однако такой подход в постквантовой криптографии считается одним из наиболее перспективных ввиду отсутствия серьезных недостатков (вроде ограниченного количества подписей) и деактулизации проблемы размеров передаваемых сообщений на фоне увеличивающихся скоростей передачи данных.

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

Наиболее популярным примером такого подходя является стандарт AES (англ. Advanced Encryption Standard) – симметричный алгоритм блочного шифрования, используемый правительством США как достаточно надежный для защиты информации, являющейся государственной тайной.

Принцип работы:

Сообщения при использовании AES разбиваются на блоки по 128 бит, ключ при этом может быть размером в 128, 192 или 256 бит. В 128-битовый блок вмещается 16 байт, запишем в него сообщение “котики очень милые”. Последние два символа будут переданы в следующем блоке, мы рассмотрим только первый.

Далее берется ключ и с помощью расписания ключей AES генерируется набор раундовых ключей (9 для 128-битового ключа). Допустим, начальный ключ был следующим:

К каждому байту блока с помощью XOR прибавляется начальный ключ. Допустим, результат будет следующим:

h3

jd

zu

7s

s8

7d

26

2n

dj

4b

9d

9c

74

el

2h

hg

Далее производится 9 итераций, на каждой из которых выполняются следующие шаги:

  • Генерируется таблица замен, по которой происходит замена байтов (например, h3->jb, s8->9f и так далее)

    jb

    n3

    kf

    n2

    9f

    jj

    1h

    js

    74

    wh

    0d

    18

    hs

    17

    d6

    px

  • Строки циклически сдвигаются на 1, 2 или 3 шага

    jb

    n3

    kf

    n2

    jj

    1h

    js

    9f

    0d

    18

    74

    wh

    px

    hs

    17

    d6

  • К каждому столбцу применяется определенная математическая операция (column mixing)

    ls

    j4

    2n

    ma

    83

    28

    ke

    9f

    9w

    xm

    3l

    m4

    5b

    a9

    cj

    ps

  • Прибавляется следующий раундовый ключ

Данные действия повторяются 9 раз для 128-битного ключа, 11 раз для 192-битного и 13 раз для 256-битного + 1 раунд. Дополнительный раунд не включает в себя преобразование столбцов как невыгодную операцию, не повышающую надежность шифра. После этого вместо исходного блока “котики очень мил” мы получаем что-то вроде “ ok23b8a0i3j 293uivnfqf98vs87a”.

Каждый из этих шагов необходим: замена байтов – нелинейное преобразование, уменьшающее взаимную информацию исходного и зашифрованного сообщений, а сдвиг строк и применение преобразования к столбцам осуществляет диффузию. Количество раундов было выбрано как компромисс между надежностью и скоростью шифрования для текущего уровня развития технологий.

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

Заключение

На данный момент стоимость создания квантовых сетей даже на 100 пользователей исчисляется миллионами долларов, и общедоступный квантовый интернет еще является туманным будущим. Однако уже в ближайшие несколько лет вычислительные мощности квантовых компьютеров могут достичь уровня, достаточного для создания угрозы современным криптосистемам, и в продаже могут появиться устройства, доступные широкой публике. Поэтому стоит уже сейчас изучать и внедрять постквантовые алгоритмы шифрования данных в повседневную жизнь – в 2017 году Национальным институтом стандартов и технологий США был начат конкурс NIST, призванный стандартизировать набор квантово-устойчивых криптографических схем, в настоящий момент он находится на третьем раунде. Из-за кардинальных различий подходов в постквантовой криптографии прямое сравнение алгоритмов зачастую невозможно, поэтому деятельность NIST направлена на увеличение производительности представленных алгоритмов и получение большей уверенности в их защищенности, победитель же будет выбран на основе совместного анализа NIST и криптографического сообщества. Экспертами NIST из 69 алгоритмов-кандидатов уже выбраны 7 основных и 8 альтернативных (среди них – McEliece, Rainbow, основанный на многомерной криптографии и отличающийся малым размером подписей всего в несколько сотен бит, и NTRU Prime, основанный на решетках), и уже к 2022 году процесс стандартизации может завершиться.

Источники:

  1. https://spectrum.ieee.org/quantum-computing-china

  2. https://arxiv.org/abs/2109.03494

  3. https://quantum-computing.ibm.com

  4. https://en.wikipedia.org/wiki/Shor%27s_algorithm

  5. What is AES encryption and how does it work?

  6. What is the Diffie–Hellman key exchange and how does it work?

  7. https://www.quora.com/How-does-Shors-algorithm-work-in-laymans-terms

  8. https://en.wikipedia.org/wiki/Post-quantum_cryptography

Подробно

Теория кодирования всегда имела тесную взаимосвязь с криптографией, поэтому неудивительно, что наиболее известная криптографическая система на основе кодов, исправляющих ошибки — система McEliece — появилась в 1978 году, став одной из первых систем с открытым ключом. Значительно уступая по эффективности системе RSA, она не получила такого же широкого распространения. Однако в последнее время, после активизации исследований в области квантовых вычислений и публикации алгоритма Шора, эффективно взламывающего систему RSA на квантовом компьютере, способность системы McEliece противостоять квантовым атакам вновь привлекла внимание исследователей.

Система McEliece и подобные ей (система Нидеррайтера) могут быть реализованы с помощью различных классов кодов. В этой области хорошо известны результаты, полученные отечественной алгебраической школой — так, известный российский исследователь В.М. Сидельников показал нестойкость системы McEliece для некоторых классов кодов. В то же время известно, что применение кодов Гоппы позволяет получить стойкий и эффективный вариант этой системы. При анализе любой атаки на систему McEliece обычно отмечают насколько она применима для кодов Гоппы. В частности, система McEliece на кодах Гоппы — самый широко изученный алгоритм из числа участников конкурса NIST. Это значит, что вряд ли появится новая атака, которая существенно снизит стойкость схемы, в отличие от других классов алгоритмов.

Основанные на теории кодирования криптографические системы, как правило, используют простые двоичные операции и могут быть легко реализованы на программном и аппаратном уровне. В то же время они требуют больших объемов памяти для хранения ключей, представленных как проверочные матрицы линейных кодов большой размерности.

Интересной и актуальной задачей является создание эффективной схемы подписи на основе задач теории кодирования.

In cryptography, post-quantum cryptography (PQC) (sometimes referred to as quantum-proof, quantum-safe or quantum-resistant) refers to cryptographic algorithms (usually public-key algorithms) that are thought to be secure against a cryptanalytic attack by a quantum computer. The problem with currently popular algorithms is that their security relies on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems could be easily solved on a sufficiently powerful quantum computer running Shor’s algorithm [1][2] or even faster and less demanding (in terms of number of cubits required) alternatives. [3]

Even though current quantum computers lack processing power to break any real cryptographic algorithm,[4] many cryptographers are designing new algorithms to prepare for a time when quantum computing becomes a threat. This work has gained greater attention from academics and industry through the PQCrypto conference series since 2006 and more recently by several workshops on Quantum Safe Cryptography hosted by the European Telecommunications Standards Institute (ETSI) and the Institute for Quantum Computing.[5][6][7] The rumoured existence of widespread harvest now, decrypt later programs has also been seen as a motivation for the early introduction of post-quantum algorithms, as data recorded now may still remain sensitive many years into the future.[8][9]

In contrast to the threat quantum computing poses to current public-key algorithms, most current symmetric cryptographic algorithms and hash functions are considered to be relatively secure against attacks by quantum computers.[2][10] While the quantum Grover’s algorithm does speed up attacks against symmetric ciphers, doubling the key size can effectively block these attacks.[11] Thus post-quantum symmetric cryptography does not need to differ significantly from current symmetric cryptography.

Algorithms[edit]

Currently post-quantum cryptography research is mostly focused on six different approaches:[2][6]

Lattice-based cryptography[edit]

This approach includes cryptographic systems such as learning with errors, ring learning with errors (ring-LWE),[12][13][14] the ring learning with errors key exchange and the ring learning with errors signature, the older NTRU or GGH encryption schemes, and the newer NTRU signature and BLISS signatures.[15] Some of these schemes like NTRU encryption have been studied for many years without anyone finding a feasible attack. Others like the ring-LWE algorithms have proofs that their security reduces to a worst-case problem.[16] The Post Quantum Cryptography Study Group sponsored by the European Commission suggested that the Stehle–Steinfeld variant of NTRU be studied for standardization rather than the NTRU algorithm.[17][18] At that time, NTRU was still patented. Studies have indicated that NTRU may have more secure properties than other lattice based algorithms.[19]

Multivariate cryptography[edit]

This includes cryptographic systems such as the Rainbow (Unbalanced Oil and Vinegar) scheme which is based on the difficulty of solving systems of multivariate equations. Various attempts to build secure multivariate equation encryption schemes have failed. However, multivariate signature schemes like Rainbow could provide the basis for a quantum secure digital signature.[20] There is a patent on the Rainbow Signature Scheme.

Hash-based cryptography[edit]

This includes cryptographic systems such as Lamport signatures, the Merkle signature scheme, the XMSS,[21] the SPHINCS,[22] and the WOTS schemes. Hash based digital signatures were invented in the late 1970s by Ralph Merkle and have been studied ever since as an interesting alternative to number-theoretic digital signatures like RSA and DSA. Their primary drawback is that for any hash-based public key, there is a limit on the number of signatures that can be signed using the corresponding set of private keys. This fact had reduced interest in these signatures until interest was revived due to the desire for cryptography that was resistant to attack by quantum computers. There appear to be no patents on the Merkle signature scheme[citation needed] and there exist many non-patented hash functions that could be used with these schemes. The stateful hash-based signature scheme XMSS developed by a team of researchers under the direction of Johannes Buchmann is described in RFC 8391.[23]
Note that all the above schemes are one-time or bounded-time signatures, Moni Naor and Moti Yung invented UOWHF hashing in 1989 and designed a signature based on hashing (the Naor-Yung scheme)[24] which can be unlimited-time in use (the first such signature that does not require trapdoor properties).

Code-based cryptography[edit]

This includes cryptographic systems which rely on error-correcting codes, such as the McEliece and Niederreiter encryption algorithms and the related Courtois, Finiasz and Sendrier Signature scheme. The original McEliece signature using random Goppa codes has withstood scrutiny for over 40 years. However, many variants of the McEliece scheme, which seek to introduce more structure into the code used in order to reduce the size of the keys, have been shown to be insecure.[25] The Post Quantum Cryptography Study Group sponsored by the European Commission has recommended the McEliece public key encryption system as a candidate for long term protection against attacks by quantum computers.[17]

Isogeny-based cryptography[edit]

These cryptographic systems rely on the properties of isogeny graphs of elliptic curves (and higher-dimensional abelian varieties) over finite fields, in particular supersingular isogeny graphs, to create cryptographic systems. Among the more well-known representatives of this field are the Diffie-Hellman-like key exchange CSIDH which can serve as a straightforward quantum-resistant replacement for the Diffie-Hellman and elliptic curve Diffie–Hellman key-exchange methods that are in widespread use today,[26] and the signature scheme SQISign which is based on the categorical equivalence between supersingular elliptic curves and maximal orders in particular types of quaternion algebras.[27] Another widely noticed construction, SIDH/SIKE, was spectacularly broken in 2022.[28] The attack is however specific to the SIDH/SIKE family of schemes and does not generalize to other isogeny-based constructions.[29]

Symmetric key quantum resistance[edit]

Provided one uses sufficiently large key sizes, the symmetric key cryptographic systems like AES and SNOW 3G are already resistant to attack by a quantum computer.[30] Further, key management systems and protocols that use symmetric key cryptography instead of public key cryptography like Kerberos and the 3GPP Mobile Network Authentication Structure are also inherently secure against attack by a quantum computer. Given its widespread deployment in the world already, some researchers recommend expanded use of Kerberos-like symmetric key management as an efficient way to get post quantum cryptography today.[31]

Security reductions[edit]

In cryptography research, it is desirable to prove the equivalence of a cryptographic algorithm and a known hard mathematical problem. These proofs are often called “security reductions”, and are used to demonstrate the difficulty of cracking the encryption algorithm. In other words, the security of a given cryptographic algorithm is reduced to the security of a known hard problem. Researchers are actively looking for security reductions in the prospects for post quantum cryptography. Current results are given here:

Lattice-based cryptography – Ring-LWE Signature[edit]

In some versions of Ring-LWE there is a security reduction to the shortest-vector problem (SVP) in a lattice as a lower bound on the security. The SVP is known to be NP-hard.[32] Specific ring-LWE systems that have provable security reductions include a variant of Lyubashevsky’s ring-LWE signatures defined in a paper by Güneysu, Lyubashevsky, and Pöppelmann.[13] The GLYPH signature scheme is a variant of the Güneysu, Lyubashevsky, and Pöppelmann (GLP) signature which takes into account research results that have come after the publication of the GLP signature in 2012. Another Ring-LWE signature is Ring-TESLA.[33] There also exists a “derandomized variant” of LWE, called Learning with Rounding (LWR), which yields ” improved speedup (by eliminating sampling small errors from a Gaussian-like distribution with deterministic errors) and bandwidth.”[34] While LWE utilizes the addition of a small error to conceal the lower bits, LWR utilizes rounding for the same purpose.

Lattice-based cryptography – NTRU, BLISS[edit]

The security of the NTRU encryption scheme and the BLISS[15] signature is believed to be related to, but not provably reducible to, the Closest Vector Problem (CVP) in a Lattice. The CVP is known to be NP-hard. The Post Quantum Cryptography Study Group sponsored by the European Commission suggested that the Stehle–Steinfeld variant of NTRU which does have a security reduction be studied for long term use instead of the original NTRU algorithm.[17]

Multivariate cryptography – Unbalanced Oil and Vinegar[edit]

Unbalanced Oil and Vinegar signature schemes are asymmetric cryptographic primitives based on multivariate polynomials over a finite field \mathbb {F} . Bulygin, Petzoldt and Buchmann have shown a reduction of generic multivariate quadratic UOV systems to the NP-Hard Multivariate Quadratic Equation Solving problem.[35]

Hash-based cryptography – Merkle signature scheme[edit]

In 2005, Luis Garcia proved that there was a security reduction of Merkle Hash Tree signatures to the security of the underlying hash function. Garcia showed in his paper that if computationally one-way hash functions exist then the Merkle Hash Tree signature is provably secure.[36]

Therefore, if one used a hash function with a provable reduction of security to a known hard problem one would have a provable security reduction of the Merkle tree signature to that known hard problem.[37]

The Post Quantum Cryptography Study Group sponsored by the European Commission has recommended use of Merkle signature scheme for long term security protection against quantum computers.[17]

Code-based cryptography – McEliece[edit]

The McEliece Encryption System has a security reduction to the Syndrome Decoding Problem (SDP). The SDP is known to be NP-hard[38] The Post Quantum Cryptography Study Group sponsored by the European Commission has recommended the use of this cryptography for long term protection against attack by a quantum computer.[17]

Code-based cryptography – RLCE[edit]

In 2016, Wang proposed a random linear code encryption scheme RLCE[39] which is based on McEliece schemes. RLCE scheme can be constructed using any linear code such as Reed-Solomon code by inserting random columns in the underlying linear code generator matrix.

Supersingular elliptic curve isogeny cryptography[edit]

Security is related to the problem of constructing an isogeny between two supersingular curves with the same number of points. The most recent investigation of the difficulty of this problem is by Delfs and Galbraith indicates that this problem is as hard as the inventors of the key exchange suggest that it is.[40] There is no security reduction to a known NP-hard problem.

Comparison[edit]

One common characteristic of many post-quantum cryptography algorithms is that they require larger key sizes than commonly used “pre-quantum” public key algorithms. There are often tradeoffs to be made in key size, computational efficiency and ciphertext or signature size. The table lists some values for different schemes at a 128 bit post-quantum security level.

Algorithm Type Public Key Private Key Signature
NTRU Encrypt[41] Lattice 766.25 B 842.875 B
Streamlined NTRU Prime[citation needed] Lattice 154 B
Rainbow[42] Multivariate 124 KB 95 KB
SPHINCS[22] Hash Signature 1 KB 1 KB 41 KB
SPHINCS+[43] Hash Signature 32 B 64 B 8 KB
BLISS-II Lattice 7 KB 2 KB 5 KB
GLP-Variant GLYPH Signature[13][44] Ring-LWE 2 KB 0.4 KB 1.8 KB
NewHope[45] Ring-LWE 2 KB 2 KB
Goppa-based McEliece[17] Code-based 1 MB 11.5 KB
Random Linear Code based encryption[46] RLCE 115 KB 3 KB
Quasi-cyclic MDPC-based McEliece[47] Code-based 1,232 B 2,464 B
SIDH[48] Isogeny 564 B 48 B
SIDH (compressed keys)[49] Isogeny 330 B 48 B
3072-bit Discrete Log not PQC 384 B 32 B 96 B
256-bit Elliptic Curve not PQC 32 B 32 B 65 B

A practical consideration on a choice among post-quantum cryptographic algorithms is the effort required to send public keys over the internet. From this point of view, the Ring-LWE, NTRU, and SIDH algorithms provide key sizes conveniently under 1KB, hash-signature public keys come in under 5KB, and MDPC-based McEliece takes about 1KB. On the other hand, Rainbow schemes require about 125KB and Goppa-based McEliece requires a nearly 1MB key.

Lattice-based cryptography – LWE key exchange and Ring-LWE key exchange[edit]

The fundamental idea of using LWE and Ring LWE for key exchange was proposed and filed at the University of Cincinnati in 2011 by Jintai Ding. The basic idea comes from the associativity of matrix multiplications, and the errors are used to provide the security. The paper[50] appeared in 2012 after a provisional patent application was filed in 2012.

In 2014, Peikert[51] presented a key transport scheme following the same basic idea of Ding’s, where the new idea of sending additional 1 bit signal for rounding in Ding’s construction is also utilized. For somewhat greater than 128 bits of security, Singh presents a set of parameters which have 6956-bit public keys for the Peikert’s scheme.[52] The corresponding private key would be roughly 14,000 bits.

In 2015, an authenticated key exchange with provable forward security following the same basic idea of Ding’s was presented at Eurocrypt 2015,[53] which is an extension of the HMQV[54] construction in Crypto2005. The parameters for different security levels from 80 bits to 350 bits, along with the corresponding key sizes are provided in the paper.[53]

Lattice-based cryptography – NTRU encryption[edit]

For 128 bits of security in NTRU, Hirschhorn, Hoffstein, Howgrave-Graham and Whyte, recommend using a public key represented as a degree 613 polynomial with coefficients {\bmod {\left(2^{10}\right)}}. This results in a public key of 6130 bits. The corresponding private key would be 6743 bits.[41]

Multivariate cryptography – Rainbow signature[edit]

For 128 bits of security and the smallest signature size in a Rainbow multivariate quadratic equation signature scheme, Petzoldt, Bulygin and Buchmann, recommend using equations in \mathbb {F} _{31} with a public key size of just over 991,000 bits, a private key of just over 740,000 bits and digital signatures which are 424 bits in length.[42]

Hash-based cryptography – Merkle signature scheme[edit]

In order to get 128 bits of security for hash based signatures to sign 1 million messages using the fractal Merkle tree method of Naor Shenhav and Wool the public and private key sizes are roughly 36,000 bits in length.[55]

Code-based cryptography – McEliece[edit]

For 128 bits of security in a McEliece scheme, The European Commissions Post Quantum Cryptography Study group recommends using a binary Goppa code of length at least {\displaystyle n=6960} and dimension at least {\displaystyle k=5413}, and capable of correcting {\displaystyle t=119} errors. With these parameters the public key for the McEliece system will be a systematic generator matrix whose non-identity part takes k\times (n-k)=8373911 bits. The corresponding private key, which consists of the code support with {\displaystyle n=6960} elements from {\displaystyle GF(2^{13})} and a generator polynomial of with {\displaystyle t=119} coefficients from {\displaystyle GF(2^{13})}, will be 92,027 bits in length[17]

The group is also investigating the use of Quasi-cyclic MDPC codes of length at least n=2^{16}+6=65542 and dimension at least {\displaystyle k=2^{15}+3=32771}, and capable of correcting {\displaystyle t=264} errors. With these parameters the public key for the McEliece system will be the first row of a systematic generator matrix whose non-identity part takes {\displaystyle k=32771} bits. The private key, a quasi-cyclic parity-check matrix with {\displaystyle d=274} nonzero entries on a column (or twice as much on a row), takes no more than {\displaystyle d\times 16=4384} bits when represented as the coordinates of the nonzero entries on the first row.

Barreto et al. recommend using a binary Goppa code of length at least {\displaystyle n=3307} and dimension at least {\displaystyle k=2515}, and capable of correcting {\displaystyle t=66} errors. With these parameters the public key for the McEliece system will be a systematic generator matrix whose non-identity part takes {\displaystyle k\times (n-k)=1991880} bits.[56] The corresponding private key, which consists of the code support with {\displaystyle n=3307} elements from {\displaystyle GF(2^{12})} and a generator polynomial of with {\displaystyle t=66} coefficients from {\displaystyle GF(2^{12})}, will be 40,476 bits in length.

Supersingular elliptic curve isogeny cryptography[edit]

For 128 bits of security in the supersingular isogeny Diffie-Hellman (SIDH) method, De Feo, Jao and Plut recommend using a supersingular curve modulo a 768-bit prime. If one uses elliptic curve point compression the public key will need to be no more than 8×768 or 6144 bits in length.[57] A March 2016 paper by authors Azarderakhsh, Jao, Kalach, Koziel, and Leonardi showed how to cut the number of bits transmitted in half, which was further improved by authors Costello, Jao, Longa, Naehrig, Renes and Urbanik resulting in a compressed-key version of the SIDH protocol with public keys only 2640 bits in size.[49] This makes the number of bits transmitted roughly equivalent to the non-quantum secure RSA and Diffie-Hellman at the same classical security level.[58]

Symmetric–key-based cryptography[edit]

As a general rule, for 128 bits of security in a symmetric-key-based system, one can safely use key sizes of 256 bits. The best quantum attack against generic symmetric-key systems is an application of Grover’s algorithm, which requires work proportional to the square root of the size of the key space. To transmit an encrypted key to a device that possesses the symmetric key necessary to decrypt that key requires roughly 256 bits as well. It is clear that symmetric-key systems offer the smallest key sizes for post-quantum cryptography.

Forward secrecy[edit]

A public-key system demonstrates a property referred to as perfect forward secrecy when it generates random public keys per session for the purposes of key agreement. This means that the compromise of one message cannot lead to the compromise of others, and also that there is not a single secret value which can lead to the compromise of multiple messages. Security experts recommend using cryptographic algorithms that support forward secrecy over those that do not.[59] The reason for this is that forward secrecy can protect against the compromise of long term private keys associated with public/private key pairs. This is viewed as a means of preventing mass surveillance by intelligence agencies.

Both the Ring-LWE key exchange and supersingular isogeny Diffie-Hellman (SIDH) key exchange can support forward secrecy in one exchange with the other party. Both the Ring-LWE and SIDH can also be used without forward secrecy by creating a variant of the classic ElGamal encryption variant of Diffie-Hellman.

The other algorithms in this article, such as NTRU, do not support forward secrecy as is.

Any authenticated public key encryption system can be used to build a key exchange with forward secrecy.[60]

Open Quantum Safe project[edit]

Open Quantum Safe (OQS) project was started in late 2016 and has the goal of developing and prototyping quantum-resistant cryptography.[61][62] It aims to integrate current post-quantum schemes in one library: liboqs.[63] liboqs is an open source C library for quantum-resistant cryptographic algorithms. It initially focuses on key exchange algorithms but by now includes several signature schemes. It provides a common API suitable for post-quantum key exchange algorithms, and will collect together various implementations. liboqs will also include a test harness and benchmarking routines to compare performance of post-quantum implementations. Furthermore, OQS also provides integration of liboqs into OpenSSL.[64]

As of March 2023, the following key exchange algorithms are supported:[61]

Algorithm Type
CRYSTALS-Kyber Module Learning With Error
Classic McEliece goppa codes
BIKE[65] codes
HQC[66][67] codes
Frodo[68] [69] Learning with errors
NTRU[70] Lattice-based cryptography
CRYSTALS-Dilithium[71][72] Shortest Integer Solution
Falcon Shortest Integer Solution
SPHINCS+ hash based

Older supported versions that have been removed because of the progression of the NIST Post-Quantum Cryptography Standardization Project are:

Algorithm Type
BCNS15[73] Ring learning with errors key exchange
NewHope[74][45] Ring learning with errors key exchange
SIDH[75][76] Supersingular isogeny key exchange
McBits[77] Error-correcting codes

Implementation[edit]

One of the main challenges in post-quantum cryptography is considered to be the implementation of potentially quantum safe algorithms into existing systems. There are tests done, for example by Microsoft Research implementing PICNIC in a PKI using Hardware security modules.[78] Test implementations for Google’s NewHope algorithm have also been done by HSM vendors. In August 2023, Google released a FIDO2 security key implementation of an ECC/Dilithium hybrid signature schema which was done in partnership with ETH Zürich.[79]

Other notable implementations include:

  • bouncycastle[80]
  • liboqs[81]

See also[edit]

  • NIST Post-Quantum Cryptography Standardization
  • Quantum cryptography – cryptography based on quantum mechanics
  • Crypto-shredding – Deleting encryption keys
  • Harvest now, decrypt later

References[edit]

  1. ^ Peter W. Shor (1997). “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM Journal on Computing. 26 (5): 1484–1509. arXiv:quant-ph/9508027. Bibcode:1995quant.ph..8027S. doi:10.1137/S0097539795293172. S2CID 2337707.
  2. ^ a b c Daniel J. Bernstein (2009). “Introduction to post-quantum cryptography” (PDF). Post-Quantum Cryptography.
  3. ^ Anna Kramer (2023). https://www.science.org/content/article/surprising-and-supercool-quantum-algorithm-offers-faster-way-hack-internet-encryption. ;
  4. ^ “New qubit control bodes well for future of quantum computing”. phys.org.
  5. ^ “Cryptographers Take On Quantum Computers”. IEEE Spectrum. 2009-01-01.
  6. ^ a b “Q&A With Post-Quantum Computing Cryptography Researcher Jintai Ding”. IEEE Spectrum. 2008-11-01.
  7. ^ “ETSI Quantum Safe Cryptography Workshop”. ETSI Quantum Safe Cryptography Workshop. ETSI. October 2014. Archived from the original on 17 August 2016. Retrieved 24 February 2015.
  8. ^ Townsend, Kevin (2022-02-16). “Solving the Quantum Decryption ‘Harvest Now, Decrypt Later’ Problem”. SecurityWeek. Retrieved 2023-04-09.
  9. ^ “Quantum-Safe Secure Communications” (PDF). UK National Quantum Technologies Programme. October 2021. Retrieved 2023-04-09.
  10. ^ Daniel J. Bernstein (2009-05-17). “Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?” (PDF).
  11. ^ Daniel J. Bernstein (2010-03-03). “Grover vs. McEliece” (PDF).
  12. ^ Peikert, Chris (2014). “Lattice Cryptography for the Internet” (PDF). IACR. Archived from the original on 12 May 2014. Retrieved 10 May 2014.{{cite web}}: CS1 maint: bot: original URL status unknown (link)
  13. ^ a b c Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). “Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems” (PDF). INRIA. Retrieved 12 May 2014.
  14. ^ Zhang, jiang (2014). “Authenticated Key Exchange from Ideal Lattices” (PDF). iacr.org. IACR. Archived from the original on 7 September 2014. Retrieved 7 September 2014.{{cite web}}: CS1 maint: bot: original URL status unknown (link)
  15. ^ a b Ducas, Léo; Durmus, Alain; Lepoint, Tancrède; Lyubashevsky, Vadim (2013). “Lattice Signatures and Bimodal Gaussians”. Retrieved 2015-04-18.
  16. ^ Lyubashevsky, Vadim; Peikert; Regev (2013). “On Ideal Lattices and Learning with Errors Over Rings” (PDF). IACR. Archived from the original on 31 January 2014. Retrieved 14 May 2013.{{cite web}}: CS1 maint: bot: original URL status unknown (link)
  17. ^ a b c d e f g Augot, Daniel (7 September 2015). “Initial recommendations of long-term secure post-quantum systems” (PDF). PQCRYPTO. Retrieved 13 September 2015.
  18. ^ Stehlé, Damien; Steinfeld, Ron (2013-01-01). “Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices”. Cryptology ePrint Archive.
  19. ^ Easttom, Chuck (2019-02-01). “An Analysis of Leading Lattice-Based Asymmetric Cryptographic Primitives”. 2019 IEEE 9th Annual Computing and Communication Workshop and Conference (CCWC). pp. 0811–0818. doi:10.1109/CCWC.2019.8666459. ISBN 978-1-7281-0554-3. S2CID 77376310.
  20. ^ Ding, Jintai; Schmidt (7 June 2005). “Rainbow, a New Multivariable Polynomial Signature Scheme”. In Ioannidis, John (ed.). Third International Conference, ACNS 2005, New York, NY, USA, June 7–10, 2005. Proceedings. Lecture Notes in Computer Science. Vol. 3531. pp. 64–175. doi:10.1007/11496137_12. ISBN 978-3-540-26223-7. S2CID 6571152.
  21. ^ Buchmann, Johannes; Dahmen, Erik; Hülsing, Andreas (2011). “XMSS – A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions”. Post-Quantum Cryptography. PQCrypto 2011. Lecture Notes in Computer Science. Vol. 7071. pp. 117–129. CiteSeerX 10.1.1.400.6086. doi:10.1007/978-3-642-25405-5_8. ISSN 0302-9743.
  22. ^ a b Bernstein, Daniel J.; Hopwood, Daira; Hülsing, Andreas; Lange, Tanja; Niederhagen, Ruben; Papachristodoulou, Louiza; Schneider, Michael; Schwabe, Peter; Wilcox-O’Hearn, Zooko (2015). Oswald, Elisabeth; Fischlin, Marc (eds.). SPHINCS: practical stateless hash-based signatures. Lecture Notes in Computer Science. Vol. 9056. Springer Berlin Heidelberg. pp. 368–397. CiteSeerX 10.1.1.690.6403. doi:10.1007/978-3-662-46800-5_15. ISBN 9783662467992.
  23. ^ Huelsing, A.; Butin, D.; Gazdag, S.; Rijneveld, J.; Mohaisen, A. (2018). “RFC 8391 – XMSS: eXtended Merkle Signature Scheme”. tools.ietf.org. doi:10.17487/RFC8391.
  24. ^ Moni Naor, Moti Yung: Universal One-Way Hash Functions and their Cryptographic Applications .STOC 1989: 33-43
  25. ^ Overbeck, Raphael; Sendrier (2009). “Code-based cryptography”. In Bernstein, Daniel (ed.). Post-Quantum Cryptography. pp. 95–145. doi:10.1007/978-3-540-88702-7_4. ISBN 978-3-540-88701-0.
  26. ^ Castryck, Wouter; Lange, Tanja; Martindale, Chloe; Panny, Lorenz; Renes, Joost (2018). “CSIDH: An Efficient Post-Quantum Commutative Group Action”. In Peyrin, Thomas; Galbraith, Steven (eds.). Advances in Cryptology – ASIACRYPT 2018. Lecture Notes in Computer Science. Vol. 11274. Cham: Springer International Publishing. pp. 395–427. doi:10.1007/978-3-030-03332-3_15. hdl:1854/LU-8619033. ISBN 978-3-030-03332-3. S2CID 44165584.
  27. ^ De Feo, Luca; Kohel, David; Leroux, Antonin; Petit, Christophe; Wesolowski, Benjamin (2020). “SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies” (PDF). In Moriai, Shiho; Wang, Huaxiong (eds.). Advances in Cryptology – ASIACRYPT 2020. Lecture Notes in Computer Science. Vol. 12491. Cham: Springer International Publishing. pp. 64–93. doi:10.1007/978-3-030-64837-4_3. ISBN 978-3-030-64837-4. S2CID 222265162.
  28. ^ Castryck, Wouter; Decru, Thomas (2023), Hazay, Carmit; Stam, Martijn (eds.), “An Efficient Key Recovery Attack on SIDH”, Advances in Cryptology – EUROCRYPT 2023, Cham: Springer Nature Switzerland, vol. 14008, pp. 423–447, doi:10.1007/978-3-031-30589-4_15, ISBN 978-3-031-30588-7, S2CID 258240788, retrieved 2023-06-21
  29. ^ “Is SIKE broken yet?”. Retrieved 2023-06-23.
  30. ^ Perlner, Ray; Cooper (2009). “Quantum Resistant Public Key Cryptography: A Survey”. NIST. Retrieved 23 Apr 2015.
  31. ^ Campagna, Matt; Hardjono; Pintsov; Romansky; Yu (2013). “Kerberos Revisited Quantum-Safe Authentication” (PDF). ETSI.
  32. ^ Lyubashevsky, Vadim; Peikert; Regev (25 June 2013). “On Ideal Lattices and Learning with Errors Over Rings” (PDF). Springer. Retrieved 19 June 2014.
  33. ^ Akleylek, Sedat; Bindel, Nina; Buchmann, Johannes; Krämer, Juliane; Marson, Giorgia Azzurra (2016). “An Efficient Lattice-Based Signature Scheme with Provably Secure Instantiation”. Cryptology ePrint Archive.
  34. ^ Nejatollahi, Hamid; Dutt, Nikil; Ray, Sandip; Regazzoni, Francesco; Banerjee, Indranil; Cammarota, Rosario (2019-02-27). “Post-Quantum Lattice-Based Cryptography Implementations: A Survey”. ACM Computing Surveys. 51 (6): 1–41. doi:10.1145/3292548. ISSN 0360-0300. S2CID 59337649.
  35. ^ Bulygin, Stanislav; Petzoldt; Buchmann (2010). “Towards Provable Security of the Unbalanced Oil and Vinegar Signature Scheme under Direct Attacks”. Progress in Cryptology – INDOCRYPT 2010. Lecture Notes in Computer Science. Vol. 6498. pp. 17–32. CiteSeerX 10.1.1.294.3105. doi:10.1007/978-3-642-17401-8_3. ISBN 978-3-642-17400-1.
  36. ^ Pereira, Geovandro; Puodzius, Cassius; Barreto, Paulo (2016). “Shorter hash-based signatures”. Journal of Systems and Software. 116: 95–100. doi:10.1016/j.jss.2015.07.007.
  37. ^ Garcia, Luis. “On the security and the efficiency of the Merkle signature scheme” (PDF). Cryptology ePrint Archive. IACR. Retrieved 19 June 2013.
  38. ^ Blaum, Mario; Farrell; Tilborg (31 May 2002). Information, Coding and Mathematics. Springer. ISBN 978-1-4757-3585-7.
  39. ^ Wang, Yongge (2016). “Quantum resistant random linear code based public key encryption scheme RLCE”. Proceedings of Information Theory (ISIT). IEEE ISIT: 2519–2523. arXiv:1512.08454. Bibcode:2015arXiv151208454W.
  40. ^ Delfs, Christina; Galbraith (2013). “Computing isogenies between supersingular elliptic curves over F_p”. arXiv:1310.7789 [math.NT].
  41. ^ a b Hirschborrn, P; Hoffstein; Howgrave-Graham; Whyte. “Choosing NTRUEncrypt Parameters in Light of Combined Lattice Reduction and MITM Approaches” (PDF). NTRU. Archived from the original (PDF) on 30 January 2013. Retrieved 12 May 2014.
  42. ^ a b Petzoldt, Albrecht; Bulygin; Buchmann (2010). “Selecting Parameters for the Rainbow Signature Scheme – Extended Version -” (PDF). Archived from the original on 4 March 2016. Retrieved 12 May 2014.{{cite web}}: CS1 maint: bot: original URL status unknown (link)
  43. ^ “SPHINCS+: Submission to the NIST post-quantum project” (PDF).
  44. ^ Chopra, Arjun (2017). “GLYPH: A New Insantiation of the GLP Digital Signature Scheme”. Cryptology ePrint Archive.
  45. ^ a b Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (2015). “Post-quantum key exchange – a new hope” (PDF). Cryptology ePrint Archive, Report 2015/1092. Retrieved 1 September 2017.
  46. ^ Wang, Yongge (2017). “Revised Quantum Resistant Public Key Encryption Scheme RLCE and IND-CCA2 Security for McEliece Schemes”. Cryptology ePrint Archive.
  47. ^ Misoczki, R.; Tillich, J. P.; Sendrier, N.; Barreto, P. S. L. M. (2013). “MDPC-McEliece: New McEliece variants from Moderate Density Parity-Check codes”. 2013 IEEE International Symposium on Information Theory. pp. 2069–2073. CiteSeerX 10.1.1.259.9109. doi:10.1109/ISIT.2013.6620590. ISBN 978-1-4799-0446-4. S2CID 9485532.
  48. ^ Costello, Craig; Longa, Patrick; Naehrig, Michael (2016). “Efficient Algorithms for Supersingular Isogeny Diffie-Hellman” (PDF). Advances in Cryptology – CRYPTO 2016. Lecture Notes in Computer Science. Vol. 9814. pp. 572–601. doi:10.1007/978-3-662-53018-4_21. ISBN 978-3-662-53017-7.
  49. ^ a b Costello, Craig; Jao; Longa; Naehrig; Renes; Urbanik. “Efficient Compression of SIDH public keys”. Retrieved 8 October 2016.
  50. ^ Lin, Jintai Ding, Xiang Xie, Xiaodong (2012-01-01). “A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem”. Cryptology ePrint Archive.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  51. ^ Peikert, Chris (2014-01-01). “Lattice Cryptography for the Internet”. Cryptology ePrint Archive.
  52. ^ Singh, Vikram (2015). “A Practical Key Exchange for the Internet using Lattice Cryptography”. Retrieved 2015-04-18.
  53. ^ a b Zhang, Jiang; Zhang, Zhenfeng; Ding, Jintai; Snook, Michael; Dagdelen, Özgür (2015-04-26). “Authenticated Key Exchange from Ideal Lattices”. In Oswald, Elisabeth; Fischlin, Marc (eds.). Advances in Cryptology – EUROCRYPT 2015. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 719–751. CiteSeerX 10.1.1.649.1864. doi:10.1007/978-3-662-46803-6_24. ISBN 978-3-662-46802-9.
  54. ^ Krawczyk, Hugo (2005-08-14). “HMQV: A High-Performance Secure Diffie-Hellman Protocol”. In Shoup, Victor (ed.). Advances in Cryptology – CRYPTO 2005. Lecture Notes in Computer Science. Vol. 3621. Springer. pp. 546–566. doi:10.1007/11535218_33. ISBN 978-3-540-28114-6.
  55. ^ Naor, Dalit; Shenhav; Wool (2006). “One-Time Signatures Revisited: Practical Fast Signatures Using Fractal Merkle Tree Traversal” (PDF). IEEE. Retrieved 13 May 2014.
  56. ^ Barreto, Paulo S. L. M.; Biasi, Felipe Piazza; Dahab, Ricardo; López-Hernández, Julio César; Morais, Eduardo M. de; Oliveira, Ana D. Salina de; Pereira, Geovandro C. C. F.; Ricardini, Jefferson E. (2014). Koç, Çetin Kaya (ed.). A Panorama of Post-quantum Cryptography. Springer International Publishing. pp. 387–439. doi:10.1007/978-3-319-10683-0_16. ISBN 978-3-319-10682-3.
  57. ^ De Feo, Luca; Jao; Plut (2011). “Towards Quantum-Resistant Cryptosystems From Supersingular Elliptic Curve Isogenies” (PDF). Archived from the original on 11 February 2014. Retrieved 12 May 2014.{{cite web}}: CS1 maint: bot: original URL status unknown (link)
  58. ^ “Cryptology ePrint Archive: Report 2016/229”. eprint.iacr.org. Retrieved 2016-03-02.
  59. ^ Ristic, Ivan (2013-06-25). “Deploying Forward Secrecy”. SSL Labs. Retrieved 14 June 2014.
  60. ^ “Does NTRU provide Perfect Forward Secrecy?”. crypto.stackexchange.com.
  61. ^ a b “Open Quantum Safe”. openquantumsafe.org.
  62. ^ Stebila, Douglas; Mosca, Michele. “Post-Quantum Key Exchange for the Internet and the Open Quantum Safe Project”. Cryptology ePrint Archive, Report 2016/1017, 2016. Retrieved 9 April 2017.
  63. ^ “liboqs: C library for quantum-resistant cryptographic algorithms”. 26 November 2017 – via GitHub.
  64. ^ “openssl: Fork of OpenSSL that includes quantum-resistant algorithms and ciphersuites based on liboqs”. 9 November 2017 – via GitHub.
  65. ^ “BIKE – Bit Flipping Key Encapsulation”. bikesuite.org. Retrieved 2023-08-21.
  66. ^ “HQC”. pqc-hqc.org. Retrieved 2023-08-21.
  67. ^ “Fast and Efficient Hardware Implementation of HQC” (PDF).
  68. ^ Bos, Joppe; Costello, Craig; Ducas, Léo; Mironov, Ilya; Naehrig, Michael; Nikolaenko, Valeria; Raghunathan, Ananth; Stebila, Douglas (2016-01-01). “Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE”. Cryptology ePrint Archive.
  69. ^ “FrodoKEM”. frodokem.org. Retrieved 2023-08-21.
  70. ^ “NTRUOpenSourceProject/NTRUEncrypt”. GitHub. Retrieved 2017-04-10.
  71. ^ Schwabe, Peter. “Dilithium”. pq-crystals.org. Retrieved 2023-08-19.
  72. ^ “Cryptographic Suite for Algebraic Lattices, Digital Signature: Dilithium” (PDF).
  73. ^ Stebila, Douglas (26 Mar 2018). “liboqs nist-branch algorithm datasheet: kem_newhopenist”. GitHub. Retrieved 27 September 2018.
  74. ^ “Lattice Cryptography Library”. Microsoft Research. 19 Apr 2016. Retrieved 27 September 2018.
  75. ^ “SIDH Library – Microsoft Research”. Microsoft Research. Retrieved 2017-04-10.
  76. ^ Feo, Luca De; Jao, David; Plût, Jérôme (2011-01-01). “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies”. Archived from the original on 2014-05-03.
  77. ^ Bernstein, Daniel J.; Chou, Tung; Schwabe, Peter (2015-01-01). “McBits: fast constant-time code-based cryptography”. Cryptology ePrint Archive.
  78. ^ “Microsoft/Picnic” (PDF). GitHub. Retrieved 2018-06-27.
  79. ^ “Toward Quantum Resilient Security Keys”. Google Online Security Blog. Retrieved 2023-08-19.
  80. ^ “Bouncy Castle Betas”.
  81. ^ “Open Quantum Safe”.

Further reading[edit]

  • Post-Quantum Cryptography. Springer. 2008. p. 245. ISBN 978-3-540-88701-0.
  • Isogenies in a Quantum World
  • On Ideal Lattices and Learning With Errors Over Rings
  • Kerberos Revisited: Quantum-Safe Authentication
  • The picnic signature scheme

External links[edit]

  • PQCrypto, the post-quantum cryptography conference
  • ETSI Quantum Secure Standards Effort
  • NIST’s Post-Quantum crypto Project
  • PQCrypto Usage & Deployment
  • ISO 27001 Certification Cost

О том, что такое постквантовая криптография, от каких киберугроз она может защитить и почему о ней все чаще говорят в мире

Об авторе: Антон Гугля, руководитель QApp — компании-разработчика отечественных решений кибербезопасности на основе постквантовых алгоритмов шифрования.

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

Зачем требуется шифрование

О какой бы криптографии ни заходила речь, окружающие зачастую считают, что это их мало касается. Крупный бизнес — да, а вот нас с вами — едва ли. Конечно, это не так. Покупки в интернет-магазинах, переписки в мессенджерах и социальных сетях, интернет-серфинг по пути на работу — все эти активности неразрывно связаны с шифрованием данных. Простой пример — защищенное соединение https, которое преобразует передаваемые в сети данные в зашифрованный формат и не дает посторонним прямой доступ к конфиденциальной информации.

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

Первый необходим, чтобы зашифровать данные, второй — чтобы расшифровать. Несмотря на то, что оба ключа связаны между собой математической функцией, без закрытого ключа доступ к данным не получить: ни привычные нам персональные компьютеры, ни суперкомпьютеры справиться с этой задачей не смогут из-за недостатка вычислительных мощностей.

Фото:Markus Spiske / Unsplash

Квантовая угроза

Между тем возможность взломать асимметричный шифр существует: алгоритм, способный справиться с этой задачей, еще в 1994 году разработал ученый Питер Шор. Реализовать этот алгоритм позволяет квантовый компьютер. В отличие от обычных устройств, работающих на основе полупроводниковых технологий, мощность квантовых растет экспоненциально. Поэтому их возможности значительно превосходят любые инструменты, которые сегодня используют хакеры.

Современные квантовые компьютеры пока не обладают мощностью достаточной для взлома систем на основе асимметричного шифрования. Но с начала 2000-х такие технологические гиганты, как IBM, Google, Intel ведут разработки по развитию квантовых вычислений, что приближает нас к кибератакам нового типа. По мнению большинства экспертов, первые случаи подобных атак могут быть зафиксированы до 2030 года. Впрочем, аналитики McKinsey предостерегают, что финансовый и государственный секторы, а также страховая индустрия могут столкнуться с ними уже в ближайшие два года.

Это подводит нас к понятию квантовой угрозы — риска, что злоумышленники могут уже сегодня сохранять конфиденциальные данные, зашифрованные асимметричной криптографией, чтобы дешифровать их в будущем при первой появившейся возможности. Неважно каким образом хакеры получат доступ к квантовым устройствам — будет ли это социальный инжиниринг, облачная платформа квантовых вычислений или трудоустройство в компанию-разработчика квантовых компьютеров. Важно лишь то, что все накопленные данные, актуальные на тот момент, будут расшифрованы и приведут к колоссальным потерям. Поэтому защищать их необходимо уже сегодня.

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

Фото:Ren Pengfei / Global Look Press

Постквантовое шифрование

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

В частности, это алгоритмы, основанные на линейных кодах, теории решеток и хеш-функциях. Первый тип (code-based) основан на гипотезе, что декодировать случайный линейный код очень сложно. Первый алгоритм такого типа появился еще в 1978 году — это была система McEliece, одна из первых систем с открытым ключом. В тот момент об атаках с использованием квантового компьютера не было и речи, однако после появления алгоритма Шора, способного легко взломать используемое повсеместно шифрование, криптографы-исследователи вновь заинтересовались алгоритмом McEliece.

Другой тип схем постквантовой криптографии — алгоритмы на основе теории решеток. Такие схемы хорошо изучены и легко применимы на практике, в частности, их использует IBM в своих приложениях безопасности.

В постквантовом шифровании применяется и один из самых популярных криптографических инструментов — хеш-функция. Хеширование — это преобразование произвольного объема данных в уникальный набор символов фиксированной длины, расшифровать который очень сложно. А постквантовые алгоритмы с использованием хеш-функции делают декодирование сообщения невозможным, во всяком случае, всеми известными методами. Хеш-функция может лежать в основе электронной подписи, в частности, эта модель сейчас прорабатывается в России.

Фото:Unsplash

Пора применять

Над интеграцией и пилотированием криптографических алгоритмов в свои продукты уже работают такие гиганты рынка, как Microsoft, Google, Verizon, Thales, Toshiba, Amazon, Cloudflare.

Так, весной 2022 года IBM представила новое поколение мейнфреймов (универсальных высокопроизводительных серверов) z16, которые используют для защиты данных постквантовую криптографию. z16 оснащен ускорителем на базе искусственного интеллекта, что позволяет быстро обрабатывать огромные объемы информации. Это критично, в частности, для финансовых компаний и медицинских организаций, то есть тех, чьи данные обладают долгим циклом жизни. Именно поэтому для их защиты IBM применяет продукты в области постквантового шифрования, построенные на теории решеток.

В то же время южнокорейский мобильный оператор LG Uplus (принадлежит LG Group) выпустил коммерческий сервис для проводной и беспроводной связи, устойчивый к атакам с помощью квантового компьютера. А уже осенью LG Electronics объявила, что будет использовать этот метод защиты для ряда задач, в том числе в технологии V2X (vehicle to everything) — обмена данными между автомобилями и объектами дорожной инфраструктуры.

В октябре 2022 года компания Cloudflare объявила о запуске поддержки постквантовой криптографии для всех веб-сайтов и API, обслуживаемых через ее сеть. По сути это делает доступным квантовое шифрование для 19% мировых веб-ресурсов. Это наглядно демонстрирует, насколько критично к квантовой угрозе относится одна из крупнейших сетевых инфраструктур.

В России работа по пилотированию постквантовых продуктов также идет полным ходом: в июне 2022 года отечественные специалисты подтвердили совместимость постквантового шифрования с российскими процессорами Baikal-M, в октябре — с процессорами «Эльбрус». Первой в стране финансовой организацией, пилотировавшей постквантовые алгоритмы, стал Газпромбанк — в 2022 году он обеспечил квантово-устойчивую защиту host-to-host соединения при проведении финансовых поручений.

Фото:Unsplash

Финальный штрих

На сегодняшний день постквантовая криптография находится на стадии стандартизации. В США этот процесс курирует Национальный институт стандартов и технологий (NIST). На конкурсной основе эксперты выбирают наиболее квантово-устойчивые алгоритмы, которые лягут в основу стандартов постквантового шифрования. В 2022 году институт выбрал четыре алгоритма — они станут частью постквантового криптографического стандарта, окончательная доработка которого ожидается примерно через два года. В то же время Белый дом обязал госструктуры уже к маю 2023 года совершить всецелую подготовку к переходу на постквантовые алгоритмы.

В России разработкой стандартов постквантовых алгоритмов занялись в 2019 году под руководством Технического комитета 26, куда входят представители государственных и коммерческих организаций. Ожидается, что отечественные стандарты будут утверждены к 2024–2025 году. Рынок вступил в фазу активного формирования, а значит уже в ближайшие один-два года число пилотных проектов мирового уровня вырастет в разы.

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией

Материал из энциклопедии Руниверсалис

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

С 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

См. также

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

Примечания

  1. Peter Shor (1995-08-30), Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, arΧiv:quant-ph/9508027.
  2. 2,0 2,1 2,2 2,3 2,4 Daniel J. Bernstein. Introduction to post-quantum cryptography (неопр.) // (Introductory chapter to book “Post-quantum cryptography”). — 2009.
  3. Q&A With Post-Quantum Computing Cryptography Researcher Jintai Ding, IEEE Spectrum (1 ноября 2008). Архивировано 8 октября 2015 года. Дата обращения 26 ноября 2014.
  4. рус. обучение с ошибками
  5. Peikert, Chris Lattice Cryptography for the Internet. IACR (2014). Дата обращения: 10 мая 2014. Архивировано 12 мая 2014 года.
  6. Guneysu, Tim Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems. INRIA (2012). Дата обращения: 12 мая 2014. Архивировано 18 мая 2014 года.
  7. Zhang, jiang Authenticated Key Exchange from Ideal Lattices. iacr.org. IACR (2014). Дата обращения: 7 сентября 2014. Архивировано 7 сентября 2014 года.
  8. Протокол Диффи-Хеллмана с использованием суперсингулярной изогении.
  9. http://crypto.rsuh.ru/papers/bogdanov-kizhvatov-quantum.pdf Архивная копия от 15 декабря 2017 на Wayback Machine стр 9
  10. официальный сайт PQCrypto 2006. Дата обращения: 19 ноября 2014. Архивировано 26 октября 2014 года.
  11. официальный сайт PQCrypto 2008 (недоступная ссылка). Дата обращения: 19 ноября 2014. Архивировано 19 октября 2014 года.
  12. официальный сайт PQCrypto 2010. Дата обращения: 19 ноября 2014. Архивировано 9 октября 2014 года.
  13. официальный сайт PQCrypto 2011. Дата обращения: 19 ноября 2014. Архивировано 27 декабря 2014 года.
  14. официальный сайт PQCrypto 2013. Дата обращения: 19 ноября 2014. Архивировано 23 декабря 2014 года.
  15. официальный сайт PQCrypto 2014 (недоступная ссылка). Дата обращения: 19 ноября 2014. Архивировано 26 октября 2014 года.

Ссылки

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *