Я определяю многопартийное вычисление, используя реально-идеальную парадигму (см. Прагматичное введение в безопасные многосторонние вычисления).
То есть для любой успешной атаки на протокол MPC в реальном мире существует симулятор, который успешно проводит эту атаку в идеальном мире. Отсюда следует, что безопасность в реальном мире должна быть эквивалентна безопасности в идеальном мире.
Я определяю интерактивные системы доказательства с нулевым разглашением для языка $L$ используя исходное определение из Сложность знаний интерактивных систем доказательства. то есть пара $(А, В)$ интерактивных машин Тьюринга должны выполнять
- Комплектность: дано $x \в л$, $В$ принимает с очень высокой вероятностью;
- Обоснованность: при любом прувере $А'$ и $x \не\в L$ перешел в $(А', В)$, $В$ принимает с очень низкой вероятностью;
- Zero-Knowledge: существует вероятностный симулятор с полиномиальным временем, который может имитировать весь обмен сообщениями между $А$ и $В$ для любого входа $x \в л$.
Теперь бумага Нулевое разглашение благодаря безопасным многосторонним вычислениям упоминает следующее:
Протоколы с нулевым разглашением можно рассматривать как частный случай безопасного двустороннего
вычисление, где функция проверяет действительность свидетеля, имеющегося у доказывающего.
То есть дано $L \in \mathcal{NP}$, существует алгоритм $А$ такой, что $x \in L \iff \exists w\двоеточие A(x, w) = 1$ (значение $\mathcal{NP}$).
Одна вечеринка $P_1$ выступает в качестве доказывающего, другой $P_2$ в качестве верификатора.
$P_1$ знает $х$ и $w$, $P_2$ знает только $х$.
Они выполняют $А(х, ш)$ вместе, чтобы определить, $x \в л$ или не.
Четко, $w$ не сообщается проверяющему $P_2$ благодаря протоколу MPC.
Однако не является ли определение нулевого знания более общим?
Если доказывающий $P_1$ отправлено, по какой-то причине, решение в какой-то экземпляр $\mathcal{NP}$-полная проблема1, никакой симулятор с полиномиальным временем не мог бы смоделировать это, предполагая, что $\mathcal{P} \neq \mathcal{NP}$.
Созданная система доказательств не будет с нулевым разглашением.
Таким образом, учитывая, что протокол MPC может обмениваться несимулируемыми сообщениями, протокол MPC фактически не может использоваться для реализации системы доказательства с нулевым разглашением для какого-либо языка. $L \in \mathcal{NP}$, может это?
1 Решение можно поставить в зависимость от $х$ таким образом, чтобы он не был постоянным и, таким образом, легко моделируемым.
