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

Честно говоря, я не на 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$ сможет отфильтровать неправильные доли и, следовательно, восстановить секрет из оставшихся правильных.

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