Читая учебники по двусторонним вычислениям, я столкнулся с двумя (по крайней мере, формально) разными определениями безопасности (с получестными противниками).
Я хочу знать, действительно ли эти определения различны или можно показать, что они эквивалентны.
Я подозреваю, что они разные, но я мог что-то упустить, учитывая, что я нигде не читал о разных определениях.
В Линделл (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) определить вычислительную неразличимость для вероятностных ансамблей, индексированных только параметром безопасности.
Я также видел подобные определения вычислительной неразличимости в других местах.
Затем при определении безопасности они требуют, чтобы совместные распределения были вычислительно неразличимы. для всех входов.
По крайней мере, формально это наводит меня на мысль, что здесь незначительная функция может зависеть от ввода.
Буду очень признателен за ответы на следующие вопросы:
- Я что-то упустил или неправильно понял определения? Могут ли показанные определения быть эквивалентными, используя неоднородность противника?
- Если нет, значит ли это, что в последнем определении не требуется, чтобы существовала единственная незначительная функция, которая «работает» для всех входных данных?
Если я не ошибаюсь, это означает, что эти два определения на самом деле разные?
- Если они разные: какому из определений следует отдать предпочтение?
