Crittografia omomorfica

La crittografia omomorfica (dall'inglese homomorphic encryption o semplicemente HE) è un tipo di crittografia basata su tecniche che permettono la manipolazione di dati cifrati. Ad esempio, avendo due numeri $X$ e $Y$ (cifrati con lo stesso algoritmo omomorfico a partire da due numeri $A$ e $B$) è possibile calcolare la cifratura della somma di $A$ e $B$ sommando direttamente $X$ e $Y,$ senza bisogno di effettuare la decifratura.

La crittografia omomorfica si suddivide in varie famiglie, due delle principali sono: la crittografia parzialmente omomorfica (PHE) e la crittografia completamente omomorfica (FHE). La crittografia parzialmente omomorfica può elaborare un solo tipo di operazione, tipicamente l'addizione o la moltiplicazione. Mentre la crittografia completamente omomorfica può elaborare tutte le operazioni necessarie, ad esempio le operazioni aritmetiche o le funzioni booleane AND, OR, NOT.

Storia

Alla fine degli anni settanta e ancora agli albori della crittografia a chiave pubblica, Rivest, Adleman e Dertouzos proposero il paradigma degli omomorfismi privati, successivamente noto in letteratura come crittografia omomorfica, per poter effettuare dei calcoli su dati cifrati. In particolare, la situazione che i tre studiarono fu la seguente: un client ha un certo input $x$ e vorrebbe calcolare $f(x)$, per una qualche funzione $f$. Il client cifra $x$, ottenendo un crittotesto $c$ che invia al server, il quale provvede ad applicare una certa funzione (che dipende da $f$) su $c$ e restituisce tale valore al client; quando il client decifra il valore ricevuto dal server ottiene direttamente $f(x)$. Un esempio molto semplice è fornito dal crittosistema RSA che permette di calcolare la moltiplicazione in modo omomorfico.

Definizione formale

Uno schema omomorfico $\Pi$ è una tupla di algoritmi $({\textrm {KGen}},{\textrm {Enc}},{\textrm {Dec}},{\textrm {Eval}})$ così definiti:

• ${\textrm {KGen}}(1^{\lambda },1^{\tau })$ prende in input un parametro di sicurezza λ e un ulteriore parametro τ e genera una coppia di chiavi (pk, sk)
• ${\textrm {Enc}}(pk,b)$ restituisce un crittotesto c associato al bit di input b
• ${\textrm {Dec}}(sk,c)$ prende in input un crittotesto c e restituisce un bit b
• ${\textrm {Eval}}(pk,\Gamma ,{\overrightarrow {c}})$ prende in input un vettore di crittotesti e un circuito Γ, restituendo un altro vettore di crittotesti ${\overrightarrow {c}}'$

Lo schema $\Pi$ soddisfa la proprietà di correttezza per una classe di circuiti $C=\{C_{\tau }\}$ se per ogni coppia di chiavi generate in modo corretto si ha che:

1. $\forall b\in \{0,1\}:Pr[{\textrm {Dec}}(sk,{\textrm {Enc}}(pk,b))=b]=1$
2. $\forall \Gamma \in C_{\tau },\forall {\overrightarrow {b}}=(b_{1},\dots ,b_{t}),b_{i}\in \{0,1\}:\Pr[{\textrm {Dec}}(sk,{\textrm {Eval}}(pk,\Gamma ,{\textrm {Enc}}(pk,{\overrightarrow {b}})))=\Gamma ({\overrightarrow {b}})]=1$

Si definisce capacità omomorfica dello schema la classe più ampia per cui lo schema preserva la proprietà di correttezza.

Applicazioni

La crittografia omomorfica è molto importante oggi, soprattutto con l'avvento del cloud computing: attualmente, infatti, i dati presenti su una piattaforma di cloud non sono totalmente sicuri, soprattutto se bisogna effettuare delle operazioni su di essi, poiché per manipolarli c'è bisogno di decifrarli. La crittografia omomorfica, invece, può risolvere questo problema e fare in modo che le informazioni memorizzate nel cloud non debbano mai essere decifrate (e che quindi siano sempre al sicuro). È già in fase di sperimentazione e di lancio sul mercato una nuova generazione di motori di ricerca come il “Crypto-Search-Engine” di Cryptolab, che riesce a fare ricerche all'interno dei dati cifrati senza conoscere né cosa si stia cercando né il contenuto dei file sui quali sta effettuando la ricerca.

Bibliografia

• (EN) Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich, collana Information Security and Cryptography, Springer International Publishing, 2017, DOI:10.1007/978-3-319-57048-8, ISBN 978-3-319-57047-1.
• (EN) Cryptography Algorithms: A guide to algorithms in blockchain, quantum cryptography, zero-knowledge protocols, and homomorphic encryption, collana Information Security and Cryptography, Packt Publishing, March 3, 2022, ISBN 1789617138.

Collegamenti esterni

• HElib una libreria C open source che implementa alcuni schemi della crittografia omomorfica.