Русская Википедия:Задача миллионеров-социалистов
Задача миллионеров-социалистов (англ. Socialist Millionaires' Problem, SMP, Tierce problem) — криптографическая задача, в которой два миллионера хотят выяснить, равны ли их состояния, не разглашая точные суммы. Решение этой задачи используется в качестве криптографического протокола, который позволяет двум сторонам проверить подлинность удаленного участника с помощью общего секрета, избегая атаки «человек посередине», без необходимости сравнивать вручную отпечатки открытого ключа через другой канал.
История
Впервые задача безопасного многостороннего вычисления была поднята Эндрю Яо в 1982 году[1]. Два миллионера, Алиса и Боб, хотят выяснить, кто же из них богаче, при этом они не хотят разглашать точную сумму своего благосостояния. Яо предложил в своей статье оригинальный способ решения задачи, получившей впоследствии название «Шаблон:Нп5». В 1996 году в работе Маркуса Якобссона и Моти Юнга частный случай, в котором Алиса и Боб хотят выяснить, равны ли их состояния, был назван задачей миллионеров-социалистов[2]. Другой вариант названия — «Tierce problem» (tierce — французская игра на ставках): подразумевается, что два игрока хотят выяснить, одинаковая ли у них комбинация ставок[3].
Эффективное решение задачи миллионеров-социалистов было предложено в 2001 году в работе[3] Фабрис Будо, Берри Шонмейкерса и Жака Траоре[4]. Оно было реализовано в протоколе OTR (Off-the record), после того как в 2007 году Оливер Гоффарт опубликовал модуль mod_otr для сервера ejabberd, позволяющий автоматически проводить атаку типа «человек посередине» на пользователей OTR, не проверяющих отпечатки открытых ключей друг друга[4].
Свойства
Алиса и Боб знают секреты <math>x </math> и <math>y </math> соответственно.
Свойства, которые должны присутствовать в протоколе взаимодействия[5]:
- Отсутствие утечки информации: если предположить, что Алиса и Боб добросовестно следуют протоколу, они не должны знать ничего кроме того, совпадают их секреты или нет.
- Конфиденциальность: никто другой не должен узнать секреты Алисы и Боба. Активный злоумышленник, способный произвольно вмешиваться в общение Алисы и Боба, должен узнать не больше, чем пассивный злоумышленник.
- Безопасность: ни Алиса, ни Боб не должны быть обмануты. Если кто-то из них не следует протоколу, он по-прежнему должен узнать секрет собеседника только при совпадении <math>x </math> и <math>y </math>.
- Простота: протокол должен быть простым в реализации и понятным, то есть Алиса и Боб не должны тратить большое количество времени, энергии и денег, чтобы использовать протокол.
- Удаленность: Алиса и Боб не должны присутствовать физически в одном и том же месте, чтобы выяснить, совпадают ли секреты.
Решение без криптографии
Решение задачи может быть представлено в наглядном виде, без криптографии.
Ситуация: Сотрудник высказал жалобу по поводу деликатного вопроса Алисе, менеджеру компании, и попросил сохранить анонимность его личности. Некоторое время спустя Боб, другой менеджер, сказал Алисе, что кто-то пожаловался ему, также попросив сохранить конфеденциальность. Алиса и Боб хотят определить, был ли это один и тот же человек, без разглашения имен.
Чашки
Для этого способа требуется, чтобы кандидатов было не слишком много, допустим, двадцать. Алиса и Боб должны взять двадцать одинаковых контейнеров, например, одноразовые чашки, наклеить на каждую чашку этикетку с именем (по одной на кандидата). Алиса должна положить сложенный листок бумаги со словом «да» в чашку человека, который жаловался и листки со словом «нет» в остальные девятнадцать чашек. Боб должен сделать то же самое. Затем они должны снять этикетки и переставить чашки в случайном порядке. Если в одной из чашек два листка со словом «да», значит, им жаловался один и тот же человек[5].
Колода карт
Этот способ подходит для случаев, когда список кандидатов велик, либо не определён. Здесь используется тот факт, что количество игральных карт в обычной колоде вдвое превышает количество букв в латинском алфавите. Колоду из 52 карт нужно разделить по цветам на две колоды по 26 карт. Затем перемешать каждую колоду и положить на стол рубашкой вверх. Всего нужно проделать 26 итераций. На <math>i</math>-й итерации Алиса снимает верхнюю карту с каждой колоды, складывает их лицом к лицу, и переворачивает так, чтобы карта из красной колоды была сверху. Дальше она прячет карты за спину и переворачивает, если в имени сотрудника, который жаловался, есть <math>i</math>-я буква в алфавите. После этого она должна дать карты Бобу, который также должен спрятать карты за спину, перевернуть, если в имени есть <math>i</math>-я буква и затем положить на стол. Процедуру нужно повторить ещё <math>26-i</math> раз. После этого карты нужно сложить в одну стопку и перемешать. Красная карта лицом вверх сигнализирует о том, что секреты не совпадают[5].
Криптографическое решение
Исходные данные
- <math>q</math> — большое простое число, по модулю которого производятся все вычисления
- <math>x, y </math>, секреты Алисы и Боба соответственно
- <math>g_1</math>- первый генератор
Требуется выяснить, совпадают ли секреты Алисы и Боба, <math>x = y </math>.
Создание генераторов
- Алиса выбирает число <math>a_2</math>, Боб выбирает <math>b_2 </math>. Затем они обмениваются <math>g_1^{a_2}</math>и <math>g_1^{b_2}</math>(проверив, что они не равны 1) и оба вычисляют <math> g_2= g_1^{a_2 b_2}</math>(вычисления ведутся по модую <math>q</math>, т.е <math>g_2</math> = <math>g_1^{a_2} \bmod q</math>).
- После этого они повторяют процедуру, генерируя новые <math>a_3, b_3</math>, обмениваясь <math>g_1^{a_3}</math>и <math>g_1^{b_3}</math>(проверив, что они не равны 1) и вычисляя <math>g_3=g_1^{a_3 b_3}</math>.
- <math>a_3</math> и <math>b_3</math> требуется запомнить для дальнейшего использования.
«Упаковка» <math>x </math> и <math>y </math>
- Алиса выбирает <math>a</math>, вычисляет <math>P_a = g_3^a </math> и <math>Q_a = g_1^ag_2^x </math>. Боб выбирает <math>b</math>, вычисляет <math>P_b = g_3^b </math> и <math>Q_b = g_1^b g_2^y </math>. Происходит обмен <math>P_a, Q_a, P_b, Q_b </math>.
Проверка <math>x = y </math>
- Алиса вычисляет <math>R_a = \Biggl(\frac{Q_a}{Q_b}\Biggr)^{a_3} </math>, Боб вычисляет <math>R_b = \Biggl(\frac{Q_a}{Q_b}\Biggr)^{b_3} </math>, они обмениваются этими значениями и вычисляют <math>R_{ab} = R_a^{b_3} = R_b^{a_3} </math>.
- В данный момент обе стороны знают, что <math>R_{ab} = \Biggl(\frac{Q_a}{Q_b}\Biggr)^{a_3 b_3} = (g_1^{a-b}g_2^{x-y})^{a_3b_3} = g_3^{a-b}g_2^{(x-y)a_3 b_3} = \Biggl(\frac{P_a}{P_b}\Biggr)(g_2^{a_3 b_3})^{x-y} </math>.
- То есть для того чтобы проверить <math>x = y </math>, нужно проверить <math>R_{ab} = \Biggl(\frac{P_a}{P_b}\Biggr) </math>
Особенности реализации в OTR
В OTR используется 1536-битная группа, описанная в RFC 3526, также известная как группа Диффи-Хеллмана 5. Для безопасности сравниваются SHA-256 хеш от идентификатора сессии, отпечатки открытого ключа обеих сторон и оригинальные секреты Алисы и Боба[4].
Безопасность
Безопасность протокола основывается на стандартных предположениях в криптографии[3]:
- DL (discrete logarithm, дискретное логарифмирование) предположение для группы <math>G_q</math> состоящее в том, что <math>\log_{q} y</math> , <math>g,y \in G_q, g \neq 1</math> невозможно вычислить за разумное время.
- DH (Diffie-Hellman) предположение для группы <math>G_q</math> состоящее в том, что невозможно вычислить <math>g^{ab}</math>, зная <math>g, g^a, g^b</math> для произвольных <math>a,b
</math>.
- DDH (decisional Diffie-Hellman) предположение для группы <math>G_q</math> состоящее в том, что невозможно определить <math>c = ab
</math> (что эквивалентно <math>g^c = g^{ab} </math>) зная <math>g, g^a, g^b, g^c</math> для произвольных <math>a,b,c </math>.
См. также
- Протокол конфиденциального вычисления
- Off-the-Record Messaging
- Атака посредника
- Протокол Диффи — Хеллмана
- Доказательство с нулевым разглашением
Примечания
Ссылки
