Рейтинг:4

Существуют ли разные определения безопасных двусторонних вычислений?

флаг mm

Читая учебники по двусторонним вычислениям, я столкнулся с двумя (по крайней мере, формально) разными определениями безопасности (с получестными противниками). Я хочу знать, действительно ли эти определения различны или можно показать, что они эквивалентны. Я подозреваю, что они разные, но я мог что-то упустить, учитывая, что я нигде не читал о разных определениях.

В Линделл (2016), безопасное двустороннее вычисление определяется следующим образом: Для каждой стороны совместное распределение симуляции и идеального результата должно быть вычислительно неотличимо от совместного распределения состязательного представления и вычисленного вывода. Формально для каждого $i \in \{1, 2\}$, должны существовать ppt. алгоритмы $S_i$ такой, что $$ {\ lbrace (S_i (1 ^ n, x, f_1 (x, y)), f (x, y)) \ rbrace} _ {x, y, n} \stackrel{c}{\equiv} {\lbrace (\operatorname{view}^\pi_i(x, y, n), \operatorname{output}^\pi_i(x, y, n)) \rbrace}_{x, y, n} \,\текст{.} $$ Это определение имеет для меня смысл, поскольку автор определяет вычислительная неразличимость над вероятностными ансамблями, индексируемыми как параметром безопасности и ввод:

Два вероятностных ансамбля $X = \{X(a, n)\}_{a \in {\{0, 1\}}^*; п \in \mathbb{N}}$ и $Y = \{Y(a, n)\}_{a \in {\{0, 1\}}^*; п \in \mathbb{N}}$ считаются вычислительно неразличимыми, обозначаемыми $X \stackrel{c}{\equiv} Y$, если для каждого неравномерного полиномиального алгоритма $Д$ существует пренебрежимо малая функция $\му(\кдот)$ такой, что для каждого $a \in \{0, 1\}^*$ и каждый $n \in \mathbb{N}$, $$ \lvert \Pr[D(X(a, n)) = 1] - \Pr[D(Y(a, n)) = 1] \rvert \leq \mu(n) \,\текст{.} $$

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

По сравнению, Эванс и др. (2018) определить вычислительную неразличимость для вероятностных ансамблей, индексированных только параметром безопасности. Я также видел подобные определения вычислительной неразличимости в других местах. Затем при определении безопасности они требуют, чтобы совместные распределения были вычислительно неразличимы. для всех входов. По крайней мере, формально это наводит меня на мысль, что здесь незначительная функция может зависеть от ввода.

Буду очень признателен за ответы на следующие вопросы:

  1. Я что-то упустил или неправильно понял определения? Могут ли показанные определения быть эквивалентными, используя неоднородность противника?
  2. Если нет, значит ли это, что в последнем определении не требуется, чтобы существовала единственная незначительная функция, которая «работает» для всех входных данных? Если я не ошибаюсь, это означает, что эти два определения на самом деле разные?
  3. Если они разные: какому из определений следует отдать предпочтение?
Geoffroy Couteau avatar
флаг cn
Для каждого многовременного противника A мы можем ограничить размер $(x,y)$ до $p(n)$ для некоторого фиксированного многочлена $p$ (большего, чем время выполнения A) в определении, поскольку A не может читать более $ p(n)$ бит их ленты в любом случае. Тогда, когда у нас есть конечное число $x$ и $y$, что плохого в том, чтобы выделить одну универсальную пренебрежимо малую функцию, взяв максимум из всех функций, которые мы получаем для каждой пары $(x,y)$?
Distinguishable Llama avatar
флаг mm
@GeoffroyCouteau Может быть, я неправильно понял ваш комментарий, но я не понимаю, как ограничить размер ввода; параметр безопасности $n$ не фиксирован. Во втором определении для всех входов существует пренебрежимо малая функция $\mu$, так что безопасность выполняется для всех $n$. Так что может быть, например, для любого многочлена $q$ $\mu(n)
Geoffroy Couteau avatar
флаг cn
Хорошо, это имеет смысл. Тогда придется ломать голову, как-то... Как-то утомительно :)
Distinguishable Llama avatar
флаг mm
@GeoffroyCouteau Да, это утомительно. Спасибо за участие в любом случае :)
Yehuda Lindell avatar
флаг us
@GeoffroyCouteau Смотрите мой ответ. Я не думаю, что это эквивалентно на самом деле.
Geoffroy Couteau avatar
флаг cn
Да, именно в это я сейчас и поверил, немного поразмыслив. Спасибо за уточняющий ответ!
Рейтинг:4
флаг us

Определить неразличимость очень сложно.Я действительно думаю, что определение в книге Эванса и др. слишком слаб, но, возможно, Майк Росулек выскажет свое мнение. Если вы определяете безопасность, говоря, что для каждого входа распределения REAL/IDEAL неразличимы, то на самом деле вы говорите следующее: для каждого входа и каждого различителя существует незначительная функция $\му$ так что различитель преуспевает с вероятностью не более $\му(п)$. Это означает, что вам может понадобиться отдельная незначительная функция для каждого входа. Чтобы быть более конкретным, если мы раскроем это дальше, это определение говорит о том, что для каждого входа каждый отличительный признак $Д$ и каждый многочлен $р$ существует значение $n_0$ такой, что для каждого $n>n_0$ различитель преуспевает с вероятностью меньше, чем $1/п(п)$. Это означает, что $n$ может зависеть от ввода и, в частности, нет $n_0$ так что дальше $n_0$ существует неразличимость для всех входов. Другими словами, вам потенциально придется использовать разные параметры безопасности для разных входных данных. Это не то, что вы хотели бы делать (и это было бы даже невозможно, поскольку как вы соглашаетесь с параметром безопасности, не зная входных данных, и как вы определяете, каким должен быть этот параметр безопасности). Напротив, в определении, где вход является частью ансамбля, есть один $n_0$ для всех входов. Вопрос о том, как мы это определяем $n_0$ на практике это просто — это то, что нам нужно для обеспечения безопасности всех примитивов, которые мы используем. Излишне говорить, что Эванс и др. не делают ничего другого в своих конструкциях. Однако определение ошибочно, насколько я понимаю.

[Кроме того, есть короткая статья Михир Белларе под названием Примечание о незначительных функциях что позволяет вам поменять местами квантификаторы на противнике и незначительной функции. Однако, насколько мне известно, это не работает для входных данных.]

Distinguishable Llama avatar
флаг mm
Это отвечает на мой вопрос :) Спасибо также за предложение статьи о незначительных функциях.
флаг us
Эта оценка кажется мне правильной. Я исправлю определение в нашем следующем обновлении ошибок. Спасибо всем здесь за коллективный отчет об ошибке!
Distinguishable Llama avatar
флаг mm
Просто примечание к статье Белларе: я думаю, что его аргумент в пользу обращения квантификаторов может работать и для входных данных, но я не совсем уверен (аргумент несколько сложнее для неоднородных противников, но он, по крайней мере, должен работать). для однородных противников). Два приведенных здесь определения по-прежнему различаются, потому что Белларе использует еще одно понятие одной пренебрежимо малой функции $\mu$: он требует только, чтобы выражение **в конечном итоге** было меньше, чем $\mu$, что по-прежнему допускает $n_0 $ зависит от ввода.
Yehuda Lindell avatar
флаг us
В этом случае здесь недостаточно хорошего определения безопасности (имея зависимость $n_0$ от ввода). Однако существуют большие различия между вводом и противником, поэтому я был бы осторожен с проверкой этого.

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

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