Будущее ассиметричной криптографии

D-Wave — не квантовый компьютер. Это классический компьютер с симуляцией квантовых эффектов, он пригоден только для узкого класса квантовых алгоритмов (и даже с ними непонятно, есть ли какой-то существенный прирост скорости решения по сравнению с классическими). У нас это неоднократно обсуждалось. Регистры реальных квантовых компьютеров всё ещё не превышают пары-тройки десятков кубитов.


Отсюда и до конца.

D-Wave — не квантовый компьютер.

Да, он пока не полноценен, многие считают, что он не чисто квантовый.

Регистры реальных квантовых компьютеров всё ещё не превышают пары-тройки десятков кубитов.

Так это и настораживает, всё сначала начинается с малого.


Вообщем, время покажет)

И пары-тройки кубитов логических.

По сети гуляет манифест 2016-го, где попытались выжать максимум оптимизма, при котором ещё можно просить

Member States and the European Commission to launch a €1 billion Flagship-scale Initiative

но при этом не сгореть от стыда до тла. Timline (стр. 17) получился таким:

Medium-term goals (5-10 years)

• Solve problems in chemistry and materials science with special-purpose quantum computers operating at high speeds beyond one hundred physical qubits.

Long-term goals (>10 years)

• Build a universal quantum computer able to demonstrate the resolution of a problem that, with current techniques on a supercomputer, would take longer than the age of the universe.

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

Ага, т. е. как я понимаю, создать полноценный КК вообще невозможно?

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

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

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

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


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

На правах внештатного криптографа по последним данным симметричная криптография имеет шансы проследовать туда же. Случайный оракул в квантовом мире приобретает более реальные очертания.

В этом сезоне моден алгоритм Саймона, адаптированный для симметрики и это не единственное направление, «из которого можно выжать максимум оптимизма», чтобы было на что просить.

Я слабо себе представляю, что КК может угрожать хешированию, насколько мне известно, хеширование квантово-устойчиво, я это видел несколько раз на сайтах, а сам Алгоритм Саймона появился очень давно.

1. Можно поподробнее про Алгоритм Саймона и про ( https://eprint.iacr.org/2016/197 ) своими словами?

(!) 2. А как хеширование, например SHA-3 512 бит (Keccak), что будет с ним?

3. А как же предел Бремерманна, что скорость не более 1.36 * 10^50 бит в секунду на килограмм для любой материальной структуры?

(!) 4. Угрожает ли Алгоритм Саймона при использовании SHA-3 (Keccak) 512 бит для создания Message Auth Code, при длине ключа также 512 бит?
Напомню, он вычисляется там достаточно просто – MAC = Hash(Key + Data).

– - – - – - – - – - – - – -

Я нашёл на одном сайте следующее про Алгоритм Гровера:

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

Ещё нашёл комментарий на geektimes.ru от 10 декабря 2015 года:

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

К слову, на Википедии про Алгоритм Гровера написано следующее:

Доказано, что GSA является оптимальным в следующих отношениях:
1. Константу pi/4 нельзя улучшить.
2. Большего квантового ускорения, чем квадратичное, нельзя получить для неисчезающей доли всех возможных черных ящиков f.

Это универсальный алгоритм перебора для чёрного ящика, дающего лишь квадратичное ускорение. Условие 2 означает, что не существует никакого алгоритма перебора хеш-значений, быстрее, чем Алгоритм Гровера?

Всё, что вы изложили — это примерный консенсус на данный момент. Но во вполне официальной науке есть те, кто считает, что это уже не так и эти сведения могут устареть.

Классически, любой брутфорс симметрики — это перебор всех значений, одного за одним. А любое квантовое вычисление (если очень грубо) — это когда вместо конкретных значений функции ей скармливают квантовую суперпозицию сразу многих значений из большого интервала (уж извините за дикую безграмотность в терминологии и примитивное понимание вопроса). И можно быстро получить ответ, есть ли в интервале решение или нет. Если нет — ищем на другом интервале, если есть — разбиваем интервал на части и быстро находим. Чем больше по размеру интервал можно скормить за раз — тем лучше.

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

Теоретически это было предсказано как раз для псевдослучайных функций (хэшей и MAC) года три-четыре назад. Теперь под это подводят конкретные квантовые алгоритмы, пока со слабыми возможностями и слабыми различителями. В режимах шифрования вот поковырялись. В будущем планируют уже учитывать свойства конкретных алгоритмов. Вот, к примеру, если раунд AES или Keccak описывается замкнутой алгебраической функцией, кто поручится, что она не решается как-нибудь хитро квантовым способом? А якобя неалгебраические алгоритмы решаются алгебраическими методами ещё эффективнее. Чисто теоретически. На практике то оно в классике недостижимо. А что там в квантах?

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

Переименовываете транскомпьютационные проблемы в транскомпьютационный криптоанализ, придумываете терминологию (наподобие трансфинитных вычислений), создаём математический аппарат для проведения соответствующих вычислительный операций, добавляем по вкусу уничтожение тёмной материи в чёрных дырах и замыканиях петель времени, и всё, вы — основоположник очередного прорывного направления ;)

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

Если кроме алгоритма Гровера работает алгоритм Саймона или что-то ещё, то это уже не так. И это пока до внутренней структуры криптоалгоритмов ещё даже не добрались. RSA/DH/EC — это цельные естественные математические группы и поля, а симметрика — синтетические составные структуры, полного строгого описания свойств которых нет. Как их там можно вертеть в квантовом мире — никто пока достоверно не скажет. Просто описание конкретной симметрики на языке квантовых вычислений — сложная задача и пока их рассматривают только как чёрные ящики с некоторыми свойствами.

Лучше уж надеяться, что требуемый QC так и не построят.

Лучше уж надеяться, что требуемый QC так и не построят.

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

Итак, пока я заметил на горизонте лишь такие атаки на криптографию:
1. Математические атаки на сам шифр или хеш
2. Угроза со стороны КК

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

Кстати, а может ли вообще существовать принципиально другой компьютер, кроме классического или квантового?

Посмотрим что время нам покажет...

Но не будем о грустном):

У криптографов есть такая традиция: каждые сто лет они собираются все вместе и уничтожают все квантовые компьютеры на планете.

: ) :

Кстати, а может ли вообще существовать принципиально другой компьютер, кроме классического или квантового?
– Может: механический.
Важное отличие механических логических элементов от электрических – могут работать одновременно и прямо и обратно.
Значит можно собрать из них например алгоритм умножения и если подать на выход факторизуемое число то входные встанут в среднее положение ("суперпозиция"). Теперь если начать дёргать по очереди входы в 0 или 1 то некоторые остальные будут вставать в 0 или 1 в зависимости существует ли решение или нет, если решений не существует то ни один входной бит не удасться до конца поставить в 0 или в 1. Также не получиться выставить несуществующее решение.
Это похоже на квантовый компьютер только механический :)

Суперпозиции недостаточно, ещё нужно соотношение неопределённости.