Słowo o szyfrowaniu funkcyjnym

Tym razem opowiemy o szyfrowaniu funkcyjnym, które jest współczesnym, już XXI-wiecznym, rozszerzeniem standardowych schematów klucza publicznego.  Początki kryptografii klucza publicznego sięgają prac Diffie'ego i Hellmana, a także Rivesta, Shamira i Adelmana, które zrewolucjonizowały świat bezpieczeństwa komputerowego w drugiej połowie lat 70. XX wieku.

W klasycznym ujęciu opisanym w powyższych pracach, osoba prywatna o imieniu Alicja generuje samodzielnie parę kluczy $(PK,SK)$ i udostępnia światu ich publiczną część $PK$, która następnie może być wykorzystana przez jej potencjalnych internetowych rozmówców do zaszyfrowania wiadomości $M$, w postaci szyfrogramu $C = Enc(PK,M)$.  Alicja, będąc w posiadaniu tajnej informacji $SK$ - odpowiadającej $PK$, wykorzystuje algorytm deszyfracji $Dec(SK,C)$ w celu odzyskania całej wiadomości $M$.  Oczywiście wymagamy również, żeby żadna osoba nieznająca $SK$ nie mogła poznać $M$ na podstawie $C$.

Wyobraźmy sobie teraz, że Alicja jest pracownikiem działu ochrony środowiska dużej agendy rządowej, a jej koleżanka Barbara pracuje w dziale analiz finansowych.  Ich organizacja wydała kompleksowy raport $R$ zawierający poufne informacje dotyczące zarówno finansów, jak i spraw związanych z zanieczyszczeniem środowiska.  Raport ten został zaszyfrowany publicznym kluczem ich firmy $PK_{agenda}$ i udostępniony wszystkim pracownikom w postaci $C = Enc(PK_{agenda},R)$.  Jak teraz poradzić sobie z sytuacją, w której Alicja i Barbara, ze względu na miejsce swojego zatrudnienia, powinny mieć dostęp do innych części zaszyfrowanego raportu? Oczywiście dział bezpieczeństwa ich firmy, nie może im udostępnić klucza prywatnego $SK_{agenda}$, gdyż to pozwoliłoby Alicji zdeszyfrować cały raport i uzyskać dane dotyczące spraw finansowych.  Odpowiedzią na nasze pytanie jest właśnie szyfrowanie funkcyjne, które pozwala na dywersyfikację możliwości kluczy prywatnych.  Dział bezpieczeństwa może udostępnić Alicji klucz $SK_{eko}$, a Barbarze $SK_{fin+kadry}$, co pozwoli im odpowiednio: poznać dane dotyczące ochrony środowiska oraz wydobyć informacje finansowe i kadrowe.  Zwróćmy uwagę, że istnienie zaufanego działu bezpieczeństwa jest tutaj niezbędne.  Gdyby Alicja generowała klucz samodzielnie, jak w wyżej opisanej sytuacji klasycznej, mogłaby w szczególności stworzyć sobie klucz do spraw finansowych.

W pełnej ogólności protokoły szyfrowania funkcyjnego pozwalają działowi bezpieczeństwa wystawić klucz $SK_f$ dający możliwość uzyskania wyłącznie informacji $f(M) = Dec(SK_f,C)$, będąc w posiadaniu szyfrogramu $C = Enc(PK,M)$.  W zarysowanym przed chwilą scenariuszu dotyczącym agendy rządowej rolę $f$ pełniły funkcje wydobywające dane związane z odpowiednimi działami organizacji.  W szczególnym przypadku, gdy funkcja $f$ sprawdza czy wiadomość jest opatrzona odpowiednim nagłówkiem wskazującym na jej adresata, otrzymujemy schemat tzw. szyfrowania opartego o tożsamość (Identity-Based Encryption).  Implementacja tego schematu, wykonana przez firmę Voltage Security należącą do jednego z twórców szyfrowania funkcyjnego Dana Boneha, okazała się być dużym sukcesem komercyjnym.

Na zakończenie opiszemy krótko historię protokołów szyfrowania funkcyjnego.  Prekursorem ogólnego szyfrowania funkcyjnego było wspomniane wyżej szyfrowanie oparte o tożsamość.  Pierwszy w pełni bezpieczny protokół, realizujący ten szczególny przypadek, pojawił się w pracy Boneh'a i Franklina "Identity-Based Encryption from the Weil Pairing" (co ciekawe było to również jedno z pierwszych zastosowań odwzorowań dwuliniowych Weila w kryptografii).  Ogólna idea szyfrowania funkcyjnego została zarysowana przez Sahai'a i Watersa w pracy "Fuzzy Identity-Based Encryption", a w pełni sformalizowana przez Boneh'a, Sahai'a i Watersa w "Functional Encryption: Definitions and Challenges".
Pierwsze protokoły realizujące oczekiwaną funkcjonalność w całkowitej ogólności pojawiły się dopiero ostatnio, w 2013 roku (np. w S. Goldwasser i inni "Reusable Garbled Circuits and Succinct Functional Encryption"). 

Nasz warszawski zespół kryptograficzny gościł ostatnio Vincenzo Iovino, kryptografa z Uniwersytetu w Salerno, którego ostatnia praca "On the achievability of Simulation-Based Security for Functional Encryption" dotyczy bezpieczeństwa protokołów szyfrowania funkcyjnego. W ostatnim tygodniu mieliśmy przyjemność wysłuchać jego referatu właśnie na ten temat.

Bibliografia:

1. D. Boneh, M.K. Franklin, "Identity-Based Encryption from the Weil Pairing" Proceedings of CRYPTO 2001, http://www.iacr.org/archive/crypto2001/21390212.pdf
2. A. Sahai, B. Waters "Fuzzy Identity-Based Encryption" Proceedings of Eurocrypt 2005, http://eprint.iacr.org/2004/086.pdf
3. D. Boneh, A. Sahai, B.Waters "Functional Encryption: Definitions and Challenges", Proceedings of TCC 2011, http://eprint.iacr.org/2010/543.pdf
4. S. Goldwasser, Y. Kalai and R.A. Popa, V. Vaikuntanathan, N. Zeldovich, "Reusable Garbled Circuits and Succinct Functional Encryption", Proceedings of STOC 2013, http://eprint.iacr.org/2012/733.pdf
5. V. Iovino, A. De Caro, A. Jain, A. O'Neill, O. Paneth, G. Persiano, "On the Achievability of Simulation-Based Security for Functional Encryption", Proceedings of Crypto 2013, http://eprint.iacr.org/2013/364.pdf