Безопасные многосторонние вычисления – одна из центральных проблем в криптографии, решение которой позволяет реализовывать множество практических задач, в том числе задачу проведения честных демократических выборов. Недавно криптоаналитики предложили схему проведения многосторонних вычислений в сети с ограниченным количеством связей.
Суть безопасных многосторонних вычислений можно сформулировать так: вычисление функции по нескольким аргументам от разных участников так, что каждый участник может узнать ответ, не узнав чужих аргументов. Например, гипотетические личности Анна и Борис могут определить кто из них богаче, не разглашая размера своих состояний.
Однако реализация безопасных многосторонних вычислений связана с некоторыми трудностями. Она требует наличия непрослушиваемых каналов связей между каждыми двумя участниками (узлами), а также общего канала связи. Криптоаналитики Хуан Гарай (Juan Garay) и Рафаил Островски (Rafail Оstrovsky) предложили метод построения достаточного числа безопасных каналов в сети с ограниченным числом связей. Их работа называется “Almost-everywhere Secure Computation” (“Безопасные вычисления почти везде”).
Исследователи базировались на данных Дворка (Dwork), Пелега (Peleg) и других авторов о реализации “Византийского соглашения” – схемы, позволяющей найти согласованное решение участниками сети, некоторые из которых нарушают установленный протокол.