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
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 me 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 = p*q, e t.że NWD(e, φ(N)) = 1 | Wygeneruj kod publiczny (N, e) i wyślij go do Boba. | N, e | Odbierz klucz publiczny. | |||
C = me mod N | Zaszyfruj wiadomość m i wyślij ją do Boba. | C | Odbierz kryptogram wiadomości m. | |||
x | Wybierz losową liczbę x mod N. | |||||
a | Odbierz a. | a = x2 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. | y | Odbierz y. | |||
Sprawdź, czy y2 = 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ść me mod N.
- Odbiorca wybiera losową liczbę x mod N i wysyła do nadawcy wartość x2 mod N.
- Nadawca znajduje cztery pierwiastki kwadratowe x2 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ć me , 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 me mod N.
Ponieważ x2 mod N ma cztery pierwiastki kwadratowe, prawdopodobieństwo tego, że odbiorca odszyfruje wiadomość m wynosi ½.
Transfer utajniony "1 z 2"
W transferze utajnionym "1 z 2" nadawca ma dwie wiadomości m0 oraz m1. 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 | |
m0, m1 | Wiadomości, które mają być wysłane. | |||||
d | N, e | Wygeneruj publiczny klucz RSA (N, e) i wyślij go do Boba. | N, e | Odbierz publiczny klucz RSA. | ||
x0, x1 | Wygeneruj dwie losowe wartości. | x0, x1 | Odbierz losowe wiadomości. | |||
k, b | Wybierz i wygeneruj losowe k. | |||||
v | v = (xb + ke) mod N | Zaszyfruj k, dodaj je do xb (w celu uniemożliwienia rozczytania k) i wyślij do Alicji. | ||||
k0 = (v – x0)d mod N, k1 = (v – x1)d mod N | Jedno spośród k0 i k1 równa się k, ale Alicja nie jest w stanie stwierdzić, która to wartość. | |||||
m0' = m0 + k0, m1' = m1 + k1 | Wyślij dwie zmodyfikowane wiadomości do Boba. | m0', m1' | Odbierz obydwie zmodyfikowane wiadomości. | |||
mb = mb' -k | Deszyfruj mb' (Bob wie, które spośród x0 i x1 wybrał). |
- Alicja ma dwie wiadomości m0, m1 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 x0, x1 i wysyła je do Boba wraz z kluczem publicznym.
- Bob decyduje, czy b będzie równe 0 czy 1 i wybiera odpowiednie xb.
- Bob generuje losowe k i uniemożliwia odczytanie, którą spośród wartości x0 i x1 wybrał poprzez stworzenie wartości v = (xb + ke) mod N, którą wysyła Alicji.
- Alicja nie wie, którą wartość spośród x0 i x1 Bob wybrał. Generuje dwie możliwe wartości k: k0 = (v – x0)d mod N, k1 = (v – x1)d mod N.
- Alicja tworzy zmodyfikowane wartości m0' = m0 + k0 oraz m1' = m1 + k1 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 mb = mb' + k.
Transfer utajniony "1 z n" oraz "k z n"
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
- ↑
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
- Zbiór linków dotyczący zagadnienia transferu utajnionego. kodu.ut.ee. [zarchiwizowane z tego adresu (2016-03-04)]. (ang.).