Socialistický problém milionáře - Socialist millionaire problem

v kryptografie, problém socialistického milionáře^[1] je ten, ve kterém dva milionáři chtějí zjistit, zda je jejich bohatství stejné, aniž by si navzájem sdělovali jakékoli informace o svém bohatství. Jedná se o variantu Milionářův problém^[2]^[3] přičemž dva milionáři si přejí porovnat své bohatství a určit, kdo má největší bohatství, aniž by si navzájem sdělovali jakékoli informace o svém bohatství.

Často se používá jako kryptografický protokol který umožňuje dvěma stranám ověřit identitu vzdálené strany pomocí sdíleného tajemství a vyhnout se útoku typu man-in-the-middle bez nepříjemností ručního porovnávání otisků prstů veřejného klíče prostřednictvím vnějšího kanálu. Ve skutečnosti lze použít relativně slabé heslo / přístupové heslo v přirozeném jazyce.

Motivace

Alice a Bob mají tajné hodnoty ${displaystyle x}$ a ${displaystyle y}$ , resp. Alice a Bob si přejí zjistit, jestli ${displaystyle x = y}$ aniž by jedné ze stran umožnilo dozvědět se něco jiného o tajné hodnotě toho druhého.

Pasivní útočník jednoduše špehuje zprávy, které si Alice a Bob vymění, se nic nedozví ${displaystyle x}$ a ${displaystyle y}$ , ani zda ${displaystyle x = y}$ .

I když je jedna ze stran nepoctivá a odchyluje se od protokolu, tato osoba se nemůže naučit nic víc, než kdyby ${displaystyle x = y}$ .

Aktivní útočník schopný svévolně zasahovat do komunikace Alice a Boba (a muž uprostřed ) se nemůže naučit víc než pasivní útočník a nemůže ovlivnit výsledek protokolu jinak, než aby selhal.

Proto lze protokol použít k ověření, zda mají dvě strany stejné tajné informace. Populární balíček kryptografie okamžitých zpráv Zprávy mimo záznam používá k ověření protokol Socialist Millionaire, ve kterém jsou tajemství ${displaystyle x}$ a ${displaystyle y}$ obsahují informace o veřejných klíčích dlouhodobé autentizace obou stran a také informace zadané samotnými uživateli.

Protokol pro zasílání zpráv mimo záznam

Státní stroj implementace socialistického milionářského protokolu (SMP).

Protokol je založen na teorie skupin.

Skupina nejlepších objednat ${displaystyle p}$ a generátor ${displaystyle h}$ jsou dohodnuty a priori, a v praxi jsou obecně stanoveny v dané implementaci. Například v protokolu Off-the-Record Messaging ${displaystyle p}$ je specifický pevný 1 536bitový prime. ${displaystyle h}$ je pak generátor podskupiny prvotřídního řádu ${displaystyle (mathbb {Z} / pmathbb {Z}) ^ {*}}$ a všechny operace jsou prováděny modulo ${displaystyle p}$ , nebo jinými slovy, v podskupině multiplikativní skupina, ${displaystyle (mathbb {Z} / pmathbb {Z}) ^ {*}}$ .

Podle ${displaystyle langle h | a ,, bangle}$ , označují bezpečný výpočet více stran, Výměna klíčů Diffie – Hellman – Merkle, která pro celá čísla ${displaystyle a}$ , ${displaystyle b}$ , se vrací ${displaystyle h ^ {ab}}$ každé straně:

Alice počítá ${displaystyle h ^ {a}}$ a pošle ji Bobovi, který poté vypočítá ${displaystyle left (h ^ {a} ight) ^ {b} ekvivalent h ^ {ab}}$ .
Bob počítá ${displaystyle h ^ {b}}$ a pošle ji Alici, která poté vypočítá ${displaystyle left (h ^ {b} ight) ^ {a} ekvivalent h ^ {ba}}$ .

${displaystyle h ^ {ab} ekviv h ^ {ba}}$ jako násobení v ${displaystyle (mathbb {Z} / pmathbb {Z}) ^ {*}}$ je asociativní. Všimněte si, že tento postup je nejistý proti muž uprostřed útoky.

Socialistický milionářský protokol^[4] má pouze několik kroků, které nejsou součástí výše uvedeného postupu, a bezpečnost každého z nich závisí na obtížnosti diskrétní logaritmus problém, stejně jako výše uvedené. Všechny odeslané hodnoty také obsahují důkazy nulové znalosti, že byly vygenerovány podle protokolu.

Část zabezpečení se také spoléhá na náhodná tajemství. Jak je však uvedeno níže, protokol je náchylný k otravě, pokud si Alice nebo Bob zvolí některou z možností ${displaystyle a}$ , ${displaystyle b}$ , ${displaystyle alpha}$ nebo ${displaystyle eta}$ být nula. Aby bylo možné tento problém vyřešit, musí každá strana zkontrolovat během Diffie-Hellman výměny, které nikdo z ${displaystyle h ^ {a}}$ , ${displaystyle h ^ {b}}$ , ${displaystyle h ^ {alpha}}$ nebo ${displaystyle h ^ {eta}}$ které dostávají, se rovná 1. Je také nutné zkontrolovat, že ${displaystyle P_ {a} eq P_ {b}}$ a ${displaystyle Q_ {a} eq Q_ {b}}$ .

	Alice	Multiparty	Bob
1	Zpráva ${displaystyle x}$ Náhodný ${displaystyle a, alfa, r}$	Veřejnost ${displaystyle p, h}$	Zpráva ${displaystyle y}$ Náhodný ${displaystyle b, eta, s}$
2		Zajistit ${displaystyle g = langle h \| a, bangle}$
3		Zajistit ${displaystyle gamma = langle h \| alpha, eta angle}$
4	Test ${displaystyle h ^ {b} ekv. 1}$ , ${displaystyle h ^ {eta} ekv. 1}$		Test ${displaystyle h ^ {a} eq 1}$ , ${displaystyle h ^ {alpha} eq 1}$
5	${displaystyle {egin {aligned} P_ {a} & = gamma ^ {r} Q_ {a} & = h ^ {r} g ^ {x} end {aligned}}}$		${displaystyle {egin {aligned} P_ {b} & = gamma ^ {s} Q_ {b} & = h ^ {s} g ^ {y} end {aligned}}}$
6		Nejistá výměna ${displaystyle P_ {a}, Q_ {a}, P_ {b}, Q_ {b}}$
7		Zajistit ${displaystyle c = leftlangle left.Q_ {a} Q_ {b} ^ {- 1} ight \| alpha, eta ightangle}$
8	Test ${displaystyle P_ {a} eq P_ {b}}$ , ${displaystyle Q_ {a} eq Q_ {b}}$		Test ${displaystyle P_ {a} eq P_ {b}}$ , ${displaystyle Q_ {a} eq Q_ {b}}$
9	Test ${displaystyle c = P_ {a} {P_ {b}} ^ {- 1}}$		Test ${displaystyle c = P_ {a} {P_ {b}} ^ {- 1}}$

Všimněte si, že:

{displaystyle {egin {aligned} P_ {a} {P_ {b}} ^ {- 1} & = gamma ^ {r} gamma ^ {- s} = gamma ^ {rs} & = h ^ {alpha eta ( rs)} konec {zarovnáno}}}

a proto

{displaystyle {egin {aligned} c & = left (Q_ {a} Q_ {b} ^ {- 1} ight) ^ {alpha eta} & = left (h ^ {r} g ^ {x} h ^ {- s} g ^ {- y} ight) ^ {alpha eta} = vlevo (h ^ {rs} g ^ {xy} ight) ^ {alpha eta} & = vlevo (h ^ {rs} h ^ {ab ( xy)} ight) ^ {alpha eta} = h ^ {alpha eta (rs)} h ^ {alpha eta ab (xy)} & = vlevo (P_ {a} {P_ {b}} ^ {- 1} ight) h ^ {alpha eta ab (xy)} end {aligned}}}

.

Kvůli náhodným hodnotám uloženým v tajnosti druhou stranou nemůže žádná strana vynutit ${displaystyle c}$ a ${displaystyle P_ {a} {P_ {b}} ^ {- 1}}$ být si rovni, pokud ${displaystyle x}$ rovná se ${displaystyle y}$ , v jakém případě ${displaystyle h ^ {alpha eta ab (x-y)} = h ^ {0} = 1}$ . To dokazuje správnost.

Viz také

Důkaz nulových znalostí

Reference

^ Markus Jakobsson, Moti Yung (1996). „Dokazování bez vědomí: Na zapomnětlivých, agnostických a se zavázanýma očima.“. Pokroky v kryptologii - CRYPTO '96, svazek 1109 přednášek v informatice. Berlín. str. 186–200. doi:10.1007/3-540-68697-5_15.
^ Andrew Yao (1982). „Protokoly pro bezpečnou komunikaci“ (PDF). Proc. 23. IEEE Symposium on Foundations of Computer Science (FOCS '82). 160–164. doi:10.1109 / SFCS.1982,88.
^ Andrew Yao (1986). „Jak generovat a vyměňovat tajemství“ (PDF). Proc. 27. IEEE Symposium on Foundations of Computer Science (FOCS '86). 162–167. doi:10.1109 / SFCS.1986.25.
^ Fabrice Boudot, Berry Schoenmakers, Jacques Traoré (2001). „Spravedlivé a efektivní řešení problému socialistických milionářů“ (PDF). Diskrétní aplikovaná matematika. 111 (1): 23–36. doi:10.1016 / S0166-218X (00) 00342-5.CS1 maint: více jmen: seznam autorů (odkaz)

externí odkazy

[socialist-millionaire-problem-1] Markus Jakobsson, Moti Yung (1996). „Dokazování bez vědomí: Na zapomnětlivých, agnostických a se zavázanýma očima.“. Pokroky v kryptologii - CRYPTO '96, svazek 1109 přednášek v informatice. Berlín. str. 186–200. doi:10.1007/3-540-68697-5_15.

[millionaires-problem-2] Andrew Yao (1982). „Protokoly pro bezpečnou komunikaci“ (PDF). Proc. 23. IEEE Symposium on Foundations of Computer Science (FOCS '82). 160–164. doi:10.1109 / SFCS.1982,88.

[how-to-generate-secrets-3] Andrew Yao (1986). „Jak generovat a vyměňovat tajemství“ (PDF). Proc. 27. IEEE Symposium on Foundations of Computer Science (FOCS '86). 162–167. doi:10.1109 / SFCS.1986.25.

[socialist-millionaire-protocol-4] Fabrice Boudot, Berry Schoenmakers, Jacques Traoré (2001). „Spravedlivé a efektivní řešení problému socialistických milionářů“ (PDF). Diskrétní aplikovaná matematika. 111 (1): 23–36. doi:10.1016 / S0166-218X (00) 00342-5.CS1 maint: více jmen: seznam autorů (odkaz)

[1]

[2]

[3]

[4]