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

В криптографии , то социалистическая проблема миллионера ^[1] является один , в котором два миллионеры хотят , чтобы определить , является ли их богатство равно без раскрытия информации о своих богатствах друг к другу. Это вариант проблемы миллионера ^[2]^[3], при которой два миллионера хотят сравнить свои богатства, чтобы определить, у кого больше всего богатства, не раскрывая друг другу никакой информации о своем богатстве.

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

Мотивация

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

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

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

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

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

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

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

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

Группа первичного порядка и генератор согласованы априори и на практике обычно фиксируются в данной реализации. Например, в протоколе обмена сообщениями без записи это конкретное фиксированное число размером 1536 бит. Затем генератор прайм порядка подгруппы , и все операции выполняются по модулю , или, другими словами, в подгруппе мультипликативной группы , . ${\ displaystyle p}$ $h$ $p$ $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} )^{*}$

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

Часть безопасности также полагается на случайные секреты. Однако, как написано ниже, протокол уязвим к отравлению , если Алиса или Боб выбирает любой из , , или равным нулю. Чтобы решить эту проблему, каждая сторона должна проверить во время Диффи-Хеллмана обмена , что ни один из , , , или , что они получают не равно 1. Кроме того , необходимо проверить , что и . $a$ $b$ $\alpha$ $\beta$ $h^{a}$ $h^{b}$ $h^{\alpha }$ $h^{\beta }$ $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$

Смотрите также

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

использованная литература

^ Маркус Якобссон , Моти Юнг (1996). «Доказательство без ведома: на испытателей, не обращающих внимания, агностиков и с завязанными глазами». . Достижения в криптологии - CRYPTO '96, том 1109 конспектов лекций по информатике . Берлин. С. 186–200. DOI : 10.1007 / 3-540-68697-5_15 .
↑ Эндрю Яо (1982). «Протоколы для безопасной связи» (PDF) . Proc. 23-й симпозиум IEEE по основам информатики (FOCS '82) . С. 160–164. DOI : 10.1109 / SFCS.1982.88 .
↑ Эндрю Яо (1986). «Как создавать и обмениваться секретами» (PDF) . Proc. 27-й симпозиум IEEE по основам информатики (FOCS '86) . С. 162–167. DOI : 10.1109 / SFCS.1986.25 .
^ Фабрис Boudot, Берри Schoenmakers, Жак Траоре (2001). «Справедливое и эффективное решение проблемы социалистических миллионеров» (PDF) . Дискретная прикладная математика . 111 (1): 23–36. DOI : 10.1016 / S0166-218X (00) 00342-5 . CS1 maint: несколько имен: список авторов ( ссылка )

внешняя ссылка

Описание протокола OTR-обмена сообщениями версии 2
Проблема социалистического миллионера - объясните, как будто мне пять
Goldbug Messenger, который использует реализацию протокола социалистического миллионера.

[socialist-millionaire-problem-1] Маркус Якобссон , Моти Юнг (1996). «Доказательство без ведома: на испытателей, не обращающих внимания, агностиков и с завязанными глазами». . Достижения в криптологии - CRYPTO '96, том 1109 конспектов лекций по информатике . Берлин. С. 186–200. DOI : 10.1007 / 3-540-68697-5_15 .

[millionaires-problem-2] Эндрю Яо (1982). «Протоколы для безопасной связи» (PDF) . Proc. 23-й симпозиум IEEE по основам информатики (FOCS '82) . С. 160–164. DOI : 10.1109 / SFCS.1982.88 .

[how-to-generate-secrets-3] Эндрю Яо (1986). «Как создавать и обмениваться секретами» (PDF) . Proc. 27-й симпозиум IEEE по основам информатики (FOCS '86) . С. 162–167. DOI : 10.1109 / SFCS.1986.25 .

[socialist-millionaire-protocol-4] Фабрис Boudot, Берри Schoenmakers, Жак Траоре (2001). «Справедливое и эффективное решение проблемы социалистических миллионеров» (PDF) . Дискретная прикладная математика . 111 (1): 23–36. DOI : 10.1016 / S0166-218X (00) 00342-5 . CS1 maint: несколько имен: список авторов ( ссылка )

[1]