Настраивать
В последнее время я заинтересовался доказательства на основе моделирования в контексте безопасных двусторонних вычислений. Я прочитал несколько глав книги (от Безопасный MPC и совместное использование секретов и Основы криптографии, том 2), документы (самое главное Как смоделировать это), и сообщения из обмена криптографическими стеками, но я все еще не чувствую уверенности в применении методов доказательства, основанных на моделировании. В качестве первого шага я рассмотрел простой аддитивный протокол обмена секретами с получестными сторонами. Там стороны хотят умножить свои секреты и использовать для этого тройки Бивера, так что протокол предполагает какое-то взаимодействие. Я делюсь им здесь, потому что он может быть полезен для других новичков, и я был бы очень признателен за исправления, критику и комментарии.
Протокол умножения
Предположим, что две стороны не вступают в сговор, и предположим, что входные данные $х,у$ принадлежат сторонам $P_1,P_2$, соответственно. Затем, $P_1$ вычисляет доли $x_1\стрелка влево\mathbb{Z}_q$, $x_2 = x-x_1\,\mathrm{mod}\,q$, куда $\leftarrow \mathbb{Z}_q$ обозначает равномерно случайную выборку из $\mathbb{Z}_q$, и отправляет $x_2$ к $P_2$. То же самое происходит аналогично с $у_1,у_2$ в $P_2$ такой, что $P_1$ имеет доступ к $x_1,y_1$ и $P_2$ имеет доступ к $x_2,y_2$ после этого шага. Чтобы вычислить $xy$, стороны используют тройки Бивера следующим образом. Перед выполнением протокола мы отбираем $(\альфа,\бета)\стрелка влево\mathbb{Z}_q^2$, вычислить $\альфа\бета\,\mathrm{mod}\,q = \gamma$ а также акции $\alpha_i,\beta_i,\gamma_i$ с $я\в\{1,2\}$, и раздайте их соответствующей стороне. Затем $я$-я сторона вычисляет
\начать{выравнивать*}
\delta_i=x_i-\alpha_i\,\mathrm{mod}\,q \quad \text{and} \quad \epsilon_i=y_i-\beta_i\,\mathrm{mod}\,q
\конец{выравнивание*}
и отправляет $\delta_i$ а также $\epsilon_i$ к другой стороне. В результате обе стороны могут вычислить
$$
\delta=\delta_1+\delta_2\,\mathrm{mod}\,q=x-\alpha\,\mathrm{mod}\,q \quad \text{and} \quad \epsilon=\epsilon_1+\epsilon_2\, \mathrm{mod}\,q=y-\beta\,\mathrm{mod}\,q.
$$
Имея их под рукой, можно, наконец, получить доли $z:=z_1+z_2\,\mathrm{mod}\,q$ посредством
\начать{выравнивать*}
z_1=\gamma_1+\delta \beta_1 +\epsilon \alpha_1+\delta\epsilon\,\mathrm{mod}\,q \quad \text{and} \quad
z_2=\gamma_2+\delta\beta_2+\epsilon\alpha_2\,\mathrm{mod}\,q.
\конец{выравнивание*}
Мы не раскрываем $z_1$ или же $z_2$ (даже если протокол кажется бесполезным таким образом).
Обратите внимание, что $x_2,y_1,\delta_1,\delta_2,\epsilon_1,\epsilon_2$ были обменены, и все эти величины являются равномерно случайными числами в $\mathbb{Z}_q$. Все остальные вычисления являются локальными. Из этого я делаю вывод, что протокол должен быть абсолютно безопасным.
Доказательство на основе моделирования (попытка)
Насколько я понимаю, доказательство на основе симуляции особенно привлекательно для протоколов, где помимо шифрования могут что-то выявить еще и вычисления и обмен данными. Следовательно, он должен подходить для указанного выше протокола.
Давайте попробуем доказать вышеупомянутую интуицию (что протокол абсолютно безопасен) более формально, применив то, что можно найти в Как смоделировать это и Безопасный MPC и совместное использование секретов. Во-первых, мы видим, что протокол (почти) симметричен.Следовательно, должно быть достаточно, если мы рассмотрим только $P_1$ быть получестным. Далее, функциональность $f(x,y):=z$ протокола $\пи$ является детерминированным и удовлетворяет корректности (оценить $z_1+z_2\,\mathrm{mod}\,q$ для подтверждения). Кроме того, первая составляющая $ф(х,у)$ является $f_1(x,y):=z_1$ и мы вводим представление о $P_1$ к
\начать{выравнивать*}
\mathrm{view}_1^{\pi}(x,y):=\left(x,r_1,m_1,m_2,\dots,m_t\right)\in\mathbb{Z}_q^{1\times p },
\конец{выравнивание*}
куда $r_1$ является содержанием $P_1$внутренняя случайная лента , и $m_1,m_2,\точки,m_t$ обозначать полученные сообщения.
Затем доказательство полной безопасности, основанное на моделировании, требует существования симулятора вероятностно-полиномиального времени. $S_1$ такой, что
\начать{выравнивать*}
\{S_1\left(x,f_1(x,y)\right)\}_{x,y\in\{0,1\}^*} \stackrel{\mathrm{perf}}{\equiv} \ {\ mathrm {представление} _1 ^ {\ pi} \ влево (х, у \ вправо) \} _ {х, у \ в \ {0,1 \} ^ *}.
\конец{выравнивание*}
Полная неразличимость между этими вероятностными ансамблями должна быть достигнута, если для всех возможных $х,у\в\{0,1\}^*$ статистическое расстояние
\begin{уравнение}
\метка{экв:расст}
\Delta(\mathrm{view}_1^\pi(x,y),S_1(x,f_1(x,y)):=\frac{1}{2} \sum_{\boldsymbol{w}\in\ mathbb{Z}_q^{1\times p}} |\mathrm{Pr}(\mathrm{view}_1^{\pi}(x,y)=\boldsymbol{w})-\mathrm{Pr}( S_1(x,f_1(x,y)=\boldsymbol{w})|
\end{уравнение}
исчезает. Мы начинаем с запуска $\пи$ и, согласно предыдущему определению, найти
$$
\mathrm{view}_1^{\pi}\left(x,y\right)=\left(x,x_1,y_1,\alpha_1,\beta_1,\gamma_1,\delta_2,\epsilon_2\right),
$$
куда $x_1$ проистекает из $P_1$внутренний источник случайности (случайная лента), $\альфа_1,\бета_1,\гамма_1$ исходят из вспомогательного автономного источника случайности (но могут также рассматриваться как сообщения?), и $y_1,\delta_2,\epsilon_2$ сообщения, полученные от $P_2$. Обратите внимание, что помимо $х$ все эти величины равномерно случайны в $\mathbb{Z}_q$. Более того, из $\mathrm{представление}_1^{\pi}(x,y)$ все остальные величины, которые $P_1$ имеет доступ, может быть вычислено. Следовательно, $\mathrm{представление}_1^{\pi}(x,y)$ содержит все $P_1$информация.
Осталось найти подходящий $S_1$. С этой целью мы выбираем
$$
S_1(x,f_1(x,y))=\left(x,\tilde{x}_1,\tilde{y_1},\tilde{\alpha}_1,\tilde{\beta}_1,\tilde{\ гамма} _1, \ тильда {\ дельта} _2, \ тильда {\ эпсилон} _2 \ справа)
$$
таким образом, что каждый компонент в $(\tilde{x}_1,\tilde{y_1},\tilde{\alpha}_1,\tilde{\beta}_1,\tilde{\gamma}_1,\tilde{\delta}_2,\tilde{ \эпсилон}_2)$ является равномерно случайным в $\mathbb{Z}_q$ (похоже, что нам не нужен вывод $f_1(х,у)$). Наконец, поскольку $S_1$ может точно имитировать распределение каждого компонента в $\mathrm{представление}_1^\pi$, легко видеть, что $\Delta(\mathrm{view}_1^\pi(x,y),S_1(x,f_1(x,y))=0$ для всех $х,у$. Другими словами, все, кроме $х$ (который предоставляется $P_1$) неотличим от случайного мусора. Таким образом, мы делаем вывод, что протокол абсолютно безопасен.
Некоторые наблюдения/вопросы
- В контексте безопасных двусторонних вычислений кажется, что всякий раз, когда $\mathrm{представление}_1^\pi$ содержит только случайные величины (кроме $х$), мы можем построить симулятор, просто выбрав переменные с теми же распределениями, что и случайные величины. Это делает конструкцию симулятора тривиальной.
- В случае, если одна переменная в $\mathrm{представление}_1^\pi$ действует неслучайно, мы должны построить его из $х,f_1(х,у)$ чтобы получить действующий симулятор. С этой целью предположим $у_1=у$ так как $P_2$ сделал ошибку. Ясно, что это небезопасно, поскольку $P_1$ теперь имеет доступ к $х,у$. Однако только от $х,f_1(х,у)$ мы не можем построить $у$ так как $х$ не имеет ничего общего с $у$ и $f_1(х,у)$ является равномерно случайным в $\mathbb{Z}_q$ по конструкции. Таким образом, этот протокол небезопасен из-за $\Delta(\mathrm{view}_1^\pi(x,y),S_1(x,f_1(x,y))\neq 0$.
- Для чего нужен тренажер $f_1(х,у)$?
