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

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

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

Мотивация

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

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

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

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

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

Протокол обмена сообщениями «не для печати»

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

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

Группа простого порядка и генератор согласуются априори и на практике обычно фиксируются в данной реализации. Например, в протоколе Off-the-Record Messaging — это определенное фиксированное простое число размером 1536 бит. — это генератор подгруппы простого порядка , и все операции выполняются по модулю , или, другими словами, в подгруппе мультипликативной группы , . п {\displaystyle p} час {\displaystyle ч} п {\displaystyle p} час {\displaystyle ч} ( З / п З ) ∗ {\displaystyle (\mathbb {Z} /p\mathbb {Z})^{*}} п {\displaystyle p} ( З / п З ) ∗ {\displaystyle (\mathbb {Z} /p\mathbb {Z})^{*}}

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

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

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

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

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

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

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

P a P b − 1 = γ r γ − s = γ r − s = h α β ( r − s ) {\displaystyle {\begin{aligned}P_{a}{P_{b}}^{-1}&=\gamma ^{r}\gamma ^{-s}=\gamma ^{r-s}\\&=h^{\alpha \beta (r-s)}\end{aligned}}}

и поэтому

c = ( Q a Q b − 1 ) α β = ( h r g x h − s g − y ) α β = ( h r − s g x − y ) α β = ( h r − s h a b ( x − y ) ) α β = h α β ( r − s ) h α β a b ( x − y ) = ( P a P b − 1 ) h α β a b ( x − y ) {\displaystyle {\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 {\displaystyle c} P a P b − 1 {\displaystyle P_{a}{P_{b}}^{-1}} x {\displaystyle x} y {\displaystyle y} h α β a b ( x − y ) = h 0 = 1 {\displaystyle h^{\alpha \beta ab(x-y)}=h^{0}=1}

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

Ссылки

  1. ^ Маркус Якобссон , Моти Юнг (1996). «Доказательство без знания: о забывчивых, агностических и слепых доказывающих». Достижения в криптологии – CRYPTO '96, том 1109 Lecture Notes in Computer Science . Берлин. стр.  186–200 . doi : 10.1007/3-540-68697-5_15 .
  2. ^ Эндрю Яо (1982). «Протоколы для безопасной связи» (PDF) . Труды 23-го симпозиума IEEE по основам компьютерной науки (FOCS '82) . стр.  160–164 . doi :10.1109/SFCS.1982.88.
  3. ^ Эндрю Яо (1986). «Как генерировать и обмениваться секретами» (PDF) . Труды 27-го симпозиума IEEE по основам компьютерной науки (FOCS '86) . стр.  162–167 . doi :10.1109/SFCS.1986.25.
  4. ^ Фабрис Будо, Берри Шёнмейкерс, Жак Траоре (2001). «Справедливое и эффективное решение проблемы социалистических миллионеров» (PDF) . Дискретная прикладная математика . 111 (1): 23– 36. doi :10.1016/S0166-218X(00)00342-5.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  • Описание протокола OTR-Messaging версии 2
  • Объясни это так, будто мне пять: Социалистическая задача миллионера и безопасные многопартийные вычисления на Wayback Machine (архивировано 25 декабря 2022 г.)
  • Goldbug Messenger, который использует реализацию Socialist Millionaire Protocol
Retrieved from "https://en.wikipedia.org/w/index.php?title=Socialist_millionaire_problem&oldid=1236458824"