Transfer utajniony

Transfer utajniony^[1] (ang. oblivious transfer, OT) – typ protokołu w kryptografii, w którym nadawca wysyła jeden z potencjalnie wielu elementów informacji do odbiorcy, ale nie wie, który element (jeśli którykolwiek) został dostarczony.

Pierwsze wzmianki o transferze utajnionym zostały wprowadzone w 1981 roku przez Michaela O. Rabina^[2].

Prace Szimona Ewena, Odeda Goldreicha i Awrahama Lempela^[3] doprowadziły do stworzenia nowej wersji protokołu nazywanej transferem utajnionym "1 z 2". Claude Crépeau udowodnił równoważność transferu utajnionego Rabina z transferem utajnionym "1 z 2"^[4]. Uogólnieniem tego modelu jest transfer utajniony "1 z n", w którym odbiorca otrzymuje dokładnie jedną spośród n wiadomości, które posiada nadawca. Nadawca nie wie, którą wiadomość otrzymał odbiorca, a odbiorca nie może odczytać żadnej innej wiadomości poza ta, którą wcześniej wybrał.

Transfer utajniony Rabina edytuj

W wersji Rabina nadawca generuje dwie duże liczby pierwsze p oraz q. Następnie obliczana jest wartość N = p*q, liczona jest wartość funkcji Eulera dla N: φ(N) = (p-1)(q-1) i wybierana liczba e względnie pierwsza z φ(N). Następnie nadawca szyfruje wiadomość m jako m^e mod N.

Alicja				Bob
Prywatne	Publiczne	Opis		Prywatne	Publiczne	Opis
m		Wiadomość, która ma być wysłana.
p, q		Wygeneruj dwie liczby pierwsze.
	N = pq, e t.że NWD(e, φ(N)) = 1*	Wygeneruj kod publiczny (N, e) i wyślij go do Boba.	$\Rightarrow$		N, e	Odbierz klucz publiczny.
C = m^e mod N		Zaszyfruj wiadomość m i wyślij ją do Boba.	$\Rightarrow$		C	Odbierz kryptogram wiadomości m.
				x		Wybierz losową liczbę x mod N.
	a	Odbierz a.	$\Leftarrow$		a = x² mod N	Wyślij a do Alicji.
	y	Oblicz pierwiastki kwadratowe a, wybierz spośród nich jeden (y) i wyślij go do Boba.	$\Rightarrow$		y	Odbierz y.
						Sprawdź, czy y² = a mod N. Jeśli y ≠ ±x mod N, to za pomocą x i y rozszyfruj kryptogram C, aby uzyskać m.

Nadawca wysyła do odbiorcy klucz publiczny (N, e) oraz zaszyfrowaną wiadomość m^e mod N.
Odbiorca wybiera losową liczbę x mod N i wysyła do nadawcy wartość x² mod N.
Nadawca znajduje cztery pierwiastki kwadratowe x² mod N.
Nadawca wybiera dowolny pierwiastek y i wysyła go do odbiorcy.
Jeśli y jest różny od x i -x mod N, to odbiorca jest w stanie rozłożyć N na czynniki, a zatem może rozszyfrować m^e , aby uzyskać wiadomość m. Jeśli y jest równy x lub -x mod N, to odbiorca nie ma żadnych informacji o m poza jej kryptogramem m^e mod N.

Ponieważ x² mod N ma cztery pierwiastki kwadratowe, prawdopodobieństwo tego, że odbiorca odszyfruje wiadomość m wynosi ½.

Transfer utajniony "1 z 2" edytuj

W transferze utajnionym "1 z 2" nadawca ma dwie wiadomości m₀ oraz m₁. Odbiorca chce odebrać jedną spośród tych dwóch wiadomości, jednak nie chce, by nadawca wiedział, którą otrzyma. Protokół stworzony przez Shimon Even, Oded Goldreich i Awrahama Lempela jest ogólny, jednak można go przedstawić używając algorytmu RSA.

Alicja				Bob
Prywatne	Publiczne	Opis		Prywatne	Publiczne	Opis
m₀, m₁		Wiadomości, które mają być wysłane.
d	N, e	Wygeneruj publiczny klucz RSA (N, e) i wyślij go do Boba.	$\Rightarrow$		N, e	Odbierz publiczny klucz RSA.
	x₀, x₁	Wygeneruj dwie losowe wartości.	$\Rightarrow$		x₀, x₁	Odbierz losowe wiadomości.
				k, b		Wybierz $b\in \{0,1\}$ i wygeneruj losowe k.
	v		$\Leftarrow$		v = (x_b + k^e) mod N	Zaszyfruj k, dodaj je do x_b (w celu uniemożliwienia rozczytania k) i wyślij do Alicji.
k₀ = (v – x₀)^d mod N, k₁ = (v – x₁)^d mod N		Jedno spośród k₀ i k₁ równa się k, ale Alicja nie jest w stanie stwierdzić, która to wartość.
	m₀' = m₀ + k₀, m₁' = m₁ + k₁	Wyślij dwie zmodyfikowane wiadomości do Boba.	$\Rightarrow$		m₀', m₁'	Odbierz obydwie zmodyfikowane wiadomości.
				m_b = m_b' -k		Deszyfruj m_b' (Bob wie, które spośród x₀ i x₁ wybrał).

Alicja ma dwie wiadomości m₀, m₁ i chce wysłać dokładnie jedną Bobowi, ale nie chce wiedzieć, którą z nich Bob otrzyma.
Alicja generuje kod publiczny RSA (N, e) oraz kod prywatny (N, d).
Generuje również dwie losowe liczby x₀, x₁ i wysyła je do Boba wraz z kluczem publicznym.
Bob decyduje, czy b będzie równe 0 czy 1 i wybiera odpowiednie x_b.
Bob generuje losowe k i uniemożliwia odczytanie, którą spośród wartości x₀ i x₁ wybrał poprzez stworzenie wartości v = (x_b + k^e) mod N, którą wysyła Alicji.
Alicja nie wie, którą wartość spośród x₀ i x₁ Bob wybrał. Generuje dwie możliwe wartości k: k₀ = (v – x₀)^d mod N, k₁ = (v – x₁)^d mod N.
Alicja tworzy zmodyfikowane wartości m₀' = m₀ + k₀ oraz m₁' = m₁ + k₁ i wysyła je do Boba.
Bob wie, którą spośród dwóch otrzymanych wiadomości może rozszyfrować za pomocą k, więc jest w stanie odczytać dokładnie jedną z wiadomości m_b = m_b' + k.

Transfer utajniony "1 z n" oraz "k z n" edytuj

Transfer utajniony "1 zn" może być zdefiniowany jako rozwinięcie transferu utajnionego "1 z 2". Nadawca posiada n wiadomości, a odbiorca chce otrzymać i-tą wiadomość spośród wszystkich wiadomości nadawcy. Nadawca nie wie, która wiadomość została odebrana przez odbiorcę, a odbiorca nie może odczytać żadnej wiadomości poza tą, którą wybrał.

Transfer utajniony "1 z n" został zaproponowany m.in. przez Sven Laur i Helger Lipmaa^[5].

Gilles Brassard, Claude Crépeau i Jean-Marc Robert stworzyli bardziej uogólnioną wersję protokołu: transfer utajniony "k z n"^[6]. W wersji tej odbiorca otrzymuje k spośród n wiadomości, które posiada nadawca. Zbiór k wiadomości może zostać otrzymany jednocześnie, lub mogą one być otrzymywane kolejno, bazując na poprzednio otrzymanych wiadomościach^[7].

Przypisy edytuj

↑ Tom Kazana: Kocha, lubi, szyfruje.... deltami.edu.pl, 2012-05. [dostęp 2016-02-04].
↑ Michael O. Rabin. "How to exchange secrets by oblivious transfer." Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981. Zeskanowany brudnopis z dopisanymi maszynowo uwagami eprint.iacr.org archive. Wersja drukowana dostępna na Dousti's homepage
↑ S. Even, O. Goldreich, and A. Lempel, "A Randomized Protocol for Signing Contracts", Communications of the ACM, Volume 28, Issue 6, pg. 637-647, 1985. Paper at Catuscia Palamidessi's page
↑ Claude Crépeau. "Equivalence between two flavours of oblivious transfer". In Advances in Cryptology: CRYPTO '87, volume 293 of Lecture Notes in Computer Science, pages 350--354. Springer, 1988
↑ Sven Laur and Helger Lipmaa (2007). "A New Protocol for Conditional Disclosure of Secrets And Its Applications". In Jonathan Katz and Moti Yung, editors, ACNS, Lecture Notes in Computer Science 4521: 207–225. Springer, Heidelberg.
↑ Gilles Brassard, Claude Crépeau and Jean-Marc Robert. "All-or-nothing disclosure of secrets." In Advances in Cryptology: CRYPTO ’86, volume 263 of LNCS, pages 234–238. Springer, 1986.
↑ Moni Naor and Benny Pinkas. "Oblivious transfer with adaptive queries." In Advances in Cryptology: CRYPTO ’99, volume 1666 of LNCS, pages 573–-590. Springer, 1999.

Linki zewnętrzne edytuj

Zbiór linków dotyczący zagadnienia transferu utajnionego. kodu.ut.ee. [zarchiwizowane z tego adresu (2016-03-04)]. (ang.).

[Kazana-1] Tom Kazana: Kocha, lubi, szyfruje.... deltami.edu.pl, 2012-05. [dostęp 2016-02-04].

[2] Michael O. Rabin. "How to exchange secrets by oblivious transfer." Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981. Zeskanowany brudnopis z dopisanymi maszynowo uwagami eprint.iacr.org archive. Wersja drukowana dostępna na Dousti's homepage

[3] S. Even, O. Goldreich, and A. Lempel, "A Randomized Protocol for Signing Contracts", Communications of the ACM, Volume 28, Issue 6, pg. 637-647, 1985. Paper at Catuscia Palamidessi's page

[4] Claude Crépeau. "Equivalence between two flavours of oblivious transfer". In Advances in Cryptology: CRYPTO '87, volume 293 of Lecture Notes in Computer Science, pages 350--354. Springer, 1988

[5] Sven Laur and Helger Lipmaa (2007). "A New Protocol for Conditional Disclosure of Secrets And Its Applications". In Jonathan Katz and Moti Yung, editors, ACNS, Lecture Notes in Computer Science 4521: 207–225. Springer, Heidelberg.

[6] Gilles Brassard, Claude Crépeau and Jean-Marc Robert. "All-or-nothing disclosure of secrets." In Advances in Cryptology: CRYPTO ’86, volume 263 of LNCS, pages 234–238. Springer, 1986.

[7] Moni Naor and Benny Pinkas. "Oblivious transfer with adaptive queries." In Advances in Cryptology: CRYPTO ’99, volume 1666 of LNCS, pages 573–-590. Springer, 1999.

[1]

[2]

[3]

[4]

[5]

[6]

[7]