Обобщенные модели конфиденциальных вычислений

Рассматривается сеть взаимодействующих процессоров. Некоторые процессоры могут «сбоить». При сбоях, приводящих к останову (FS-сбоях), сбоящий процессор может приостановить в некоторый момент времени отправку своих сообщений. В то же время предполагается, что сбоящие процессоры продолжают получение сообщений и могут выдавать некую информацию в свои выходные каналы. При византийских сбоях (Ву-сбоях) процессоры могут произвольным образом сотрудничать друг с другом с целью получения необходимой для них информации или с целью нарушения процесса вычислений. При By-сбоях сбоящие процессоры могут также объединять свои входы и изменять их. В то же время, такие действия должны происходить при условии того, что изучение любой информации о входах несбоящих процессоров невозможно.

Сбои могут быть статическими и динамическими. При статических сбоях набор сбоящих процессоров фиксирован вначале и в процессе вычислений, при динамических — может меняться, как может меняться и характер самих сбоев. Сбоящие процессоры будут также называться нечестными участниками вычислений, в противоположность честным участникам, которые выполняют предписанные вычисления.

Противника можно представлять как некий универсальный процессор, действия которого заключаются в стремлении сделать процессоры сети сбоящими («подкупить» их). По аналогии со сбоями противник может быть динамическим и статическим. Статическим противником является противник, который «сотрудничает» с фиксированным числом сбоящих процессоров («подкупленных» противником). При действиях динамического противника количество сбоящих процессоров может меняться, в том числе непредсказуемым образом.

Кроме того, противник может быть активным и пассивным, а также с априорными и апостериорными, протокольными и раундовыми действиями. Пассивный противник не может изменять сообщения, циркулирующие в сети. Активный противник может знать все о внутренней конфигурации сети, способен читать и изменять все сообщения сбоящих процессоров и, по своему усмотрению, выбирать сообщения, которые будут посылать сбоящие процессоры при вычислениях. Активный динамический противник может в начале каждого раунда подкупить несколько новых процессоров. Таким образом, он может изучить информацию, получаемую ими в текущем раунде, и принять решение, подкупить ему новый процессор или нет. Такой противник может собирать и изменять все сообщения от сбоящих процессоров к несбоящим. В то же время гарантируется, что все сообщения (в том числе между несбоящими процессорами) будут доставлены адресатам в конце текущего раунда. Действия аналогичного характера активный противник может выполнить не только в течение раунда (в его начале и конце), но и до начала выполнения протокола и после его завершения. Противник называется^{-противником,} если он «сотрудничает» с t процессорами.

Взаимодействие процессоров может осуществляться посредством конфиденциальных и (или) аутентифицированных и (или) открытых каналов связи (рис. 4.5). Кроме того, может существовать широковещательный канал связи, т. е. канал, посредством которого один из процессоров может одновременно распространить свое сообщение всем другим процессорам сети. Такой канал называется также каналом с общей шиной.

Взаимодействие в сети характеризуется трафиком Т, который может представлять собой совокупность сообщений, полученных участниками вычислений в r-м раунде в установленной модели взаимодействия.

Каждый процессор i имеет также широковещательный канал, представляющий собой ленту, исключающую вались для i и являющийся каналом «только-для-чтения» для всех остальных процессоров сети.

Предполагается, что в раунде г для каждого процессора i существует однозначно определенное сообщение (возможно пустое),.

которое распространяет процессор i в этом раунде и для каждой пары процессоров i и j существует единственное сообщение, которое i может безопасным образом послать j в данном раунде. Все каналы.

Рис. 4.5. Взаимодействия участников вычислений в реальном и идеальном сценарии (п = 5, t = 2) являются помеченными так, что каждый получатель сообщения может идентифицировать его отправителя.

Каждый процессор i запускает программу л_;. Совокупность таким образом выполняемых программ n_j реализует распределенный алгоритм П. Протоколом работы сети называется «-элементный кортеж Р = (я, я₂, л_н). Протокол называется t-устойчивым, если t процессоров являются сбоящими во время выполнения протокола.

Историей процессора i являются:

• • содержание его конфиденциального и общего входа;
• • все распространяемые им сообщения;
• • все сообщения, полученные i по конфиденциальным каналам связи;
• • все случайные параметры, сгенерированные процессором i во время работы сети.

Для доказуемо конфиденциального вычисления вводятся понятия идеального и реального сценария. В идеальном сценарии дополнительно вводится доверенный процессор (ГР-процессор). Процессоры конфиденциально посылают свои входы ГР-процессору, который вычисляет необходимый результат (выход) и также конфиденциально посылает его обратно процессорам сети (см. рис. 4.5).

Противник может манипулировать этим результатом (вычислить или изменить его) следующим образом. До начала вычислений он может подкупить один из процессоров и изучить его конфиденциальный вход. Основываясь на этой информации, противник может подкупить второй процессор и изучить его конфиденциальный вход. Это продолжается до тех пор, пока противник не получит вею необходимую для него информацию. Далее у противника есть два основных пути. Он может изменить входы сбоящих процессоров. После чего те, вместе с корректными входами несбоящих процессоров, направляют свои новые измененные входы ГР-процессору.

По получении от последнего выхода значения вычисленной функции противник может приступить к изучению выхода каждого сбоящего процессора. Второй путь заключается в последовательном изучении входов и выходов процессоров, подключая их всякий раз к числу сбоящих. В данном случае рассматривается противник, который не только может изучать входы сбоящих процессоров, но и менять их, изучать по полученному значению функции входы несбоящих процессоров.

Для размышления В реальном сценарии не существует '/'/?'-процессора, и все участники вычислений моделируют его поведение посредством выполнения многостороннего интерактивного протокола. Считается, что вычисления в действительности (в реальном сценарии) безопасны, если эти вычисления эквивалентны вычислениям в идеальном сценарии.

Всякий раз для конкретного протокола конфиденциальных вычислений идеальный и реальный сценарии детально уточняются.