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

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

История править

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

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

Свойства править

Алиса и Боб знают секреты $x$ и $y$ соответственно.

Свойства, которые должны присутствовать в протоколе взаимодействия^[5]:

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

Решение без криптографии править

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

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

Чашки

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

Колода карт

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

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

Протокол миллионеров-социалистов в OTR

Исходные данные

$q$ — большое простое число, по модулю которого производятся все вычисления
$x,y$ , секреты Алисы и Боба соответственно
$g_{1}$ - первый генератор

Требуется выяснить, совпадают ли секреты Алисы и Боба, $x=y$ .

Аутентификация по секретному ключу в Pidgin

Создание генераторов

Алиса выбирает число $a_{2}$ , Боб выбирает $b_{2}$ . Затем они обмениваются $g_{1}^{a_{2}}$ и $g_{1}^{b_{2}}$ (проверив, что они не равны 1) и оба вычисляют $g_{2}=g_{1}^{a_{2}b_{2}}$ (вычисления ведутся по модую $q$ , т.е $g_{2}$ = $g_{1}^{a_{2}}{\bmod {q}}$ ).
После этого они повторяют процедуру, генерируя новые $a_{3},b_{3}$ , обмениваясь $g_{1}^{a_{3}}$ и $g_{1}^{b_{3}}$ (проверив, что они не равны 1) и вычисляя $g_{3}=g_{1}^{a_{3}b_{3}}$ .
$a_{3}$ и $b_{3}$ требуется запомнить для дальнейшего использования.

«Упаковка» $x$ и $y$

Алиса выбирает $a$ , вычисляет $P_{a}=g_{3}^{a}$ и $Q_{a}=g_{1}^{a}g_{2}^{x}$ . Боб выбирает $b$ , вычисляет $P_{b}=g_{3}^{b}$ и $Q_{b}=g_{1}^{b}g_{2}^{y}$ . Происходит обмен $P_{a},Q_{a},P_{b},Q_{b}$ .

Проверка $x=y$

Алиса вычисляет $R_{a}={\Biggl (}{\frac {Q_{a}}{Q_{b}}}{\Biggr )}^{a_{3}}$ , Боб вычисляет $R_{b}={\Biggl (}{\frac {Q_{a}}{Q_{b}}}{\Biggr )}^{b_{3}}$ , они обмениваются этими значениями и вычисляют $R_{ab}=R_{a}^{b_{3}}=R_{b}^{a_{3}}$ .
В данный момент обе стороны знают, что $R_{ab}={\Biggl (}{\frac {Q_{a}}{Q_{b}}}{\Biggr )}^{a_{3}b_{3}}=(g_{1}^{a-b}g_{2}^{x-y})^{a_{3}b_{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}$ .
То есть для того чтобы проверить $x=y$ , нужно проверить $R_{ab}={\Biggl (}{\frac {P_{a}}{P_{b}}}{\Biggr )}$

Особенности реализации в OTR править

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

Безопасность править

Безопасность протокола основывается на стандартных предположениях в криптографии^[3]:

DL (discrete logarithm, дискретное логарифмирование) предположение для группы $G_{q}$ состоящее в том, что $\log _{q}y$ , $g,y\in G_{q},g\neq 1$ невозможно вычислить за разумное время.
DH (Diffie-Hellman) предположение для группы $G_{q}$ состоящее в том, что невозможно вычислить $g^{ab}$ , зная $g,g^{a},g^{b}$ для произвольных $a,b$ .
DDH (decisional Diffie-Hellman) предположение для группы $G_{q}$ состоящее в том, что невозможно определить $c=ab$ (что эквивалентно $g^{c}=g^{ab}$ ) зная $g,g^{a},g^{b},g^{c}$ для произвольных $a,b,c$ .

См. также править

Примечания править

↑ Andrew Chi-Chih Yao. Protocols for Secure Computations // Foundations of Computer Science. — 1982. Архивировано 8 августа 2017 года.
↑ Markus Jakobsson, Moti Yung. Proving without knowing: On oblivious, agnostic and blindfolded provers. // Advances in Cryptology—CRYPTO’96. — 1996. — С. 189. Архивировано 14 октября 2017 года.
↑ ¹ ² ³ Fabrice Boudot, Berry Schoenmakers, Jacques Traore. A Fair and Efficient Solution to the Socialist Millionaires’ Problem // Discrete Applied Mathematics. — 2001. — С. 3. Архивировано 22 сентября 2017 года.
↑ ¹ ² ³ Chris Alexander, Ian Goldberg. Improved User Authentication in Off-The-Record Messaging // Privacy in electronic society. — 2007. — С. 4, 5. Архивировано 29 октября 2017 года.
↑ ¹ ² ³ Ronald Fagin, Moni Naor, Peter Winkler. Comparing Information Without Leaking It // Communications of the ACM. — 1996. — С. 5, 10, 11. Архивировано 9 августа 2017 года.

Ссылки править

[1] Andrew Chi-Chih Yao. Protocols for Secure Computations // Foundations of Computer Science. — 1982. Архивировано 8 августа 2017 года.

[2] Markus Jakobsson, Moti Yung. Proving without knowing: On oblivious, agnostic and blindfolded provers. // Advances in Cryptology—CRYPTO’96. — 1996. — С. 189. Архивировано 14 октября 2017 года.

[:0-3] ¹ ² ³ Fabrice Boudot, Berry Schoenmakers, Jacques Traore. A Fair and Efficient Solution to the Socialist Millionaires’ Problem // Discrete Applied Mathematics. — 2001. — С. 3. Архивировано 22 сентября 2017 года.

[:1-4] ¹ ² ³ Chris Alexander, Ian Goldberg. Improved User Authentication in Off-The-Record Messaging // Privacy in electronic society. — 2007. — С. 4, 5. Архивировано 29 октября 2017 года.

[:2-5] ¹ ² ³ Ronald Fagin, Moni Naor, Peter Winkler. Comparing Information Without Leaking It // Communications of the ACM. — 1996. — С. 5, 10, 11. Архивировано 9 августа 2017 года.

[1]

[2]

[3]

[4]

[5]