Проблема социалистического миллионера

В криптографии миллионера проблема социалистического это тот, в котором два миллионера хотят определить, равно ли их богатство, не раскрывая друг другу никакой информации о своем богатстве. Это вариант проблемы миллионера. при этом два миллионера желают сравнить свое богатство, чтобы определить, у кого больше богатства, не раскрывая друг другу никакой информации о своем богатстве.

Он часто используется в качестве криптографического протокола , который позволяет двум сторонам проверять личность удаленной стороны посредством использования общего секрета, избегая атаки «человек посередине» без неудобств ручного сравнения отпечатков открытого ключа через внешний канал. По сути, можно использовать относительно слабый пароль/парольную фразу на естественном языке.

Мотивация

У Алисы и Боба есть тайные ценности $x$ и $y$, соответственно. Алиса и Боб хотят узнать, $x=y$ не позволяя ни одной из сторон узнать что-либо еще о тайной ценности другой стороны.

Пассивный злоумышленник, просто шпионящий за сообщениями, которыми обмениваются Алиса и Боб, ничего о них не узнает. $x$ и $y$даже если $x=y$.

Даже если одна из сторон нечестна и отклоняется от протокола, этот человек не сможет узнать ничего большего, чем если бы $x=y$.

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

Таким образом, протокол можно использовать для проверки подлинности двух сторон, имеющих одинаковую секретную информацию. Популярный пакет шифрования мгновенных сообщений Off-the-Record Messaging использует для аутентификации протокол Socialist Millionaire, в котором секреты $x$ и $y$ содержат информацию об открытых ключах долгосрочной аутентификации обеих сторон, а также информацию, введенную самими пользователями.

Протокол обмена сообщениями без записи

Основная статья: Неофициальные сообщения

Государственный аппарат реализации протокола социалистического миллионера (SMP).

Протокол основан на теории групп .

Группа простого порядка $p$ и генератор $h$ согласованы априори и на практике обычно фиксируются в данной реализации. Например, в протоколе обмена сообщениями без записи: $p$ представляет собой определенное фиксированное 1536-битное простое число. $h$ тогда является генератором подгруппы простого порядка группы $(\mathbb {Z} /p\mathbb {Z} )^{*}$, и все операции выполняются по модулю $p$или, другими словами, в подгруппе мультипликативной группы , $(\mathbb {Z} /p\mathbb {Z} )^{*}$.

К $\langle h|a,\,b\rangle$, обозначают безопасное многостороннее вычисление , обмен ключами Диффи-Хеллмана-Меркла , который для целых чисел $a$, $b$, возвращает $h^{ab}$ каждой стороне:

• Алиса вычисляет $h^{a}$ и отправляет его Бобу, который затем вычисляет $\left(h^{a}\right)^{b}\equiv h^{ab}$.
• Боб вычисляет $h^{b}$ и отправляет его Алисе, которая затем вычисляет $\left(h^{b}\right)^{a}\equiv h^{ba}$.

$h^{ab}\equiv h^{ba}$ как умножение в $(\mathbb {Z} /p\mathbb {Z} )^{*}$ является ассоциативным. Обратите внимание, что эта процедура небезопасна против атак «человек посередине» .

Протокол социалистического миллионера имеет только несколько шагов, которые не являются частью описанной выше процедуры, и безопасность каждого из них зависит от сложности задачи дискретного логарифмирования , как и вышеописанное. Все отправленные значения также включают доказательства с нулевым разглашением того, что они были сгенерированы в соответствии с протоколом.

Часть безопасности также опирается на случайные секреты. Однако, как написано ниже, протокол уязвим для отравления, если Алиса или Боб выберут любой из $a$, $b$, $\alpha$, или $\beta$ быть нулем. Чтобы решить эту проблему, каждая сторона должна проверить во время обмена сообщениями Диффи-Хеллмана , что ни один из $h^{a}$, $h^{b}$, $h^{\alpha }$, или $h^{\beta }$ которое они получают, равно 1. Также необходимо проверить, что $P_{a}\neq P_{b}$ и $Q_{a}\neq Q_{b}$.

	Алиса	Многопартийность	Боб
1	Сообщение $x$ случайный $a,\alpha ,r$	Общественный $p,h$	Сообщение $y$ случайный $b,\beta ,s$
2		Безопасный $g=\langle h|a,b\rangle$
3		Безопасный $\gamma =\langle h|\alpha ,\beta \rangle$
4	Тест $h^{b}\neq 1$, $h^{\beta }\neq 1$		Тест $h^{a}\neq 1$, $h^{\alpha }\neq 1$
5	${\begin{aligned}P_{a}&=\gamma ^{r}\\Q_{a}&=h^{r}g^{x}\end{aligned}}$		${\begin{aligned}P_{b}&=\gamma ^{s}\\Q_{b}&=h^{s}g^{y}\end{aligned}}$
6		Небезопасный обмен $P_{a},Q_{a},P_{b},Q_{b}$
7		Безопасный $c=\left\langle \left.Q_{a}Q_{b}^{-1}\right|\alpha ,\beta \right\rangle$
8	Тест $P_{a}\neq P_{b}$, $Q_{a}\neq Q_{b}$		Тест $P_{a}\neq P_{b}$, $Q_{a}\neq Q_{b}$
9	Тест $c=P_{a}{P_{b}}^{-1}$		Тест $c=P_{a}{P_{b}}^{-1}$

Обратите внимание, что:

${\begin{aligned}P_{a}{P_{b}}^{-1}&=\gamma ^{r}\gamma ^{-s}=\gamma ^{r-s}\\&=h^{\alpha \beta (r-s)}\end{aligned}}$

и поэтому

${\begin{aligned}c&=\left(Q_{a}Q_{b}^{-1}\right)^{\alpha \beta }\\&=\left(h^{r}g^{x}h^{-s}g^{-y}\right)^{\alpha \beta }=\left(h^{r-s}g^{x-y}\right)^{\alpha \beta }\\&=\left(h^{r-s}h^{ab(x-y)}\right)^{\alpha \beta }=h^{\alpha \beta (r-s)}h^{\alpha \beta ab(x-y)}\\&=\left(P_{a}{P_{b}}^{-1}\right)h^{\alpha \beta ab(x-y)}\end{aligned}}$.

Поскольку случайные значения хранятся в секрете другой стороной, ни одна из сторон не может принудительно $c$ и $P_{a}{P_{b}}^{-1}$ быть равным, если только $x$ равно $y$, в этом случае $h^{\alpha \beta ab(x-y)}=h^{0}=1$. Это доказывает правильность.

См. также

• Доказательство с нулевым разглашением

Внешние ссылки

• Описание протокола OTR-сообщений версии 2
• Объясните это так, как будто мне пять: проблема социалистического миллионера и безопасные многосторонние вычисления в Wayback Machine (архивировано 25 декабря 2022 г.)
• Goldbug Messenger, использующий реализацию протокола социалистического миллионера.