Анонимные совместные вычисления

Анонимные совместные вычисления

Иногда бывает так, что группе людей требуется совместно вычислить некоторую функцию от многих переменных. Каждый участник вычислительного процесса является источником значений одной или нескольких переменных этой функции. Результат вычислений становится известен всем членам группы, однако ни один из них не в состоянии выяснить что-либо о значениях, поданных на вход функции другим членом группы.

Вычисление средней зарплаты

Допустим, что начальник отдела приказал своим подчиненным подсчитать среднюю зарплату в отделе. Начальник осведомлен о зарплате любого сотрудника, но слишком занят более важными делами, чтобы отвлекаться на подобные пустяки. Каждый сотрудник прекрасно знает собственную зарплату, но категорически не желает сообщать о ней сослуживцам. Чтобы сотрудники отдела (Антон, Борис, Владимир и Георгий) смогли просуммировать свои оклады, сохранив их в тайне от других, им следует воспользоваться следующим протоколом:

1. Антон генерирует случайное число, прибавляет его к своей зарплате,

шифрует полученную сумму при помощи открытого ключа Бориса и затем передает то, что у него получилось, Борису.

2. На своем тайном ключе Борис расшифровывает результат,

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

3. На своем тайном ключе Владимир расшифровывает результат,

вычисленный Борисом, прибавляет к нему свою зарплату, шифрует полученную сумму при помощи открытого ключа Георгия и затем передает то, что у него получилось, Георгию.

4. На своем тайном ключе Георгий расшифровывает результат,

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

5. На своем тайном ключе Антон расшифровывает результат,

вычисленный Георгием, вычитает из него случайное число, сгенерированное на шаге 1, делит на количество сотрудников отдела и получает искомую среднюю зарплату в отделе.

Точность вычисления средней зарплаты зависит от честности каждого сотрудника. Если хотя бы один из участников протокола соврет относительно своего жалованья, итоговое значение будет неверным. Особенно большими потенциальными возможностями для злоупотреблений обладает Антон. На шаге 5 он может вычесть любое число, какое только придет ему в голову, и никто не заметит подделки. Поэтому необходимо обязать Антона воспользоваться какой-либо из схем предсказания бита. Однако, если от Антона потребуется раскрыть перед всеми случайное число, сгенерированное им на шаге 1, зарплату Антона узнает Борис. Это значит, что начальнику отдела все же придется отвлечься и самому выполнить вычисления, предусмотренные шагом 2 протокола. Ведь он и так знает зарплату Антона.