Задача миллионеров-социалистов

Задача миллионеров-социалистов (англ. Socialist Millionaires' Problem, SMP, Tierce problem) — криптографическая задача, в которой два миллионера хотят выяснить, равны ли их состояния, не разглашая точные суммы. Решение этой задачи используется в качестве криптографического протокола, который позволяет двум сторонам проверить подлинность удаленного участника с помощью общего секрета, избегая атаки «человек посередине», без необходимости сравнивать вручную отпечатки открытого ключа через другой канал.

История 
Впервые задача безопасного многостороннего вычисления была поднята Эндрю Яо в 1982 году. Два миллионера, Алиса и Боб, хотят выяснить, кто же из них богаче, при этом они не хотят разглашать точную сумму своего благосостояния. Яо предложил в своей статье оригинальный способ решения задачи, получившей впоследствии название «». В 1996 году в работе Маркуса Якобссона и Моти Юнга частный случай, в котором Алиса и Боб хотят выяснить, равны ли их состояния, был назван задачей миллионеров-социалистов. Другой вариант названия — «Tierce problem» (tierce — французская игра на ставках): подразумевается, что два игрока хотят выяснить, одинаковая ли у них комбинация ставок.

Эффективное решение задачи миллионеров-социалистов было предложено в 2001 году в работе Фабрис Будо, Берри Шонмейкерса и Жака Траоре. Оно было реализовано в протоколе OTR (Off-the record), после того как в 2007 году Оливер Гоффарт опубликовал модуль mod_otr для сервера ejabberd, позволяющий автоматически проводить атаку типа «человек посередине» на пользователей OTR, не проверяющих отпечатки открытых ключей друг друга.

Свойства 
Алиса и Боб знают секреты  и  соответственно.

Свойства, которые должны присутствовать в протоколе взаимодействия:
 Отсутствие утечки информации: если предположить, что Алиса и Боб добросовестно следуют протоколу, они не должны знать ничего кроме того, совпадают их секреты или нет.
 Конфиденциальность: никто другой не должен узнать секреты Алисы и Боба. Активный злоумышленник, способный произвольно вмешиваться в общение Алисы и Боба, должен узнать не больше, чем пассивный злоумышленник.
 Безопасность: ни Алиса, ни Боб не должны быть обмануты. Если кто-то из них не следует протоколу, он по-прежнему должен узнать секрет собеседника только при совпадении  и .
 Простота: протокол должен быть простым в реализации и понятным, то есть Алиса и Боб не должны тратить большое количество времени, энергии и денег, чтобы использовать протокол.
 Удаленность: Алиса и Боб не должны присутствовать физически в одном и том же месте, чтобы выяснить, совпадают ли секреты.

Решение без криптографии 
Решение задачи может быть представлено в наглядном виде, без криптографии.

Ситуация: Сотрудник высказал жалобу по поводу деликатного вопроса Алисе, менеджеру компании, и попросил сохранить анонимность его личности. Некоторое время спустя Боб, другой менеджер, сказал Алисе, что кто-то пожаловался ему, также попросив сохранить конфеденциальность. Алиса и Боб хотят определить, был ли это один и тот же человек, без разглашения имен.

Чашки

Для этого способа требуется, чтобы кандидатов было не слишком много, допустим, двадцать. Алиса и Боб должны взять двадцать одинаковых контейнеров, например, одноразовые чашки, наклеить на каждую чашку этикетку с именем (по одной на кандидата). Алиса должна положить сложенный листок бумаги со словом «да» в чашку человека, который жаловался и листки со словом «нет» в остальные девятнадцать чашек. Боб должен сделать то же самое. Затем они должны снять этикетки и переставить чашки в случайном порядке. Если в одной из чашек два листка со словом «да», значит, им жаловался один и тот же человек.

Колода карт

Этот способ подходит для случаев, когда список кандидатов велик, либо не определён. Здесь используется тот факт, что количество игральных карт в обычной колоде вдвое превышает количество букв в латинском алфавите. Колоду из 52 карт нужно разделить по цветам на две колоды по 26 карт. Затем перемешать каждую колоду и положить на стол рубашкой вверх. Всего нужно проделать 26 итераций. На -й итерации Алиса снимает верхнюю карту с каждой колоды, складывает их лицом к лицу, и переворачивает так, чтобы карта из красной колоды была сверху. Дальше она прячет карты за спину и переворачивает, если в имени сотрудника, который жаловался, есть -я буква в алфавите. После этого она должна дать карты Бобу, который также должен спрятать карты за спину, перевернуть, если в имени есть -я буква и затем положить на стол. Процедуру нужно повторить ещё  раз. После этого карты нужно сложить в одну стопку и перемешать. Красная карта лицом вверх сигнализирует о том, что секреты не совпадают.

Криптографическое решение 

Исходные данные
  — большое простое число, по модулю которого производятся все вычисления
 , секреты Алисы и Боба соответственно
 - первый генератор
Требуется выяснить, совпадают ли секреты Алисы и Боба, .Создание генераторов
 Алиса выбирает число , Боб выбирает . Затем они обмениваются и (проверив, что они не равны 1) и оба вычисляют (вычисления ведутся по модую , т.е  = ).
 После этого они повторяют процедуру, генерируя новые , обмениваясь и (проверив, что они не равны 1) и вычисляя .
  и  требуется запомнить для дальнейшего использования.
«Упаковка»  и 
 Алиса выбирает , вычисляет  и . Боб выбирает , вычисляет  и . Происходит обмен .
Проверка 
 Алиса вычисляет , Боб вычисляет , они обмениваются этими значениями и вычисляют .
 В данный момент обе стороны знают, что .
 То есть для того чтобы проверить , нужно проверить

Особенности реализации в OTR 
В OTR используется 1536-битная группа, описанная в RFC 3526, также известная как группа Диффи-Хеллмана 5. Для безопасности сравниваются SHA-256 хеш от идентификатора сессии, отпечатки открытого ключа обеих сторон и оригинальные секреты Алисы и Боба.

Безопасность 
Безопасность протокола основывается на стандартных предположениях в криптографии:
 DL (discrete logarithm, дискретное логарифмирование) предположение для группы  состоящее в том, что  ,  невозможно вычислить за разумное время.
 DH (Diffie-Hellman) предположение для группы  состоящее в том, что невозможно вычислить , зная  для произвольных .
 DDH (decisional Diffie-Hellman) предположение для группы  состоящее в том, что невозможно определить  (что эквивалентно ) зная  для произвольных .

См. также 
 Протокол конфиденциального вычисления
 Off-the-Record Messaging
 Атака посредника
 Протокол Диффи — Хеллмана
 Доказательство с нулевым разглашением

Примечания

Ссылки 
 Описание протокола OTR
 Подборка статей о задаче миллионеров-социалистов
 Группы Диффи-Хеллмана 

Криптография