Алиса нравится забавляться с плюшевыми медведями. В эротических фантазиях Боба важное место зан и-мают мраморные столы. Оба весьма стесняются своих привычек, но с удовольствием нашли бы кого-нибудь, кто разделил бы с ними их... гм... образ жизни.
В Службе безопасных вычислений с несколькими участниками мы спроектировали протокол для подобных людей. Мы занумеровали впечатляющий список их пристрастий от "африканских муравьедов" до "яблочных пирогов". Разделенные модемной линией связи, Алиса и Боб могут участвовать в безопасном протоколе с н е-сколькими участниками. Они вместе могут определить, есть ли у них общие привычки . Если есть, они могли бы устремиться к обоюдному счастью. Если нет, то они могли бы безопасно расстаться, сохраняя уверенность, что их привычки остались в тайне. Никто, даже Служба безопасных вычислений с несколькими участниками, ник о-гда не узнает об их пристрастиях.
Вот как это работает:
(1) С помощью однонаправленной функции Алиса хэширует свою привычку как семизначную строку .
(2) Используя эту семизначную строку как телефонный номер, Алиса звонит по этому номеру и оставляет с о-общение Бобу. Если никто не отвечает, или номер не обслуживается. Алиса применяет однонаправленную функцию к телефонному номеру до тех пор, пока не найдется кто-нибудь, кто подхватит протокол .
(3) Алиса сообщает Бобу, сколько раз ей пришлось применять однонаправленную функцию к своей привы чке.
(4) Боб хэширует свою привычку столько же раз. Он также использует семизначную строку как телефонный номер и спрашивает человека на другом конце провода, нет ли для него сообщений.
Обратите внимание, что у Боба есть возможность вскрытия с использованием выбранного открытого текста . Он может хэшировать распространенные привычки и позвонить по получившемуся телефону, разыскивая соо б-щения для него. Это протокол реально работает только такое вскрытие непрактично из-за достаточного числа возможных открытых текстов сообщений.
Также существует математический протокол, похожий на Протокол № 2 . Алиса знает а, Боб знает Ъ, и они вместе пытаются определить, верно ли, что а = Ъ, причем так, чтобы Боб ничего не узнал об а, а Алиса - о Ъ. Подробности можно найти в разделе 23.14.