Poza kryptografią klucza publicznego: szyfrowanie funkcjonalne

Tradycyjne szyfrowanie kluczem publicznym opiera się na prostym modelu: szyfrowaniu za pomocą klucza publicznego i odszyfrowaniu za pomocą odpowiadającego mu klucza prywatnego. Odbiorca poznaje całą wiadomość w postaci jawnej. Ten model typu wszystko albo nic jest zbyt mało elastyczny dla wielu zastosowań: baza danych medycznych może na przykład umożliwiać lekarzowi ustalenie wyłącznie, czy pacjent cierpi na określone schorzenie, bez ujawniania całej dokumentacji medycznej. Szyfrowanie funkcyjne rozwiązuje ten problem.

Szyfrowanie oparte na tożsamości (IBE), zaproponowane przez Shamira w 1984 roku i skonstruowane przez Boneha i Franklina w 2001 roku, umożliwia użycie ciągu identyfikującego (adresu e-mail, nazwy domeny, identyfikatora pracownika) jako klucza publicznego. Zaufany urząd zarządzający kluczami generuje klucze prywatne dla określonych tożsamości. IBE eliminuje potrzebę stosowania certyfikatów klucza publicznego i upraszcza dystrybucję kluczy. IBE jest najprostszą formą szyfrowania funkcyjnego.

Szyfrowanie funkcyjne (FE), formalnie zdefiniowane przez Boneha, Sahaiego i Watersa w 2011 roku, uogólnia IBE. W schemacie FE urząd zarządzający kluczami może wygenerować klucz funkcji sk_f dla dowolnej funkcji f. Mając szyfrogram Enc(x) i klucz funkcji sk_f, odbiorca może obliczyć f(x), ale nie dowiaduje się niczego więcej o x poza tym, co ujawnia f(x). Funkcja f może być dowolną funkcją obliczalną należącą do klasy obsługiwanej przez schemat.

Szyfrowanie funkcyjne dla iloczynu skalarnego umożliwia odbiorcy posiadającemu sk_y obliczenie iloczynu skalarnego na podstawie szyfrogramu wektora x. Umożliwia to przeprowadzanie prywatnego wnioskowania w uczeniu maszynowym: należy zaszyfrować wektor cech użytkownika x i przekazać właścicielowi modelu sk_y dla jego wektora wag y, a właściciel pozna wyłącznie iloczyn skalarny (surowy wynik predykcji), bez poznawania cech użytkownika. Istnieje kilka praktycznych schematów szyfrowania funkcyjnego dla iloczynu skalarnego (ABDALLA et al. 2016).

Szyfrowanie funkcyjne do testowania równości umożliwia stronie sprawdzenie, czy zaszyfrowana wartość odpowiada konkretnej wartości v, przy czym poznaje ona wyłącznie, czy równość zachodzi. Umożliwia to wykonywanie zapytań do baz danych z zachowaniem prywatności: serwer przechowuje zaszyfrowane rekordy, a użytkownik wyszukuje rekordy pasujące do określonych wartości, nie ujawniając serwerowi, czego szuka, ani wyników wykraczających poza informację tak/nie o dopasowaniu. Praktyczne konstrukcje wykorzystują parowania biliniowe.

Najpotężniejsza forma szyfrowania funkcyjnego obsługuje dowolne obwody boolowskie lub arytmetyczne jako funkcje. Odbiorca posiadający sk_f dla dowolnej funkcji f wykonywalnej w czasie wielomianowym może obliczyć f(x) na podstawie Enc(x). Szyfrowanie funkcyjne dla obwodów ogólnych zostało skonstruowane teoretycznie przez Garga, Gentry’ego, Haleviego, Raykovą, Sahaiego i Watersa (2013) z wykorzystaniem map wieloliniowych, ale istniejące konstrukcje ogólnego szyfrowania funkcyjnego są niepraktyczne ze względu na zależność od niedoskonałych założeń dotyczących map wieloliniowych.

Obfuskacja nierozróżnialności (iO) to najsilniejszy znany prymityw kryptograficzny, ściśle powiązany z szyfrowaniem funkcyjnym. Schemat iO przyjmuje obwód C i tworzy jego obfuskowaną wersję O(C), która oblicza tę samą funkcję, ale nie ujawnia żadnych informacji o C poza jego zachowaniem wejście–wyjście. iO implikuje większość znanych prymitywów kryptograficznych, w tym ogólne FE. Istnieją konstrukcje kandydujące oparte na problemach kratowych, ale są one bardzo odległe od praktycznego zastosowania.

Szyfrowanie oparte na atrybutach (ABE) to możliwa do praktycznej realizacji forma szyfrowania funkcyjnego, w której funkcja f jest ograniczona do oceny polityki: f(x) = 1, jeśli zbiór atrybutów x spełnia politykę, a w przeciwnym razie f(x) = 0. ABE umożliwia precyzyjną kontrolę dostępu, w której uprawnienia do odszyfrowywania zależą od atrybutów użytkownika. ABE jest najczęściej wdrażaną praktycznie formą szyfrowania funkcyjnego; stosuje się je w pamięci masowej w chmurze, ochronie zdrowia i IoT.

Historia konstrukcji FE prowadzi od rozwiązań prostych do zaawansowanych: IBE (Boneh-Franklin 2001) → FE dla równości (różne konstrukcje z lat 2005–2010) → FE dla iloczynu skalarnego (ABDALLA 2016) → FE dla obwodów o ograniczonej głębokości (oparte na odwzorowaniach wieloliniowych, 2013) → ogólne FE (przypuszczalnie wynikające z iO). Każdy kolejny etap zapewnia większe możliwości, ale jest także bardziej złożony i mniej wydajny. W praktyce wdraża się najprostszą formę, która zapewnia wymaganą funkcjonalność.

Bezpieczeństwo FE definiuje się poprzez nierozróżnialność szyfrogramów dwóch wiadomości x0 i x1, nawet przy znajomości kluczy funkcyjnych dla dowolnych funkcji f, o ile dla wszystkich zapytanych funkcji zachodzi f(x0) = f(x1). Gwarantuje to, że osoba odszyfrowująca poznaje dokładnie f(x) i nic ponadto. Wyróżnia się dwa poziomy bezpieczeństwa: bezpieczeństwo selektywne (przeciwnik określa wiadomości stanowiące wyzwanie przed poznaniem klucza publicznego) oraz bezpieczeństwo adaptacyjne (pełne bezpieczeństwo oparte na symulacji).

Ogólne FE pozostaje niepraktyczne, ale FE dla iloczynu skalarnego i ABE można wdrażać już dziś. Wyzwania obejmują konieczność korzystania z zaufanego urzędu wydającego klucze (pojedynczy punkt awarii), złożoność odwoływania kluczy, narzut wydajnościowy operacji parowania oraz ograniczoną standaryzację. Kierunki badań obejmują FE z wieloma urzędami (bez jednego zaufanego urzędu), zdecentralizowane generowanie kluczy oraz FE dla większych klas funkcji bez odwzorowań wieloliniowych.

Co odróżnia szyfrowanie funkcyjne od tradycyjnego szyfrowania z kluczem publicznym?

Szyfrowanie funkcyjne (Boneh-Sahai-Waters 2011) uogólnia IBE, umożliwiając korzystanie z kluczy funkcyjnych sk_f, które pozwalają obliczyć f(x) na podstawie Enc(x) bez pełnego poznania x. Istnieją praktyczne konstrukcje FE dla iloczynu skalarnego (prywatne wnioskowanie ML) oraz testowania równości. ABE jest praktycznie wdrożonym przypadkiem szczególnym służącym do oceny polityk dostępu. FE dla obwodów ogólnych wymaga odwzorowań wieloliniowych (niepraktycznych). iO jest najsilniejszym powiązanym prymitywem. Kluczowym wyzwaniem jest przejście od teorii do wydajnych zastosowań praktycznych.