Рейтинг:2

Может ли кто-нибудь объяснить доказательство Рабина и Бена о безопасных многосторонних вычислениях?

флаг ua

Может ли кто-нибудь объяснить доказательство Рабин и Бен-ор безопасных многосторонних вычислений?

Идея состоит в том, что каждый игрок $я$, из $N<+\infty$ игроки, держит секрет сказать $s_i$. Все они хотят делиться своей информацией таким образом, чтобы правило функционировало. $f(s_1,s_2,\cdots,s_N)=(a_1,a_2,...a_N)$ формируется и каждый игрок в конце протокола будет знать только свой компонент $a_i$ и никакой другой информации.

  • Как пошагово выполняется протокол Рабина и Бен-Ора? Кто-нибудь может объяснить процедуру?
  • Используют ли авторы перестановки? Если нет, можем ли мы предоставить другое доказательство такого протокола с перестановками? другими словами, что это за функции $f$ которые принимают на вход зашифрованные сообщения о совместном использовании секрета между игроками и могут вычислять выходные данные $а$ это может быть профиль рекомендации стокастического действия, где каждый игрок $я$ учится $a_i$?

Хорошо, позвольте мне дать более подробную информацию из протокола со следующим определением

$\textbf{Определение:}$ Группа $N$ игроки хранят подтвержденный секрет (данные) $s$, разделенный с помощью полинома $ф(х)$, так что $f(0)=s$, и удовлетворяющих условиям ВСС, если:

  • Полином $ф(х)$ имеет степень $t$
  • Каждый игрок, $P_i$, хранит долю секрета $b_i=f(a_i)$
  • Каждый кусок $b_i$ поделился $P_i$, используя WSS

В случае, если посредник есть, это легко показать, но когда посредника нет, проблема становится сложной и трудной. С моей точки зрения я понимаю, что первое, что я хочу сделать, это показать, что секрет поддается проверке. Но что происходит, когда секрет, который хранится у каждого игрока, является частной информацией, известной игрокам до того, как они начнут обмениваться информацией? А именно, у каждого игрока есть личная тайна $s_i$ и если все они поделятся своими секретами с определенной схемой, то они создадут функцию правила, которая будет принимать в качестве входных данных отдельные сигналы и давать им в качестве выходных данных «новую» информацию, которую они будут использовать для выполнения действия в игре, которое может отличаться в случае отсутствия связи. Итак, чтобы сгенерировать эту функцию $f$ Мне нужно доказать, что отдельные секреты $s_i$ которые являются компонентами секретных данных $s=(s_1,s_2,...,s_N)$ следовать поддающейся проверке схеме обмена секретами, а также то, что протокол наделен добавлением и умножением этого поддающегося проверке секрета. На основании протокола Рабина и Бена, или как я могу это сделать?

Кроме того, могу ли я использовать протокол Додис и др. (2000) вместо Рабина и Бена-или протокол показать проверяемую схему обмена секретами для более чем двух игроков?

Daniel avatar
флаг ru
Было бы очень полезно, если бы вы предоставили немного подробностей о конкретных частях протокола, которые вы не понимаете.
Hunger Learn avatar
флаг ua
@Daniel Я имею в виду случай многосторонних вычислений, но позвольте мне добавить некоторые части в основной текст.
Рейтинг:2
флаг ru

Честно говоря, я не на 100% знаком с оригинальной презентацией в RB89, но они представили несколько техник, которые использовались во многих последующих статьях, и сегодня есть своего рода упрощенная версия (в современных терминах) надежного секрета. Схема обмена есть. Например, описание высокого уровня можно найти на странице 3. здесь.

В двух словах, цель состоит в том, чтобы взять секрет $s\in\mathbb{F}$ и распределить между $n$ стороны $P_1,\ldots,P_n$ чтобы в более поздний момент стороны могли восстановить этот секрет друг для друга, гарантируя при этом, что даже если некоторые $t$ коррумпированные партии с $t<n/2$ отправлять неверные значения, честные (т. е. некоррумпированные) стороны все равно могут получить основной секрет. Это достигается следующим образом:

  • Дилер использует традиционный обмен секретами Шамира для получения доли секрета. $(s_1,\ldots,s_n)$. Если $t<n/2$, то эти акции обеспечивают обнаружение ошибок, что означает, что сторона, получающая эти акции, где $t$ из них могут быть изменены из-за враждебного поведения, могут узнать, был ли секрет подделан, но, в случае ошибок, данная сторона не может «исправить их» для восстановления правильного секрета. Этого недостаточно для надежного обмена секретами.

  • Дилер выбирает равномерно случайные пары $(\alpha_{ij},\beta_{ij})\in\mathbb{F}^2$ и вычисляет $\tau_{ji} = \alpha_{ij}\cdot s_j + \beta_{ij}$ для каждой пары $i,j\in[n]$ (здесь $[n] = \{1,\ldots,n\}$). Как мы увидим, цель этих дополнительных данных состоит в том, чтобы гарантировать, что принимающая сторона сможет не только определить, были ли подделаны общие ресурсы, но и фактически идентифицировать неправильные, следовательно, отфильтровывая правильные, что приводит к восстановлению правильного секрета.

  • Дилер отправляет $\sigma_i = (s_i, \{(\alpha_{ij},\beta_{ij})\}_{j\in[n]}, \{\tau_{ij}\}_{j\in[n ]})$ каждой стороне $P_i$. Проще говоря: каждый $P_i$ получает долю $s_i$ плюс пара ключей $(\alpha_{ij},\beta_{ij})$ для каждой другой стороны. Кроме того, $P_i$ получает «аутентифицированную версию $s_i$" с использованием ключей друг друга.

Скажем, вечеринка $P_j$ должен узнать секрет. С этой целью стороны $P_i$ за $i\in[n]\setminus\{j\}$ Отправить $P_j$ их ценности $(s_i',\tau_{ij}')$ (если $P_i$ честно, то $s_i' = s_i$ и $\tau_{ij}' = \tau_{ij}$, но коррумпированная сторона может отправить неверные значения), и $P_j$ проверяет, используя свой собственный ключ $(\alpha_{ji},\beta_{ji})$, что $\tau_{ij}' = \alpha_{ji}\cdot s_i' + \beta_{ji}$.

В качестве упражнения можно проверить, что если $s_i'\neq s_i$, то вероятность выполнения этого уравнения не более $1/|\mathbb{F}|$ (при этом используется тот факт, что $P_i$ не знает ключ $(\alpha_{ji}, \beta_{ji})$, что является случайным), поэтому, пока поле достаточно велико, $P_j$ сможет отфильтровать неправильные доли и, следовательно, восстановить секрет из оставшихся правильных.


Это как-то поможет вам с конкретными вопросами, которые у вас были? Не стесняйтесь оставлять любые комментарии, если вам нужны разъяснения в определенном направлении.

Hunger Learn avatar
флаг ua
То есть, другими словами, всю работу делает дилер. Он тот, кто предоставляет информацию агентам в схеме, которая называется схемой аутентификации, и им необходимо обмениваться некоторыми сообщениями между собой, чтобы получить все части своего индивидуального сообщения и зашифровать его с помощью какой-либо процедуры... ?
Daniel avatar
флаг ru
В RB89 предлагается схема надежного разделения секрета: есть дилер с секретом $s$, который определенным образом распределяет его среди множества сторон.Позже есть реконструктор, который хочет узнать этот секрет, поэтому стороны отправляют ему некоторую информацию. Вот что описано в RB89.
Hunger Learn avatar
флаг ua
Хорошо, я понимаю это сейчас. Но моя идея заключалась в следующем. Предположим, что у каждого игрока есть свой секрет, представляющий собой некую личную информацию. Все они думают об определенном способе обмена своими личными секретами с остальными игроками, чтобы воспроизвести функцию правила $f$. Итак, с моей точки зрения, каждый игрок может быть делером, а другие игроки могут быть получателями сообщения определенным образом, как это предлагает RB89. Но роль реконструктора, чем она отличается от других сторон?
Hunger Learn avatar
флаг ua
@Daniel где-то в формуле, где вы пишете, то есть $\tau_{ji}=\alpha_{i,j}\cdot s_j+\beta_{i,j}$, должен быть термин по модулю $n$ (mod $n $) верно?
Daniel avatar
флаг ru
@HungerLearn Не совсем так. Под капотом происходит модульная редукция, но она неявна из-за того, что элементы берутся из поля $\mathbb{F}$. Это конечное поле может быть, например, целым числом по простому модулю $p$ (но определенно не по модулю $n$, поскольку $n$ уже используется для обозначения количества акций/партий).
Hunger Learn avatar
флаг ua
@ Даниил, ты прав. Значит, это простое число p обозначает мощность поля?
Daniel avatar
флаг ru
@HungerLearn Да, существуют и другие конечные поля (поля расширения), но в случае, если $\mathbb{F}$ обозначает множество целых чисел по модулю простого числа $p$, мощность результирующего поля будет равна $p$.
Hunger Learn avatar
флаг ua
так что можно было бы написать $\tau_{ij}=\alpha_{ij}\cdot s_i+\beta_{ij} mod p$? И последний вопрос... Протоколы Рабина Бен-Ора и Бен-Ора и др. — это протоколы, в которых можно построить любую функцию-правило, являющееся сложением или умножением секретов. Другими словами, если вы определяете поле с помощью операторов сложения и умножения, у вас есть четко определенная алгебраическая структура для построения любой желаемой функции. Эта функция может быть либо детерминированной, либо вероятностной, верно?
Hunger Learn avatar
флаг ua
@KingOdysseus извините за этот беспорядок комментариев в вашем вопросе ... было бы лучше задать новый вопрос, который принадлежит мне ...
Daniel avatar
флаг ru
@HungerLearn Да, вы можете использовать обозначение модуля. Вы можете определить любую функцию (детерминированную или вероятностную), которая использует сложения и умножения над полем, и использовать существующие протоколы MPC (например, BGW) для безопасного вычисления этих функций.
Hunger Learn avatar
флаг ua
Предполагают ли они неявно, что работают с абелевыми группами?
Daniel avatar
флаг ru
Давайте [продолжим это обсуждение в чате](https://chat.stackexchange.com/rooms/132553/discussion-between-daniel-and-hunger-learn).

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

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