Введение
В 1994 году ученый-компьютерщик Питер Шор открытый что, если квантовые компьютеры когда-либо будут изобретены, они уничтожили бы большую часть инфраструктуры, используемой для защиты информации, передаваемой в Интернете. Эта пугающая возможность заставила исследователей изо всех сил пытаться создать новые, «постквантовые» схемы шифрования, чтобы сохранить как можно больше информации от попадания в руки квантовых хакеров.
Ранее в этом году Национальный институт стандартов и технологий показал, четыре финалиста в поисках стандарта постквантовой криптографии. Три из них используют «решетчатую криптографию» — схему, вдохновленную решетками, регулярным расположением точек в пространстве.
Решеточная криптография и другие постквантовые возможности кардинально отличаются от современных стандартов. Но все они опираются на математическую асимметрию. Безопасность многих современных криптографических систем основана на умножении и разложении на множители: любой компьютер может быстро умножить два числа, но могут потребоваться столетия, чтобы разложить криптографически большое число на его простые составляющие. Эта асимметрия делает секреты легкими для кодирования, но трудными для расшифровки.
Что Шор показал в своем алгоритме 1994 года, так это то, что особенность факторинга делает его уязвимым для атак квантовых компьютеров. «Это очень специфическая, особая вещь, которую может делать квантовый компьютер», — сказал он. Кэтрин Станге, математик из Колорадского университета в Боулдере. Итак, после Шора у криптографов появилась новая задача: найти новый набор математических операций, которые легко выполнить, но почти невозможно отменить.
Решетчатая криптография — одна из самых успешных попыток на сегодняшний день. Первоначально разработанный в 1990-х годах, он основан на сложности обратного инжиниринга суммы баллов.
Вот один из способов описать решетчатую криптографию: представьте, что у вашего друга есть решетка, которая представляет собой просто набор точек в регулярном повторяющемся узоре по всей плоскости. Ваш друг хочет, чтобы вы назвали 10 из этих пунктов. Но он трудный, и всю решетку не нарисует. Вместо этого он перечисляет всего два пункта — первый с x-значение 101 и y-значение 19, другое с координатами [235, 44].
К счастью, на решетке легко найти новые точки, потому что, добавляя и вычитая любые две точки на решетке, вы получаете третью точку в той же решетке. Так что все, что вам нужно сделать, это сложить баллы, которые дал вам ваш друг, или умножить их на целые числа, а затем сложить их, или какую-то комбинацию из двух. Сделайте это восемью разными способами, и вы сможете ответить на вопрос вашего друга.
Но ваш друг все еще не удовлетворен. Он дает вам те же две начальные точки, а затем спрашивает, находится ли точка [2, 1] на той же решетке. Чтобы правильно ответить на этот вопрос, вы должны найти комбинацию [101, 19] и [235, 44], которая дает [2, 1]. Эта задача намного сложнее, чем первая, и вам, вероятно, придется просто гадать и проверять, чтобы получить ответ.* Именно эта асимметрия лежит в основе решетчатой криптографии.
Если вы действительно хотите использовать решетчатую криптографию для обмена информацией, вы должны сделать следующее. Представьте, что друг (более приятный!) хочет отправить вам защищенное сообщение. Вы начинаете с квадратной сетки чисел. Скажем, он имеет две строки и два столбца и выглядит так:
Теперь вы придумываете закрытый «ключ», который знаете только вы. В этом примере предположим, что ваш закрытый ключ состоит всего из двух секретных чисел: 3 и −2. Вы умножаете числа в первом столбце на 3, а числа во втором столбце на -2. Сложите результаты в каждой строке, чтобы получить третий столбец с двумя записями.
Приклейте новый столбец к концу вашей сетки. Эта новая сетка из трех столбцов является вашим открытым ключом. Делитесь свободно!
(Реальный сценарий будет немного сложнее. Чтобы хакеры не расшифровали ваш закрытый ключ, вы должны добавить немного случайного шума в свой последний столбец. Но здесь мы собираемся проигнорировать этот шаг для простоты. )
Теперь ваш друг будет использовать открытый ключ, чтобы отправить вам сообщение. Она придумывает два собственных секретных числа: 2 и 0. Она умножает числа в первой строке на 2, а числа во второй строке на 0. Затем она суммирует результаты в каждом столбце, чтобы получить третью строку.
Теперь она прикрепляет новую строку к нижней части сетки и отправляет ее обратно вам. (Опять же, в реальной системе ей нужно было бы добавить немного шума в свою строку.)
Сейчас ты прочитаешь сообщение. Для этого вы проверяете правильность последней строки вашего друга. Примените свой закрытый ключ к первым двум записям ее строки. Результат должен соответствовать последней записи.
Ваш друг также может отправить вам строку с неправильным номером в последнем столбце. Она знает, что это число не совпадет с вашими расчетами.
Если ваш друг отправит строку, в которой последнее число верное, вы интерпретируете это как 0. Если она отправит строку, в которой число неверное, вы интерпретируете ее как 1. Таким образом, строка кодирует одиночное число. бит: 0 или 1.
Обратите внимание, что внешний злоумышленник не будет иметь доступа ни к вашему закрытому ключу, ни к ключу вашего друга. Без них злоумышленник не будет знать, верно ли окончательное число или нет.
На практике вы хотели бы отправлять сообщения длиннее одного бита. Таким образом, люди, которые хотят получить, скажем, 100-битное сообщение, будут генерировать 100 новых столбцов вместо одного. Затем отправитель сообщения создаст одну новую строку, изменив последние 100 записей, чтобы закодировать либо 0, либо 1 для каждой записи.
Если решетчатая криптография действительно реализована, она будет иметь бесчисленное множество нюансов, не охваченных в этом сценарии. Например, если вы хотите, чтобы сообщение было действительно защищено от посторонних глаз, матрица должна иметь невообразимое количество записей, что делает все это настолько громоздким, что его не стоит использовать. Чтобы обойти это, исследователи используют матрицы с полезными симметриями, которые могут сократить количество параметров. Кроме того, существует целый набор настроек, которые можно применить к самой проблеме, способу включения ошибок и многому другому.
Конечно, всегда есть вероятность, что кто-то найдет фатальную ошибку в решетчатой криптографии, как это сделал Шор в факторинге. Нет никакой гарантии, что конкретная криптографическая схема сработает перед лицом любой возможной атаки. Криптография работает до тех пор, пока ее не взломают. Действительно, этим летом одна многообещающая схема постквантовой криптографии была взломана используя не квантовый компьютер, а обычный ноутбук. Для Штанге весь проект создает неудобный парадокс: «Что я нахожу таким удивительным в криптографии, так это то, что мы построили эту инфраструктуру для человечества, твердо веря в то, что наши возможности как людей ограничены», — сказала она. «Это так отстало».
*: Ответ, если вам интересно, 7 × [101, 19] – 3 × [235, 44] = [2, 1]. [вернуться к статье]
