id: Гость   вход   регистрация
текущее время 19:45 28/03/2024
Владелец: unknown (создано 29/10/2012 13:14), редакция от 16/07/2013 10:08 (автор: unknown) Печать
Категории: криптография, алгоритмы, симметричное шифрование, квантовая криптография
https://www.pgpru.com/Новости/2012/ПредложеныТеоретическиеМетодыИспользованияКвантовогоСлучайногоОракула
создать
просмотр
редакции
ссылки

29.10 // Предложены теоретические методы использования квантового случайного оракула


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


В 1986 году в своей основополагающей работе Goldreich, Goldwasser и Micali дали ответ на вопрос о том, как сконструировать функции, которые выглядят случайными для классического противника (не обладающего квантовым компьютером). В частности, они определили псевдослучайную функцию (PRF), как обладающую таким свойством, что не существует никакого классического алгоритма, имеющего доступ к оракулу PRF, который мог бы отличить её от истинно случайной функции. Они предложили вариант построения таких функций на основе псевдослучайных генераторов. Позднее были предложены конструкции PRF на основе псевдослучайных синтезаторов, также как и напрямую из т.н. сложных проблем. Псевдослучайные функции стали важным инструментом в криптографии: например, они используются в конструировании идентификационных протоколов, блочных шифров, кодов аутентификации сообщений.


В классическом случае при анализе функций ищут различитель между функцией и случайным оракулом — RO, идеализированной моделью, выдающей истинно случайные числа, но каждый раз одинаковые при одинаковых запросах на входе. Представим, что квантовые компьютеры изобретены. Тогда модель классического RO станет неадекватной и потребуется анализ базовых строительных блоков квантовостойких протоколов на основе квантового оракула. Именно такой подход недавно предложил Mark Zhandry из Стэнфордского Университета в своей работе, описывающей конструирование квантовых случайных функций. Спонсорами выступили Национальный Фонд Научных Исследований и Агентство перспективных оборонных разработок США.


При более точном рассмотрении вопроса следует учесть две возможности: противник может делать при помощи квантового компьютера классические запросы к PRF, пытаясь найти различитель между ней и оракулом, проводя при этом некие квантовые вычисления; но он может делать непосредственно и сами запросы к функции квантовым образом. Это более сильное допущение лежит в основе требований к квантовой безопасности. Квантовый запрос состоит из отправки квантовых суперпозиций входов функции и получения суперпозиции выходов. Функция, стойкая к таким атакам названа квантовой псевдослучайной функцией (QPRF).


Так, если псевдослучайная функция используется в качестве кода аутентификации сообщений (MAC), то в квантовом мире противник может подбирать суперпозиции сообщений, вынуждая использовать квантовостойкий MAC.


Создание квантовостойких PRF предоставляет подход для симуляции случайного оракула, работающего на квантовых запросах. Если в классической схеме RO может быть симулирован на лету при помощи идеальной хэш-функции или абстрактной алгоритмической модели (запрос — проверка предыдущего значения — выбор генерации случайного числа с записью или чтения ранее существующего значения — ответ), то в квантовом случайном оракуле вся функция должна быть сгенерирована заранее, ведь в ответ даже на единичный запрос квантовый оракул выдаёт множество ответов сразу. Однако, как показывает автор в предыдущей работе, если количество запросов априорно ограничено q, то достаточно независимых 2q-функций. Но при неизвестном числе запросов квантовый оракул должен быть симулирован при помощи QPRF.


Первый интересный теоретический результат, который удалось получить автору, состоит в том, что стойкие PRF могут быть очевидно нестойкими QPRF. Такие PRF могут иметь очень большой период, неизвестный противнику и необнаружимый классическими методами. Но при квантовом запросе такой период будет выявлен и таким образом противник сможет отличить PRF от идеальной QPRF.


Другим интересным результатом оказалось то, что многие PRF являются QPRF. К ним относятся классические конструкции удваивающих генераторов Goldreich, Goldwasser и Micali, псевдослучайные синтезаторы Наора и Рейнгольда, конструкции на проблемах обучении с ошибками Banerjee, Peikert и Rosen. Последняя конструкция, хотя и построена на использовании алгебраических свойств решёток, предназначена для создания симметричных алгоритмов с возможностью более быстрой работы.


Открытыми вопросами, которые нуждаются в дальнейшем исследовании в данной работе отмечены следующие:


  • Являются ли квантовостойкими PRP — псевдослучайные перестановки (блочные шифры). Несмотря на известность способов преобразований PRF — PRP для доказуемо безопасного создания блочного шифра, доказательство стойкости в модели с квантовыми запросами остаётся неясным.

  • Возможно ли создание квантовостойких MAC.

Источник: Cryptology ePrint Archive


 
На страницу: 1, 2 След.
Комментарии [скрыть комментарии/форму]
— spinore (03/11/2012 06:09, исправлен 04/11/2012 05:17)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786

unknown, что это? Я прочитал новость — ничего не понял, потом почитал оригинал — всё равно ничего не понял. Далее почитал в википедии про квантовые алгоритмы и RO (далёк я от этих тем), поглядел на ещё один креатив1 автора, но и это толком ничего не прояснило. Наконец, я решил начать делать query к RO гуглить по ключевым словам и нашёл вот это2 — его ещё более ранний креатив с кучей соавторов и не без афиллиаций в Амстердаме. Последняя ссылка сильно обнадёжила, но дойти до сути я так и не смог: в самом интересном месте (верх страницы 7) идёт отсылка к [BBC+98], но я не вижу там ничего про квантовый RO.


Попытка понять буквально


Часть трудных мест (стр. 6 тут) я с трудом разобрал, воспользовавшись хрустальными шарами (но в тексте нет никаких намёков на то, как их использовать), но на 7ой странице пассаж

Here, oracle Oi : {0,1}n → {0,1}m maps the first n + m qubits from basis state | x 〉 | y 〉 to basis state | x 〉 | y Oi(x) 〉
for
x ∈ {0,1}n and y ∈ {0,1}m.

меня совсем разочаровал. Если функция (RO) отображает битовую строку длины n в битовую строку длины m (так определяется оракул Oi), то как это может быть мапом n + m кубитов? Да ещё и каких-то «первых» — о чём это? Судя по второй части цитаты, да, можно задать какое-то отображение | x 〉 | y 〉 → | z 〉 | w 〉, где x и z — битовые строки длины n, а y и w — битовые строки длины m. Но вот и слева и справа стоит x — что это значит? Первый вектор не меняется, или сохраняется только его длина? От таких авторов можно всего ожидать.


Можно, конечно, предположить, что аффтар хотел сказать не «maps», а «оракулу можно изоморфно поставить в соответствие другое отображение». Вероятно, я потрясающе безграмотен и незнаком с внутренним криптографическим сленгом, но это очень резво звучит: «функция y = f(x) отображает (x,y) в (x,z)». Нет, ну а чо, всегда можно сказать, что f задаёт в том числе и набор пар (x,y), потому можно слова про изоморфизм и другую область определения опустить и сказать, что f отображает (x,y) в какую-нибудь (x,y(x)).


Ну, хорошо, пусть даже так, и наша цель — отображение | x 〉 | y 〉 → | x 〉 | yOi(x) 〉, но в чём его смысл? Почему входной аргумент оракула (т.е. | x 〉) и его значение (второй вектор, | y 〉) рассматриваются как единое целое, вектор | x 〉 ⊗ | y 〉? Мы хотим описать эволюцию системы «оракул + его вход» как единого целого? А зачем? Почему нам недостаточно считать вход в оракул независимым аргументом, типа Oi : | x 〉 → | y 〉? И таких вопросов там очень много.


P.ک.: А разгадка проста — безбл не стреляйте в аспиранта, он публикуется, как умеет.

Кстати, ссылка на [BBC+98] показательна: это FOCS-конференция, входит в TOP-2 мировых конференций по CS, опубликоваться там крайне трудно (не легче PRL), но текст читаешь и сразу всё ясно: это взято оттуда-то, вот та мысль автором выводится из предыдущих, здесь же, а вон то — общепринятый термин, который если не знаешь, надо его просто гуглить и почитать работы на тему. В плохих же работах (авторы либо не умеют писать, либо не считают нужным тратить на хорошее изложение своё время), как некоторые великие выражаются, «мне даже непонятно, что именно мне непонятно», т.к. общие знания по теме перемешаны с собствеными домыслами и результатами автора, нет чётких формулировок, нет прозрачных отсылок по каждому факту к ранним работам. Такое впечатление, что автор думает, будто бы все с ним годами обсуждали его работу, и потому и сами понимают, что есть x, а что y, как это формализовать и какие допущения используются. Одно дело — уровень внутренних обсуждений со своими, кто варится в этом же котле, и другое — представление результата широкой публике. Стоит отметить, что междисципилинарное понимание результатов возможно только в одном случае: если все используют один язык — общепринятый язык математики. Когда же рабочий сленг в статье начинает зашкаливать, её перестают понимать даже те, кто работают в этой же теме, но над другими задачами. У меня у самого на вычистку сленга из статей в своё время ушли месяцы, потому знаю, о чём говорю.


Общие идеи


Сама идея QPRF, конечно, интересная, но я бы не называл его так (разве что для краткости). Их QPRF — обычная классическая PRF, которую попытались сделать защищённой против квантовых атак (с нечётким определением того, что называть этим словом). Можно сказать, что это постквантовая классическая криптография (чтобы отличить её от конвенциональной «доквантовой» классической и «постквантовой квантовой»). Я бы даже сказал, что любая классическая задача пораждает семейство из 4ёх видов протоколов/отображений:


  1. C → [ящик] → C (классический вход, классический выход).
  2. Q → [ящик] → C (квантовый вход, классический выход).
  3. C → [ящик] → Q (классический вход, квантовый выход).
  4. Q → [ящик] → Q (квантовый вход, квантовый выход).

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

C → [классический ящик] → C,

квантовый алгоритм факторизации — как

C → [квантовый ящик] → C.

Под классичностью входа/выхода подразумевается, что там имеется обычная строка битов, а под его квантовостью — что там набор кубитов3. True QPRF была бы такая PRF, которая принимает на вход квантовое состояние (набор кубитов) и возвращает другое квантовое состояние (другой набор кубитов), причём так, что для разных входов были бы разные/случайные выходы4.


Попытка понять иносказательно


Теперь собственно о том, что имел(и) в виду автор(ы). Они нам говорят, что любая классическая PRF может быть эффективно представленна своим квантовым аналогом. Пользуясь их традицией для обозачений, было бы логичным обозначить такую функцию как PRFQ. Итак, если классическая PRF работает, грубо говоря, как


( 0 1 1 0 1 0 1 1 ) → PRF → ( 0 1 0 0 ),

то её квантовый аналог PRFQ работал бы как

| 0 1 1 0 1 0 1 1 〉 → PRFQ → | 0 1 0 0 〉,

где, например, | 0 1 0 0 〉 = | 0 〉 ⊗ | 1 〉 ⊗ | 0 〉 ⊗ |0 〉. Но, раз аналог квантовый, ему можно подать на вход не | 0 1 1 0 1 0 1 1 〉, а некоторую | ψ 〉, которая не является прямым квантовым аналогом никакой битовой строки, а является их «суперпозицией»5.


Из-за линейности квантовой механики (это аксиома) любое действие над состоянием можно представить действием унитарного оператора U, который «поворачивает» вектор (состояние) | ψ 〉 в прострастве6, поэтому можно построить цепочку применений к | ψ 〉 операций

U1 → ROQ,1U2 → ROQ,2 → ... → UT → ROQ,T,

где T — «время»7. Видимо, это соответствует8 классически-криптографическому «подали вход на оракул, взяли выход, модифицировали, снова подали на вход, получили выход, как-то поменяли, снова подали на вход» и так столько раз, сколько T позволяет. Когда последний результат получили, его можно померить и извлечь нужную битовую строку — утверждается, что якобы какой-то такой вид «квантового криптоанализа» может позволить атакующему отличать классические PRF/RO от истиных PRF/RO эффективней, чем классическими методами9. Однако, от этого якобы можно защититься, сведя такой криптоанализ к какому-то другому (так и не понял какому), классическому, который раньше никто не анализировал, и при котором доступно экспоненциально много то ли операций, то ли пар (вход,выход) для RO/PRF. И они вот этот классический криптоанализ проведут, классическими же методами10, после чего сдизайнят PRF, защищённые от этого типа криптоанализа и назовут такие PRF гордым словом QPRF. Зашибись :)



1Secure Identity-Based Encryption in the Quantum Random Oracle Model.
2Random Oracles in a Quantum World.
3А они несводимы к битовым строкам так же, как эрмитовы матрицы не сводимы к одному из их собственных значений, выбираемому вероятностным образом.
4Тут можно было бы говорить уже и о типе их различимости: можно ли их отличить квантово (действительно ли там разные состояния) или классически (проводя измерения, доказать, что состояния на выходе оракула разные). Кое-что тут было бы заранее очевидным. К примеру, если среднее состояние по ансамблю одно и то же, то ансамбли неразличимы (иначе получаем сигналинг — передачу информации быстрее скорости света). К слову, полная неразличимость ансамблей с одинаковым средним — очень сильный и контринтуитивный факт, но он есть, я к нему не сразу привык.
5Т.е. линейной комбинацией 2n всевозможных векторов, взятых с какими-то комплексными коэффициентами, где каждый из 2n векторов является точным аналогом классической битовой строки. Например, в случае 2ух битов любая | ψ 〉 имеет вид | ψ 〉 = α00 | 0 0 〉 + α01 | 0 1 〉 + α10 | 1 0 〉
+ α11 | 1 1 〉.

6В случае n (ку)битов | ψ 〉 может быть представлена вектором в пространстве размерности 2n.
7Я тут на уровне смысла, о размерности множеств не заботился. Что тут правильнее писать (PRF или RO) — тоже не понял.
8См. «Модель случайного оракула для чайников», «Криптоанализ за две недели», «Криптологию – в массы» (в т.ч. в красочной мягкой обложке).
9Типа, «легко показать что», но мне сходу понять логику автор(а,ов) не удалось.
10Квантовую механику они вроде бы нигде не используют в доказательствах.

— unknown (04/11/2012 19:14)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Поскольку у этого аспиранта в руководителях и даже кое-где в соавторах Dan Boneh (что само по себе конечно не является сильной репутационной гарантией, но всё таки), то дополнительно обратил внимание на эту работу.


У многих авторов терминология немного плавает в определении самих PRF и RO (если нет строгой отсылки к основоположникам), но не до такой степени, чтобы их спутать. PRF — это эффективно вычислимая алгоритмическая реализация (эмулятор RO), пусть даже абстрактная, настолько хорошая, что не отличима от RO в рамках условий на вычресурсы в поставленной задаче. Чаще всего под этим имеют ввиду семейство (PRF-family). Функция всегда выбирается из семейства случайно, так что даже один и тот же вход будет давать случайные выходы, в отличие от хэша. Но после срвершения акта равновероятного и случайного выбора одной функции из всего семейства функций (эмуляция выбора ключа) эта одна функция будет фиксирована (один вход → один выход), как у RO. Их и предлагается различать (строить различитель).


Вот это самое прекрасное во всей этой очевидной классификации. Классическая CCC-криптография и самая фантастическая QQQ-криптография (по такому тоже что-то публикуют, есть даже квантовостойкие асимметричные алгоритмы, исполняемые на квантовом компьютере).

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

В целом с замечаниями скорее согласен или просто не знаю, что конкретно возразить :)


Негоже криптографам лезть внутрь чёрного квантового ящика. Они просто понимают его чисто описательно на уровне, что там полудохлый кот лежит.
— unknown (27/02/2013 15:21, исправлен 27/02/2013 15:23)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Secure Signatures and Chosen Ciphertext Security in a Post-Quantum World.


Теперь и с известным соавтором.


Я бы даже сказал, что любая классическая задача пораждает семейство из 4ёх видов протоколов/отображений:

Сам ящик тоже можно считать либо классическим, либо квантовым.

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


И вроде они доказали, что одноразовые подписи на симметричных алгоритмах (хэшах) — Лампорт, Меркл — квантовостойкие. Причём, подозреваю, что их работы малопонятны специалистам-некриптографам по квантовым вычислениям. В разных исследовательских сообществах — разный язык.

— Гость (14/06/2013 07:25)   <#>
/comment65996 заел мою совесть. Если долго откладывать, то отвечено не будет никак, ни коротко, ни длинно, но самое страшное — будет забыто то, что хотел написать в качестве ответа. Надо было хотя бы набросок в черновиках написать. :-(

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

В общем, про квантовый RO: я дятел, потому что это, оказывается, вещь стандартная, есть даже в Н&Ч (там около трёх разворотов книги ей посвящено), используется в куче областей, в том числе, в квантовой теории сложности. Можно почитать Н&Ч, выложить сканы и ещё раз подумать над вышеописанным. Чуть позже нашёл, что в коридоре каждый день хожу мимо постеров, на которых висит это определение RO, и как только я раньше его не замечал? Надеюсь вернуться к этому позже, сейчас времени развивать тему нет.
— unknown (14/06/2013 10:12, исправлен 14/06/2013 10:13)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

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


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

— Гость (22/06/2013 05:17)   <#>

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

  1. Оракул — не то же, что в классическое криптографии (считается, что там только частный его случай), это что-то типа абстрактной blackbox-функции без каких-либо особых предопределённых свойств.
  2. Adversary (и adversary method) — не противник, хотя определённая связь с этим понятием имеется. В теории сложности общеприняты оценки на скорость алгоритмов в случае самого худшего входа (input)* — это можно интерпретировать так, как будто вы пытаетесь выполнить алгоритм как можно быстрее, а компьютер наоборот изыскивает все способы, как бы замедлить решение вашей задачи, как бы подсунуть вам самые неоптимальные входные данные (т.о., играет роль вашего противника — adversary). Ещё мне показалось (это, возможно, ошибочно), что adversary характеризует степень незнания вычисляющего.

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

Краткая мораль: за счёт алгоритма Гровера можно ускорить процедуру брутфорса любого алгоритма с 2n-1 до 2n/2-1 шагов — именно за счёт этого эффективно уполовинивается длина всех симметричных шифров при квантовом атакующем. Имеются и обобщения этой процедуры: если вероятность удачи есть P, то в классике в среднем требуется 1 / P операций на подбор удачи, в то время как при квантовом поиске достаточно 1 / √P операций. Помимо собственно брутфорса, да, действительно, можно найти те особенности классических криптоалгоритмов, которые решаются с помощью квантовых вычислений быстрее, что вполне оправдывает квантовый криптоанализ классических шифров.


Трудно не согласиться.


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


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

P.S. Н&Ч-га ещё не читал, поэтому на счёт оракулов позже выскажусь. Когда в теории сложности пишут ABCDEF, DEF — это как раз тип используемого оракула, если ничего не путаю.

*Есть теория сложности, где оценивается среднее времени на исполнение алгоритма (усреднение по разным входам), но там намного труднее что-либо посчитать и доказать.
— unknown (22/06/2013 10:51, исправлен 22/06/2013 10:52)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Интересно, что обозначения на постере похожи на те, что были в ваших оценках по Беллейру-Роговею. :-) Впрочем, это логично: и там и тут оценивают вычислительную сложность, только в классике она условная, а в квантах стараются перейти к безусловным оценкам

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

— Гость (23/06/2013 05:45)   <#>

Или мне кажется, или и правда есть такой терминологический парадокс: термин «вычислительная безопасность» реально обозначает совсем не то, что должен бы. Правильнее говорить, что есть безусловная безопасность и условная, где безусловная — то же самое, что и вычислительная или информационно-теоретическая (единственный способ взломать — брутфорс). Собственно, термин «IT-безопасность» как раз и подразумевает возможность найти точную оценку на вычислительную сложность взлома, почему бы тогда не называть такую безопасность вычислительной? Как давно термин «вычислительная безопасность» вдруг стал синонимом условной безопасности?
— unknown (23/06/2013 12:45)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
С момента развития теории информации и доказательства отсутствия утечки данных об открытом тексте в шифртекст Шенноном, появилось понятие "информационно-теоретически стойкий".

Дальше думали, как сделать, чтобы можно было:

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

Тогда (наверное?) считали, что можно создать практически неломаемый шифр, только соблюдая по крайней мере эти два основных ограничения. Оставаясь в рамках выч.модели можно, якобы, сделать что-то неломаемое и даже усиленно (псевдо)доказательную базу под это дело подводить — "доказуемую безопасность".
— Гость (24/06/2013 01:41)   <#>

Оно звучит очень правдоподобно, и именно поэтому ваше заявление о доказуемости несуществования ICM вызвало шок. Правда, тут всё спотыкается об определения. Доказуемая безопасность и случайный оракул требуют неразличимости от случайного текста — это очень сильное требование, намного превосходящее те требования, которые достаточны для неэффективности практического криптоанализа. А с позиции здравого смысла кажется очевидным, что нельзя взломать конкретное сообщение, зашифрованное конкретным шифром, быстрее, чем за какое-то (трудно оцениваемое) число операций. С другой стороны, даже если бы мы смогли оценить затраты на взлом в этом случае, вся безопасность рухнула бы при малейшем переопределении понятий (а что, если имеется на одно сообщение, а десять сообщий, зашифрованных этим же алгоритмом? И так далее).
— Гость (01/07/2013 03:22)   <#>

§ 6.1.1. Оракул (пока без комментариев).
Тэг: private
— unknown (21/01/2015 11:40, исправлен 21/01/2015 11:57)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

The Classification of Quantum Symmetric-Key Encryption Protocols. См. таблицу на третьей странице. Китайцы рассмотрели Plaintext, Ciphertext, Key, Encryption, Decryption, присвоили им буковки "C" и "Q" и получили 25 = 32 сочетания для протоколов, от CCCCC до QQQQQ. Они как-то показывают, что 21 сочетание невозможно, а 5 вариантов протоколов — под вопросом. Это только для симметрики, естественно.



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

— Гость (21/01/2015 21:49)   <#>

Спасибо, очень интересно.

It was Boykin[1] who firstly suggested the quantum one time pad, he encrypted n qubits by 2n bits classical key with Pauli rotation operations. // Стр. 2

Мне казалось, что первые работы в этом направлении были до [1], но могу ошибаться — надо смотреть ссылки. Возможно, в первых работах не было доказано то, что нужно бы доказать. С шифрованием кубитов (авторы тут тоже про это пишут) мне также не всё ясно: можно шифровать квантовую информацию (состояние кубитов), а можно классическую (биты, которые в них закодированы), поэтому не совсем понятно, в чём состоит суть заявления, когда пишут про 2n вместо n (есть же классический одноразовый блокнот). Мне кажется, Винтер как-то подтверждал, что в той его статье с Амбаинисом речь шла именно о шифровании квантовой информации.

These kinds of protocol have one trait in common: they request at least one of the encryption and decryption algorithms belongs to classical space, meanwhile they request at least one of the plaintext, ciphertext, and key belongs to quantum space. This means they will take a quantum state as the input or output object of a classical algorithm, which is not valid.

If a algorithm involve a quantum object, it must also belong to quantum space. Both encryption and decryption algorithms involve plaintext, ciphertext and key simultaneously. Encryption algorithm takes plaintext and key as input objects, and ciphertext as output object. Decryption algorithm takes ciphertext and key as input objects, and plaintext as output object. As a result, if one of the encryption and decryption algorithms belongs to classical space, the plaintext, ciphertext and key must all belong to classical space. Therefore these 21 kinds of quantum symmetric-key encryption are unable to construct. // Стр. 10

The last type includes the rest 21 kinds, they are proved to be unable to construct as they request classical algorithm work on quantum target, which is not valid. // Стр. 11

Это всё требует медитации. Вдруг авторы неправы? Дело в том, что любое классическое состояние можно превратить в квантовое тривиальным отображением. В то же время, любое квантовое можно превратить (в общем случае, с потерей информации и недетерминированно) в классическое посредством измерения. Затем, кажется, между алгоритмом и состоянием тоже есть некоторая дуальность (одно можно представить как другое). Как всё это вместе собрать в кучу и осознать — пока не могу сказать.


Ну, не совсем так, но примерно. Я не говорил в лоб, что квантовый оракул — это чушь. Мои претензии касались лишь того, как его ввели в работу и определили авторы (на тот момент я действительно не знал, что это понятие существует и всем, кто в теме, хорошо известно). Непонимание во многом снимается этим:

Кстати, непонимание, откуда берётся ⊕ в квантовом RO, снимается этим же фактом: раз квантовые вычисления обратимы, их классический прообраз тоже строится обратимым (в Н&Ч это есть), и, собственно, ⊕ появляется уже на стадии конструирования обратимого описания классических вычислений/операций в обычной классической теории, а потом эти концепты переносят на квантовый случай простой калькой.

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

Например, у нас есть внутренний сленг, когда всё, что относится к одной частице, мы называем одномерным случаем, две частицы — двумерным и т.д. И все друг друга понимают, о чём речь. Полное осознание патовости терминологии возникло, когда я попытался объяснить это другому, не вхожему в наш узкий круг. Он немало прифигел с этого, потому что, во-первых, даже если это одна частица (кубит), то состояние гильбертово двумерное, а если две частицы, то четырёхмерное. Связь там n ↔ 2n. Но и это ещё не всё. Когда мы говорим о частицах, это просто привычка, оставшаяся от дискретного случая, а у нас всё непрерывно, потому, конечно же, никаких частиц нет, а «одна частица» — это одна мода. «Две частицы» — две моды. Только вот настоящее пространство одной моды уже бесконечное, а двух мод — бесконечность в квадрате. Правда, поскольку нас интересуют только ковариации и гауссовы состояния, бесконечное пространство эффективно описывается как двумерное в пространстве ковариаций, поэтому всё же оно «как бы двумерное». И вот это «думерное пространство для матриц ковариаций» — «случай одной частицы» и «одномерный», да. Клёво? Когда для своих рисуешь на доске и есть возможность переспросить, по контексту все всех понимают, о чём речь. А когда это же хочешь изложить в статье, приходится долго бить себя по рукам, чтобы описать это не на сленге, а на формальном общепринятом языке. Хорошо, я напрягся, а 99% других людей напрягаться на этот счёт не будут, поэтому в статью попадёт адская смесь из «ну вы же должны быть в курсе», «люди в области это знают», «можно же догадаться по контексту» и «а это формальное определение». И серьёзные люди с топовыми именами часто так свои работы пишут, что уж говорить про чернорабочий пролетариат типа нас.

Когда начинал читать Cover&Thomas с первых параграфов, я сразу же видел там косяки на каждом шагу — например, требуется догадаться о чём-то, но явно это не произнесено. Не сказано, какое множество в какое отображается, не проводится связь с теорией вероятности (хотя теория информации основана на ней), некоторые определения вообще не понятно как обобщать, и как они должны звучать в общем виде, и т.д. Я на каждом шагу вижу, что исходя из материала параграфа естественно возникает вопрос, на который прочтение этого параграфа должно бы давать ответ, но не даёт — ответ нужно домысливать самому или искать в других источниках. И всё это основы самого простейшего — теории информации. А что говорить о более сложных вещах?

Короче, я последовательно выступаю против сленга. Все должны формулировать свои определения на конвенциональном языке математики, а не переизобретать язык — это единственный способ сделать коммуникацию между людьми из разных областей возможной. Я понимаю, что сленг тоже служит тем, что упрощает язык между теми, кто «уже в курсе», и какие-то части сленга впоследствии удаётся формализовать и корректно встроить в математический язык, но нельзя аппелировать к тому, что ещё неформализовано — надо либо самому формализовывать сленг в своей же статье до момента его использования (я часто так делал), либо опираться на то, что кем-то уже было формализовано в других статьях/работах.

А вообще, это всё следствие того, что инженерия, физика и разные гуманитарные науки исторически брали своё начало не в математике, и лишь потом их связь с математикой устанавливалась. До сих пор расхлёбываем эти «гуманитарные» первобытные представления последствия.
— unknown (22/01/2015 11:08)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Заметна глобальная проблема: чем больше объёмы информации, тем меньше ресурсов на её структурирование, её так и вываливют в фрагментарном виде, её даже приходиться учиться понимать полусырой.
— unknown (28/01/2015 11:00, исправлен 28/01/2015 11:22)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Bit-oriented quantum public-key encryption. Теперь китайцы утверждают, что изобрели (правда, не первые) инф.-теоретически стойкое квантовое шифрование с открытым ключом (QPKE). И дополнительно упомянули классификацию четырёх типов асимметричного квантового шифрования.


Эффективность их метода оценивается как:


The proposed scheme in this paper aims at encrypting classical message, the public-key will be used only once to encrypt one bit,
but the private key can be reused o(2n2 p(n) − n) times. So one private-key corresponding to exponential public-keys and one private-key can encrypt exponential classical bits.

Оказывается, QPKE уже давно существует, в т.ч. на телепортации. Оно ещё и IT-стойкое оказывается.

На страницу: 1, 2 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3