Юмор

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


Да, неплохой мультик.

P.S. Заметил статью в конферинционных абстрактах: «Linear-optical Quantum Router» [Cernoch, Lemr, Bartkiewitz, Soubusta]. Ссылаются на это и это. В общем, квантовые свичи и квантовые роутеры уже в разаботке. Естественно, на BSD и с прозрачной т(а,о)рификацией :-)

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

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

Т.е. Postquantum crypto может быть нужно будет создавать и для симметрики. Но пока официально это нигде вроде не заявлено ни одним специалистом.

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

И помимо Гровера для симметрики, приводящего к усорению полного перебора с n бит до n/2 бит. Иными словами говоря, все 128-битные шифры накрываются медным тазом, поэтому их надо выводить из использования как можно скорее.


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


Ну, почему, Реннер уже давно говорит, что пора:^*

Abstract. It is well known that classical computationally-secure cryptosystems may be susceptible to quantum attacks, i.e., attacks by adversaries able to process quantum information. A prominent example is the RSA public key cryptosystem, whose security is based on the hardness of factoring; it can be broken using a quantum computer running Shor's efficient factoring algorithm. In this extended abstract, we review an argument which shows that a similar problem can arise even if a cryptosystem provides information-theoretic security. As long as its security analysis is carried out within classical information theory, attacks by quantum adversaries cannot in general be excluded.

...

Conclusions

The proof that a cryptographic system is secure against any classical adversary does not in general imply that it is also secure in the presence of quantum adversaries. While this is not very surprising for cryptosystems that use quantum communication (such as Quantum Key Distribution schemes), the example shown in Section 3 illustrates that even purely classical cryptosystems may become insecure in the presence of quantum adversaries.

Nevertheless, in various cases the full (quantum) security of a cryptographic scheme may follow generically from its security against classical adversaries (see [Unr10]). Furthermore, in the particular case of key expansion protocols in the bounded storage model, security can be obtained via the use of quantum-proof extractors, as shown in [KR11] (see also [DPVR09]). However, it is an open question whether general cryptographic concepts such as privacy amplification schemes based on extractors--for which there is a classical security proof--can in a generic way be shown secure against quantum adversaries.

Более того, он порывается чуть ли ни сделать даже более серьёзное заявление: то, что считалось IT-безопасным в классической криптографии против классического атакующего, может перестать быть таковым по отношению к квантовому атакующему. Конец одноразовому блокноту? Шутка.

Да и нельзя сказать, что классические криптографы недостаточно осведомлены о происходящем. Додис публиковался совместно с Реннером, Видик и Додис тоже знают друг друга. Т.е., в общем-то, в этой Computer-Science-тусовке все про всё в курсе и часто работают над проблемами совместно (те, у кого бэкграунд в классической теории, с теми, у кого он в квантовой). На STOC- и FOCS-конференциях, которые изначально были про классическую CS, тоже есть секции по Quantum Computer Science (QCS), люди туда ездят и докладываются.

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


Дык специалисты уже давно об этом трындят, но за пределами области об этом мало кто знает. Первая квантовая революция (создание квантовой механики) фактически сделала научную революцию и перевернула всю индустрию. Хотя в 20-ых годах квантмех и ОТО казались слишком абстрактными для практических применений, сейчас вы пользуетесь этим ежедневно.^** Сейчас предрекают вторую квантовую революцию. В теории она уже произошла, произойдёт ли в эксперименте — это пока вопрос, но люди работают.

^*Conference «Mathematical and Engineering Methods in Computer Science», Conference Proceedings, Series Title «Lecture Notes in Computer Science», Springer, 2012.
^**Не будь ОТО — не работал бы GPS у вас в машине [1], [2].

А эта новость не об этом ли самом была? Если да, то «уже заявляли».

Как известно, DIQKD (как и другие DI-протоколы и DI-устройства защиты информации) основано в т.ч. на таком свойстве, как нелокальность.¹ На тему нелокальности совсем недавно вышел основательный обзор, по которому можно оценить масштаб проблемы. Всего так много есть, что это уже целое море. И надо заранее понимать, что это всего лишь обзор работ, где по поводу каждой работы-ссылки можно произнести максимум несколько предложений, а то и вообще до полпредложения урезать приходится. Там и про DIRNG есть и про DIQKD, и про коммуникационную сложность, и про нелокальные игры (см. главу «IV. Applucations of quantum nonlocality»).

Недавно один из цитируемых в этом обзоре коллег делал доклад на эту тему.² Для себя отметил, что непонятно практически ничего, нужно вдумчиво читать статьи, чтобы начать что-то понимать в теме. :-( Запомнившиеся термины-хинты, о которых говорят в контексте нелокальности:

• Представление Майорана и комплексная геометрия
• Нелокальность первого типа (CHSH и корреляционные функции)
• Нелокальность второго типа (Mermin)
• Парадокс Харди³
• Квантовые состояния Dicke
• Преобразование Мёбиуса
• Моногамия
• Байесовы игры

Впрочем, практически обо всём этом так или иначе упомянуто в вышеприведённое обзоре.

---

¹Именно потому в контексте DI произносится столько слов про неравенства Белла и про их обобщения — CHSH-неравенства.
²Название доклада — «Нелокальность симметричных состояний и её применения в квантовой информации».
³Имеется: a > 0, b = c = d = 0, но a – b – c – d ≤ 0 — неравенство, демонстрирующеее нелокальность. Можно было бы выложить слайды.

Интересная деталь на тему фундаментальности нелокальности: на стр. 26 есть параграф «Grothendieck's constant and Bell inequalities with unbounded violation». И тут Гротендик! Впрочем, ранее он уже встречался всвязи с применением в КТИ теоремы Дворецкого.

Слайды
Тэг: private

все 128-битные шифры накрываются медным тазом

напомните сколько это символов?

Байтов? Печатных ASCII? Base64?

вот спасибо. помню читал, но не мог вспомнить где).

помню читал, но не мог вспомнить где).

Почти всё есть здесь.⁴ В частности, приведённый пост — ответ на вопрос «О минимальной длине пароля, рекомендуемой для защиты от атаки методом полного перебора».

⁴Уже накопилось +50 новых ссылок из последних обсуждений, которые надо бы туда проинвестировать добавить.

Вот одно из применений по этой тематике, вроде не упоминавшееся в докладе.

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

Статьи по коммитменту — вещь, где можно обжечься. Доказано, что безусловный коммитмент запрещён (авторы по ссылке это признают), а с небезусловным там какое-то болото, я не специалист, чтоб судить. Пока писал пост, подоспел ответ от специалиста:

Я бегло просмотрел статью. На первый взгляд, я не думаю, что она ошибочна, по двум причинам: они действительно обсуждают, почему доказательство невозможности BC неприменимо, и Адан Кабелло — признанный исследователь в области. Также я знаю, что протокол BC возможен, если используются релятивистские эффекты, но это вводит дополнительные ограничения на протокол [а именно, это не позволяет задерживать reveal phase (момент, когда сторона сообщает бит?)]. Если я понимаю правильно (но я не читал детали), их основная идея — скомбинировать идеи с этих релятивистских протоколов с идеями нелокальности, чтобы преодолеть ограничения (невозможности протокола)... Возможно, работа стоит того, чтобы прочитать её более внимательно.

Можно. Вы берёте плотность вероятности P(x₁, x₂,...) такую, что нарушает неравенства Белла, генерируете выборку и загружаете её на сторону Алисы и Боба. Пока выборка не будет исчерпана, будет казаться, что нелокальность нарушается, всё ОК.


Идея в том, что если Алиса и Боб не могут между собой общаться после начала эксперимента по измерениям, то, как бы они не договаривались между собой заранее, они не смогут создать выборку, которая бы нарушала неравенства Белла. Смысл примерно в этом (если исключить выдачу уже предсгененированной выборки, которая, к слову, не может быть бесконечной).

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

Можно ещё вспомнить про некопируемость информации: если одна часть максимально запутана с другой, она не может быть запутанной с кем-либо ещё. Проделав эксперимент, вы убеждаетесь, что результаты измерений дают такие корреляции, которые соответствуют максимально запутанным состояниям, а раз так, вы знаете, что у каждой из частей, и что противник не запутал своё состояние с какой-либо из сторон. Можно пофантазировать, что вы покупаете одну часть QKD у одного производителя, а другую — у другого, тем самым исключая предзагруженные результаты измерений; либо вы можете раскрыть ящик и сами проверить общий принцип его функционирования, чтобы исключить такую «закладку».

Представьте себе QKD-ящик. Классическую часть QKD-протокола можно сделать отдельным классическим модулем, внести его за рамки рассмотрения DI и ничего от него не требовать. В этом случае останется только квантовый модуль. Единственное его общение с миром — посылка (излучение) квантовых состояний, все другие его коммуникации вы можете зарубить подобающим герметичным кожухом. Нам надо добиться того, чтобы излучаемые им квантовые состояния соответствовали протоколу, а то вдруг посылается не то, что задекларировано, и это поможет Еве, сидящей на канале, слушать информацию? Здесь та же проблема, что и с генерацией гаммы в TRNG. Вдруг случайный поток — неслучайный и получен шифрованием счётчика? Но в классике вы, какую статистику ни делай, не сможете отличить истино случайную гамму от псевдослучайной, кванты же вам такую возможность дают из-за завязки на нелокальность. Вообще, в DIQKD рассматриваются разные постановки: доверен прибор только у одной из сторон, или недоверены оба из них и т.п.

Я могу наговорить много чуши, потому что никогда не разбирался с DI.⁶ Первая попытка на тему, о чём же идёт речь в DI, обсуждалась в этой же ветке на примере DIQRNG, и с тех пор я не возвращался к этому вопросу. Выкладываемые слайды вдумчиво тоже не пролистывал повторно, поэтому есть какое-то впачатление только в самых общих чертах.

Я недавно сконвертил видик⁷ (сам ещё его несмотрел), получилась полная запись туториала по введению в DIQKD для тех, кто знает КТИ, но ничего не знает про DI. Оно должно быть вразумительным, доклад неплохой, где-то час длительностью + вопросы. Думаю, скоро залью на youtube.⁸ Помимо него есть полный Колбек и ещё несколько полных докладов, уже более профессиональных и узконаправленных (но Колбек всё же ещё достаточно общий характер имеет).


Вышеупомянутая дискуссия, как оказалось, — вопросы Жизана к Колбеку после его докалада. Я постараюсь написать стенограмму, если получится, но краткая мораль такова: Жизан настаивает, что DI — это self-testing приборов, защита от неидеальности, несовершенства приборов, возможность легитимной стороне быстро обнаружить ошибки и брак в приборах, но это не означает, что прибор можно покупать у противника. Тем не менее, другие с ним не согласны. Грубо говоря, есть некоторое свойство, которым можно воспользоваться для борьбы с гэ улучшения защиты и доверия к коммуникационным приборам, а вот под каким соусом это свойство подавать — уже дело третье. Наверное, по-своему все они в чём-то правы. Искоробки оно даёт только защиту от брака, но если предположить выполнение ряда дополнительных условий, то можно покупать прибор и у недоверенной стороны.

---

⁵Вроде бы это как-то нетрудно доказывается из общих соображений.
⁶Однако, поверхностная верификация писанины проходит проверку по результатам обсуждений с коллегами.
⁷Пережатие в x264 занимает в 20 раз больше времени, чем сама длительность видео, зато вес видео уменьшается в 15.5 раз при примерно том же качестве.
⁸Оригинал весит где-то 550MB, в меньшем качестве, чем HD, будет весить в 2-3 раза меньше.

Вы берёте плотность вероятности P(x₁, x₂,...) такую, что нарушает неравенства Белла, генерируете выборку и загружаете её на сторону Алисы и Боба. Пока выборка не будет исчерпана, будет казаться, что нелокальность нарушается, всё ОК.

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