Existem casos em que é se deseja realizar operações sobre dados sensíveis em um ambiente passível de comprometimento. Neste caso, é interessante o uso de um sistema de criptografia que permite realizar operações sobre os dados encriptados de maneira que o resultado seja decriptado para o resultado esperado das operações. Nesse caso, dizemos que uma encriptação é homemórfica.
Encriptações homomórficas apresentam algumas fortes limitações, mas ainda assim podem ser utilizadas de maneira efetiva no contexto certo.
Sejam \(U = (S, f_1,\dots, f_k, p_1,\dots, p_l, s_1,\dots, s_m)\) e \(C = (S', f_1',\dots, f_k', p_1',\dots, p_l', s_1',\dots, s_m')\) dois sistemas algébricos onde \(S\) e \(S'\) denotam espaços de dados, \(f_i\) e \(f_i'\) denotam operações que podem ser efeituadas nos respectivos dados, \(p_i\) e \(p_i'\) denotam predicados (i.e. uma função com retorno booleano) que podem condicionar a realização das operações e \(s_i\) e \(s_i'\) denotam constantes.
Sejam também \(d_1, d_2,\dots\) dados sensíveis elementos de \(S\).
Uma função de decodificação \(\varphi : C \to U\) é dita homomórfica se, para qualquer \(i\), - \(f'_i(a,b ,...) = c \implies f_i(\varphi(a), \varphi(b),\dots) = \varphi(c)\) - \(p'(a,b,\dots) \equiv p( \varphi(a), \varphi(b), ...)\) - \(\varphi(s_i') = s_i\)
Isso significa essencialmente que os elementos de \(U\) são equivalentes aos elementos de \(C\), ou seja, que para qualquer operação, predicado ou constante que possa ser utilizada no sistema não encriptado \(U\), existe uma operação, predicado ou constante do sistema encriptado \(C\) que é equivalente.
Dado um programa qualquer escrito no sistema \(U\), pode-se traduzi-lo para o sistema \(C\) simplesmente trocando todo \(f_i\) por \(f_i'\), todo \(p_i\) por \(p_i'\) e todo \(s_i\) por \(s_i'\).
Existem algumas características que devem ser exigidas da função \(\varphi\) para que ela seja praticável como sistema criptográfico: - \(\varphi\) e \(\varphi ^{-1}\) devem ser fáceis de computar (i.e. tempo polinomial, mas em geral pouco tempo computacional é melhor) - As operações \(f'_i\) e os predicados \(p_i'\) devem ser facilmente computáveis (não muito mais que seus equivalentes \(f_i\) e \(p_i\)) - Quando encriptados, os dados \(\varphi ^{-1}(d_i)\) não devem ocupar muito mais espaço do que \(d_i\) - Conhecimento de diversos \(\varphi ^{-1}(d_i)\) não deve ser suficiente para revelar a \(\varphi\) (i.e. resistente a ataques de texto cifrado) - Conhecimento de \(d_i\) e \(\varphi(d_i)\) não deve ser suficiente para revelar a \(\varphi\) (i.e. resistente a ataques de texto escolhido) - As operações e predicados de \(C\) não devem permitir revelar a \(\varphi\) (como no exemplo adiante)
Encriptações homomórficas são um pouco limitadas em relação a suas capacidades, uma vez que essas podem gerar vulnerabilidades.
Se o sistema criptográfico permite a determinação da codificação de qualquer constante arbitrária e um predicado \(\leq\), o sistema é vulnerável a uma simples busca binária.
Por exemplo, suponha \(U = (\mathbb{N}, +, \leq, 0, 1)\) e \(C = (\mathbb{W}, +', \leq', 0', 1')\) para algum conjunto \(\mathbb{W}\) e suponha que desejamos decodificar um dado \(\varphi ^{-1}(d)\). Podemos computar \(\varphi ^{-1}(1) = 1'\), \(\varphi ^{-1}(2) = 1' +' 1'\), \(\varphi ^{-1} (4) = 2' +' 2'\) e assim por diante, verificando a cada passo se \(\varphi ^{-1}(2^k) \geq \varphi ^{-1}(d)\). Quando o predicado for verdadeiro, fazemos \(\varphi ^{-1} (2 ^k) +' 1'\) e assim por diante até computarmos \(d\) exatamente.
Se o sistema criptográfico tem as operações de soma e produto, o predicado de igualdade binário e o predicado de igualdade a zero, então podemos testar a igualdade de um dado encriptado a uma constante qualquer.
Isso segue do fato de que \(x=k \iff x\neq0 \text{ e } x^2 = \underbrace{ x+\dots+x }_{ k \text{ vezes} }\).
Ou seja, se sabemos a encriptação de uma constante qualquer \(\varphi ^{-1} ( s)\), podemos testar se \(\varphi ^{-1}(s_i) = 0\) e se \(\varphi ^{-1}(s_i) \cdot \varphi ^{-1}(s_i) = \underbrace{ \varphi ^{-1}(s_i) +\dots + \varphi ^{-1}(s_i) }_{ \varphi ^{-1} ( s) \text{ vezes} }\). Se o primeiro predicado for falso e o segundo verdadeiro, \(d = s\).