Рейтинг:1

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

флаг us

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

Точнее, я рассматриваю протокол, по которому сервер Боб получает сообщение $к$ от Алисы (это можно рассматривать как шифрование битовой строки $d_0$ под секретным открытым ключом $t_k$) и отправляет обратно сообщение $у$ (что также можно рассматривать как шифрование некоторых сообщений $х$ под тот же открытый ключ $к$ Алисы: не то чтобы из-за формы протокола мне действительно нужно использовать именно этот ключ). В доказательстве безопасности я хотел бы показать, что никакой злонамеренный Боб не может найти секретное значение $\тета_\пи=f(x,d_0)$ в противном случае это должно выглядеть случайным.

Хорошая новость в том, что если я знаю $х$, я могу инвертировать $f$ и найти $d_0$. Следовательно, если злонамеренный Боб знает $х$, я мог бы сделать редукцию, чтобы доказать, что если Боб сможет найти $\тета_\пи$ их Боб тоже знает $d_0 = f^{-1}(x,\theta_\pi)$: это противоречие, поскольку шифрование защищено IND-CPA.

К сожалению, это сокращение не работает, потому что злонамеренный Боб может не «знать» $х$: они отправляют только зашифрованную версию $у$ об этом: и во время сокращения я не могу расшифровать это $у$ поскольку ключ известен только Алисе (в моем случае это неизбежно)...

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

РЕДАКТИРОВАТЬ

Чтобы ответить Микеро, я думаю, что в вашем рассуждении нужно сказать что-то вроде этого:

введите описание изображения здесь

Если нам удастся получить правильный ящик, то я согласен, что доказательство легко следует. Но я не знаю, как доказать эквивалентность этих двух сценариев. Я не думаю, что это прямое снижение безопасности IND-CPA, потому что отличительный признак также имеет доступ к $\тета_\пи$ что связано с некоторой информацией о расшифровке $у$. Я думаю, было бы также неплохо показать, что первая диаграмма эквивалентна

введите описание изображения здесь

но не уверен, как это доказать (конечно $Идеальная функция_1$ отличается от $Идеальная функция_3$, вопрос когда добавим симулятор сверху).

флаг us
Похоже, что Алиса в этой ситуации честна, поэтому симулятор должен сгенерировать открытый ключ Алисы. Тогда симулятор сможет расшифровать шифротексты, зашифрованные этим открытым ключом, и выполнить обычное сокращение. Кстати, что произойдет, если Боб просто повторит то же самое шифрование $d_0$?
флаг cn
В качестве альтернативы стандартным способом убедиться, что противник знает открытый текст, было бы добавление доказательства знания к зашифрованному тексту.
Léo Colisson avatar
флаг us
@Maeher Спасибо за ваш ответ.К сожалению, это не может работать в моем случае, потому что я нахожусь в квантовой среде: в основном, чтобы противник узнал $x$, ему нужно разрушить свое состояние (и тогда протокол больше не полезен). Я мог бы, конечно, использовать подход «вырезать и выбрать», время от времени спрашивая, не уничтожать ли состояние и время от времени продолжать, но тогда я получаю только полиномиальную безопасность :-( Я также не думаю, что предложенный подход by Mikero работает, постараюсь уточнить в другом сообщении.
Léo Colisson avatar
флаг us
@Mikero Спасибо за ваш ответ, но я не уверен, что он работает (по крайней мере, в моем случае). Если симулятор выбирает открытый ключ Алисы, нам нужен аргумент, чтобы сказать, что симулятор может зашифровать случайный $d_0'$ вместо $d_0$ (поскольку $d_0$ не должен попасть в симулятор) без обнаружения. Однако я не думаю, что это прямо подразумевается IND-CPA (см. мое редактирование). Я что-то пропустил?
Léo Colisson avatar
флаг us
@Mikero также, если Боб вернет $y$, то это в основном установит $x = 00$ (что совершенно нормально).
флаг cn
Я не уверен, что понимаю, как квантовая настройка является проблемой. Вы хотите сказать, что y на самом деле *не* зашифрованный текст, а произвольная суперпозиция зашифрованных текстов? Во-первых, почему вы позволяете противнику делать это? А во-вторых, насколько я понимаю, вы можете точно так же вычислить доказательство знания на этой суперпозиции.
Léo Colisson avatar
флаг us
@Maeher Это потому, что цель протокола - создать квантовое состояние, неизвестное Бобу. По сути, чтобы получить $y$, Боб должен создать суперпозицию $\sum_x | х \угл | г(х) \rangle$. Функция $g$ является 2-к-1: поэтому после измерения второго регистра мы получаем $| x \rangle+|x' \rangle$ в первом регистре для двух прообразов $g$. Из этого состояния мы можем получить новое квантовое состояние, которое будет использоваться в других протоколах (противник не может полностью описать это состояние, так как он не может инвертировать $g$). Если бы Боб хотел выучить один $x$, он мог бы его измерить... но это бы его разрушило.
Léo Colisson avatar
флаг us
Таким образом, $y$ — это классический шифрованный текст, но он определяется с помощью суперпозиции, которая все еще полезна после окончания протокола.

Ответить или комментировать

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