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

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

== История ==
Впервые задача [[Протокол конфиденциального вычисления|безопасного многостороннего вычисления]] была поднята [[Эндрю Яо]] в 1982 году<ref>{{Статья|автор=Andrew Chi-Chih Yao|заглавие=Protocols for Secure Computations|ссылка=https://research.cs.wisc.edu/areas/sec/yao1982-ocr.pdf|язык=|издание=Foundations of Computer Science|тип=|год=1982|месяц=|число=|том=|номер=|страницы=|issn=|archivedate=2017-08-08|archiveurl=https://web.archive.org/web/20170808212631/http://research.cs.wisc.edu/areas/sec/yao1982-ocr.pdf}}</ref>. Два миллионера, Алиса и Боб, хотят выяснить, кто же из них богаче, при этом они не хотят разглашать точную сумму своего благосостояния. Яо предложил в своей статье оригинальный способ решения задачи, получившей впоследствии название «{{нп5|Задача миллионеров Яо|Задача миллионеров Яо|en|Yao's Millionaires' Problem}}». В 1996 году в работе Маркуса Якобссона и Моти Юнга частный случай, в котором Алиса и Боб хотят выяснить, равны ли их состояния, был назван задачей миллионеров-социалистов<ref>{{Статья|автор=Markus  Jakobsson, Moti Yung|заглавие=Proving without knowing: On oblivious, agnostic and blindfolded provers.|ссылка=https://link.springer.com/content/pdf/10.1007%2F3-540-68697-5_15.pdf|язык=|издание=Advances in Cryptology—CRYPTO’96|тип=|год=1996|месяц=|число=|том=|номер=|страницы=189|issn=|archivedate=2017-10-14|archiveurl=https://web.archive.org/web/20171014183459/https://link.springer.com/content/pdf/10.1007%2F3-540-68697-5_15.pdf}}</ref>. Другой вариант названия — «Tierce problem» (tierce — французская игра на ставках): подразумевается, что два игрока хотят выяснить, одинаковая ли у них комбинация ставок<ref name=":0">{{Статья|автор=Fabrice Boudot, Berry Schoenmakers, Jacques Traore|заглавие=A Fair and Efficient Solution to the Socialist Millionaires’ Problem|ссылка=https://www.win.tue.nl/~berry/papers/dam.pdf|язык=|издание=Discrete Applied Mathematics|тип=|год=2001|месяц=|число=|том=|номер=|страницы=3|issn=|archivedate=2017-09-22|archiveurl=https://web.archive.org/web/20170922220706/http://www.win.tue.nl/~berry/papers/dam.pdf}}</ref>.

Эффективное решение задачи миллионеров-социалистов было предложено в 2001 году в работе<ref name=":0" /> Фабрис Будо, Берри Шонмейкерса и Жака Траоре<ref name=":1" />. Оно было реализовано в протоколе [[Off-the-Record Messaging|OTR]] (Off-the record), после того как в 2007 году Оливер Гоффарт опубликовал модуль <code>mod_otr</code> для сервера [[ejabberd]], позволяющий автоматически проводить атаку типа «[[человек посередине]]» на пользователей OTR, не проверяющих отпечатки открытых ключей друг друга<ref name=":1">{{Статья|автор=Chris Alexander, Ian Goldberg|заглавие=Improved User Authentication in Off-The-Record Messaging|ссылка=http://www.cypherpunks.ca/~iang/pubs/impauth.pdf|язык=|издание=Privacy in electronic society|тип=|год=2007|месяц=|число=|том=|номер=|страницы=4, 5|issn=|archivedate=2017-10-29|archiveurl=https://web.archive.org/web/20171029172344/http://www.cypherpunks.ca/~iang/pubs/impauth.pdf}}</ref>.

== Свойства ==
Алиса и Боб знают секреты <math>x </math> и <math>y </math> соответственно.

Свойства, которые должны присутствовать в протоколе взаимодействия<ref name=":2">{{Статья|автор=Ronald Fagin, Moni Naor, Peter Winkler|заглавие=Comparing Information Without Leaking It|ссылка=https://www.stat.berkeley.edu/~aldous/157/Papers/fagin.pdf|язык=|издание=Communications of the ACM|тип=|год=1996|месяц=|число=|том=|номер=|страницы=5, 10, 11|issn=|archivedate=2017-08-09|archiveurl=https://web.archive.org/web/20170809093339/https://www.stat.berkeley.edu/~aldous/157/Papers/fagin.pdf}}</ref>:
* Отсутствие утечки информации: если предположить, что Алиса и Боб добросовестно следуют протоколу, они не должны знать ничего кроме того, совпадают их секреты или нет.
* Конфиденциальность: никто другой не должен узнать секреты Алисы и Боба. Активный злоумышленник, способный произвольно вмешиваться в общение Алисы и Боба, должен узнать не больше, чем пассивный злоумышленник.
* Безопасность: ни Алиса, ни Боб не должны быть обмануты. Если кто-то из них не следует протоколу, он по-прежнему должен узнать секрет собеседника только при совпадении <math>x </math> и <math>y </math>.
* Простота: протокол должен быть простым в реализации и понятным, то есть Алиса и Боб не должны тратить большое количество времени, энергии и денег, чтобы использовать протокол.
* Удаленность: Алиса и Боб не должны присутствовать физически в одном и том же месте, чтобы выяснить, совпадают ли секреты.

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

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

'''Чашки'''

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

'''Колода карт'''

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

== Криптографическое решение ==
[[Файл:SMP in OTR fixed Qb.png|мини|354x354пкс|
Протокол миллионеров-социалистов в OTR
]]
'''Исходные данные'''
* <math>q</math> — большое [[Простое число|простое]] число, [[Деление с остатком|по модулю]] которого производятся все вычисления
* <math>x, y </math>, секреты Алисы и Боба соответственно
* <math>g_1</math>- первый генератор
Требуется выяснить, совпадают ли секреты Алисы и Боба, <math>x = y  </math>.[[Файл:Shared secret.png|мини|347x347пкс| Аутентификация по секретному ключу в Pidgin ]]'''Создание генераторов'''
* Алиса выбирает число <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 ===
В [[Off-the-Record Messaging|OTR]] используется 1536-битная [[Группа (математика)|группа]], описанная в <nowiki>RFC 3526</nowiki>, также известная как группа Диффи-Хеллмана 5. Для безопасности сравниваются SHA-256 [[Хеширование|хеш]] от идентификатора сессии, [[Отпечаток открытого ключа|отпечатки открытого ключа]] обеих сторон и оригинальные секреты Алисы и Боба<ref name=":1" />.

=== Безопасность ===
Безопасность протокола основывается на стандартных предположениях в криптографии<ref name=":0" />:
* DL (discrete logarithm, [[дискретное логарифмирование]]) предположение для группы <math>G_q</math> состоящее в том, что <math>\log_{q} y</math> , <math>g,y \in G_q, g \neq 1</math> невозможно вычислить за разумное время.
* DH ([[:en:Diffie–Hellman problem|Diffie-Hellman]]) предположение для группы <math>G_q</math> состоящее в том, что невозможно вычислить <math>g^{ab}</math>, зная <math>g, g^a, g^b</math> для произвольных <math>a,b
</math>.
* DDH ([[:en:Decisional Diffie–Hellman assumption|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]]
* [[Атака посредника]]
* [[Протокол Диффи — Хеллмана]]
* [[Доказательство с нулевым разглашением]]

== Примечания ==
{{примечания|2}}

== Ссылки ==
* [https://otr.cypherpunks.ca/Protocol-v3-4.1.1.html Описание протокола OTR]
* [https://web.archive.org/web/20170923194952/http://kodu.ut.ee/~lipmaa/crypto/link/zeroknowledge/pok.php Подборка статей о задаче миллионеров-социалистов]
* [http://www.ietf.org/rfc/rfc3526.txt Группы Диффи-Хеллмана] 

[[Категория:Криптография]]
{{Добротная статья|Теория информации и криптография}}