|
|
|
|
|
Universidade Federal de Santa Maria
Ci. e Nat., Santa Maria, v. 47, e87825, 2025
DOI: 10.5902/2179460X87825
ISSN 2179-460X
Submitted: 29/05/2024 • Approved: 19/02/2025 • Published: 11/04/2025
4 ANÁLISE DAS COMPLEXIDADES DE PHE
Análise da complexidade dos algoritmos de Criptografia Homomórfica
Analysis of the complexity of Homomorphic Encryption algorithms
Aline De Lurdes Zuliani LunkesI
Fábio Borges de OliveiraI
I Laboratório Nacional de Computação Científica, RJ, Brasil
RESUMO
A Criptografia Parcialmente Homomórfica é importante para a preservação da privacidade no processamento de qualquer informação sensível. Este trabalho apresenta esquemas de Criptografia Parcialmente Homomórfica aplicados a inteiros, os quais suportam apenas uma operação homomórfica, seja aditiva ou multiplicativa. Realizamos a análise das complexidades de tempo computacional associadas às operações de cifragem, decifragem, cálculo do homomorfismo e possíveis ataques a cada esquema. Além disso, comparamos os esquemas estudados, detalhando seus algoritmos e destacando suas principais características de eficiência e segurança.
Palavras-chave: Criptografia Parcialmente Homomórfica; Complexidade computacional; Privacidade.
ABSTRACT
Partially Homomorphic Cryptography plays a crucial role in preserving privacy during the processing ofsensitive information. This work presents partially homomorphic encryption schemes applied tointegers, which support only one homomorphic operation, either additive or multiplicative. We analyzethe computational time complexities associated with encryption, decryption, homomorphiccomputation, and potential attacks on each scheme. Additionally, we compare the studied schemes,detailing their algorithms and highlighting their key efficiency and security characteristics.
Keywords: Partially Homomorphic Cryptography; Computational complexity; Privacy; Security
Um esquema de criptografia depende do compartilhamento de uma chave entreos pares envolvidos na troca de uma mensagem. O conceito de homomorfismo foiutilizado inicialmente em criptografia por Rivest, R. L., Adleman, L. & Dertouzos, M. L.(1978), como uma possível solução para a computação sem a necessidade de decifrar os dados. A Criptografia Homomórfica, em inglês Homomorphic Encryption - HE, é o esquema de criptografia que permite a terceiros, nuvens computacionais, executaremdeterminadas funções computáveis nos dados, preservando seus recursos e o formatodos dados criptografados.
Um esquema de HE é constituído por quatro operações: geração das chaves, cifrar 𝐸(𝑚), decifrar 𝐷(𝐸(𝑚)) e homomorfismo. A geração das chaves retorna ou um par de chaves secretas e públicas para a versão assimétrica de Criptografia Homomórfica ou uma única chave para a versão simétrica. O algoritmo de homomorfismo é uma operação específica na criptografia homomórfica. Ele recebe como entrada os textos cifrados das mensagens 𝑚1 e 𝑚2, representados como 𝐸(𝑚1) e 𝐸(𝑚2), e gera como saída o texto cifrado de uma função 𝑓 sobre 𝑚1 e 𝑚2, denotado por 𝐸(𝑓(𝑚1, 𝑚2,)). Assim, a operação𝑓 é realizada diretamente sobre as mensagens cifradas, dispensando a necessidade de prévia decifragem. O ponto crucial na HE é a preservação do formato das mensagens cifradas após um processo de homomórfico, garantindo que as mensagens possam ser decifradas corretamente. Além disso, conforme apontado por Halevi (2017), é admissível um crescimento logarítmico dotamanho do texto cifrado em função do número de operações homomórficas realizadas.
Com base nisso, temos que os esquemas de Criptografia Parcialmente Homomórfica - PHE, em inglês Partially Homomorphic Encryption, podem ser usadosapenas para aplicações cujos algoritmos incluem apenas operações ou aditivas ou multiplicativas. Por exemplo, o esquema de criptografia de Paillier é homomórficoaditivo Paillier (1999), já o esquema de RSA é apenas homomórfico multiplicativo Rivest, R. L., Shamir, A. & Adleman, L. (1978). Algumas das aplicações de PHE são em Votação Eletrônica, Assinatura Digitral, Certificação de Website e Armazenamento de dados em nuvem. O que propomos neste trabalho é a análise das complexidades de tempo das operações de: cifrar, decifrar, homomorfismo e de ataque dos métodos de Criptografia Parcialmente Homomórfica sobre números inteiros que constam em Acar, A., Aksu, H., Uluagac, A. S., & Conti, M. (2018). Não iremos analisar as complexidades da geração das chaves, pois estas são geradas uma única vez para cada esquema de PHE.
Além disso, os métodos: Goldwasser-Micali Goldwasser, S. & Micali, S. (1982), e KTX Kawachi, A., Tanaka, K., & Xagawa, K. (2007), que constam em Acar, A., Aksu, H.,Uluagac, A. S., & Conti, M. (2018) não se enquadram em nossa proposta, pois o homomorfismo desses métodos é baseado a uma operação XOR, que não se enquadra na soma de números inteiros. Este trabalho está organizado da seguinte maneira: na seção 2, abordamos uma visão geral de HE. Na seção 3, abordamos commais profundidade os algoritmos de PHE, discutindo cada um dos métodos de PHE propostos no trabalho Acar, A., Aksu, H., Uluagac, A. S., & Conti, M. (2018). Na seção 4,apresentamos a análise das complexidades dos algoritmos revisados na seção 3. Na última seção discutiremos os resultados obtidos neste trabalho.
Nesta seção, exploramos de forma mais detalhada a HE e suas principais propriedades. Além disso, fornecemos uma explicação aprofundada do funcionamento de cada esquema de PHE abordado neste trbalaho. A tabela 1 oferece uma visão geral das propriedades homomórficas de cada algoritmo de Criptografia de Chave Pública (PKC) analisado na seção 3, destacando suas principais características e diferenças.
Tabela 1 – Criptografia de Chave Pública (PKC)
|
Esquema |
Fatoração de Inteiros |
Logaritmo Discreto |
|
RSA |
X |
|
|
Goldwasser-Micali |
X |
|
|
El-Gamal |
X |
|
|
Benaloh |
X |
|
|
Naccache-Stern |
X |
|
|
Okamoto-Uchiyama |
X |
|
|
Paillier |
X |
|
|
Damgard-Jurik |
X |
Fonte: autores (2024)
Um esquema HE é caracterizado principalmente por quatro operações. Além disso, analisamos qual o melhor ataque para cada esquema. As operações são descritas a seguir:
Geração de Chaves: onde ocorre a geração de chaves secretas e públicas.
Cifrar: denotado por 𝐸(𝑚), onde 𝑚 é a mensagem a ser cifrada.
Decifrar: denotado por 𝐷(𝐸(𝑚)), onde 𝑚 é a mensagem a ser decifrada.
Homomorfismo: denotado por 𝐸(𝑚) □ 𝐸(𝑚) , onde 𝑚 é a mensagem e □ é a operação relaizada, que pode ser aditiva ou mulitiplicativa, dependendo do esquema. Na Tabela 2, detalhamos as operações de homomorfismo executadas em cada esquema discutido neste trabalho.
Por exemplo,
A Tabela 2 apresenta as propriedades homomórficas associadas a cada esquema descrito na seção 3.
Tabela 2 – Operações Homomórficas dos esquemas PHE
|
Algotitmos |
Adição |
Multiplicação |
|
RSA |
X |
|
|
El-Gamal |
X |
|
|
Benaloh |
X |
|
|
Naccache-Stern |
X |
|
|
Okamoto-Uchiyama |
X |
|
|
Paillier |
X |
|
|
Damgard-Jurik |
X |
Fonte: autores (2024)
Na Figura 1, apresentamos um exemplo ilustrativo do processo de homomorfismo. Nesse cenário, Alice deseja enviar uma mensagem para Bob por meio de um canal não seguro, enquanto Eve tenta interceptar a comunicação entre eles.
Alice possui a mensagem tanto em sua forma original (pura) quanto cifrada. Bob, por sua vez, utiliza o homomorfismo para realizar operações diretamente sobre o texto cifrado de Alice, garantindo que a mensagem permaneça protegida, mesmo em um ambiente vulnerável à interceptação. Além disso, ilustramos a resolução de um problema físico utilizando chaves públicas e privadas. Neste processo, o servidor (Bob) realiza o processamento das infromações de forma homomórfica, preservando a confidencialidade dos dados. Após o cálculo, o servidor retorna a solução do problema ao lciente (Alice), assegurando a segurança durante todo o procedimento. Assim, a comunicação entre Alice e Bob é protegida por criptografia, garantinfo a confidencialidade, autenticidade e integridade das infromações, mesmo diante de possíveis ataques de interceptação.
Figura 1 – Cenário onde Alice e Bob trocam mensagem por um canal não seguro
Fonte: autores (2025)
Ataque
O esquema PHE é adequado para aplicações específicas, sendo utilizado em algoritmos que realizam exclusivamente operações aditivas ou multiplicativas.
Nesta seção, apresentamos detalhadamente alguns algoritmos de Criptografia Parcialmente Homomórfica (PHE), com base nos conceitos apresentados em Acar, A., Aksu, H., Uluagac, A. S., & Conti, M. (2018). Para cada algoritmo, descrevemos as etapas fundamentais: geração de chaves, cifragem, decifragem, operação homomórfica e possíveis ataques.
3.1 Rivest, Shamir, Adleman (RSA)
Este método é baseado no problema de fatoração por inteiros de produtos de dois números primos grandes Rivest, R. L., Shamir, A. & Adleman, L. (1978). O RSA é o sistema criptográfico assimétrico de chave pública mais conhecido. Como este algoritmo é relativamente lento, é indicado que seus usuários, ao invás de usarem diretamente o RSA para criptografar seus dados, usem-o apenas para transmitir chaves criptográficas cifradas que serão empregadas em algoritmos simétricos. Esses algoritmos simétricos permitem que os processos de cifrar e decifrar ocorram de maneira mais rápida. Abaixo descreveremos o método de RSA.
Geração das Chaves: sejam 𝑝 e 𝑞 números primos gerados aleatoriamente, consideramos 𝑛 = 𝑝𝑞 e ϕ (𝑛) = (𝑝 – 1) (𝑞 – 1). Seja ℯ tal que mdc (ℯ, ϕ (𝑛)) = 1. Pelo algortimo de Euclides temos que 𝑑 = ℯ-1 mod ϕ (𝑛). Assim, obtemos as respectivas chaves desta esquema:
A chave pública: (ℯ, 𝑛)
A chave secreta: (𝑑, 𝑛).
Cifrar: considere 𝑚 a mensagem a ser cifrada e 𝑀, o conjunto de mensagens possíveis de serem cifradas, com 0 ≤ 𝑚 < 𝑛. Utilizaremos o par de chave pública (ℯ, 𝑛) para cifrar 𝑚
Decifrar: a mensagem 𝑚 pode ser recuperada usando o par de chave secreta (𝑑, 𝑛) da seguinte maneira
Homomorfismo: sejam 𝑚1 e 𝑚2 mensagens então,
Logo, este método não permite a adição homomórfica em mensagens cifradas, ou seja, é apenas homomórfico sobre a multiplicação.
Ataque: O melhor algoritmo para resolver o problema da fatoração de inteiros é General Number Field Sieve (GNFS). Para efetuar a decomposição de 𝑛 em fatores primos, consultar Lara, P., & Borges, F. (2008); Pandey (2014). Além disso, o tempo de execução deste algoritmo aplicado a um inteiro de 𝑛 bits é
onde 𝑐 é uma constanate e 𝑛 é o número inteiro ímpar que queremos fatorar.
3.2 Elgamal
Este esquema é um algoritmo de criptografia assimétrica de chave pública utilizado para o gerenciamento de chaves. Conforme Elgamal (1985) a segurança do algoritmo é derivada da dificuldade de se extrair um logaritmo discreto em corpos finitos. Este algoritmo permite confirmar a autenticidade de uma mensagem enviada, mesmo que tenha sido enviada em um canal não seguro.
Gerações das Chaves: seja 𝑔 um um gerador do grupo cíclico 𝔾 com módulo 𝑝, e 𝑛 = 𝑝𝑞, onde 𝑝 e 𝑞 são números primos. Em um grupo cíclico, é possível gerar todos os elementos desse grupo usando o seu gerador. Considere 𝒽 = 𝑔𝑦 mod 𝑝 onde 𝑦 ∈ ℤ𝑝 é qualquer, e seja 𝑥 um elemento aleatório do conjunto {1, 2, . . . , 𝑝 − 1}.
Assim, obtemos as respectivas chaves deste esquema:
A chave pública: (𝑝, 𝑔, 𝒽).
A chave secreta: 𝑦.
Cifrar: a mensagem 𝑚 é criptografada usando 𝑔 (gerador do grupo) e 𝑥, e a saída é um par de mensagens cifradas, assim
Decifrar: seja s = 𝐸(𝑚)1–𝑦 calculado onde 𝑦 é a chave secreta, assim
Homomorfismo: sejam 𝑚1 e 𝑚2 mensagens a serem cifradas, então
Portanto, este método permite somente operações multiplicativas.
Ataque: como no RSA, ultilizamos o algoritmo GNFS.
3.3 Benaloh
Este esquema é uma extensão do criptossistema de Goldwasser, S. & Micali, S. (1982), efetuando um número ilimitado de adições modulares, ou seja, cifra a mensagem como um bloco, em vez de bit a bit, veja Clarkson (1994); Fousse, L., Lafourcade, P., & Alnuaimi, M (2011).
Geração das Chaves: seja um bloco de tamanho 𝑟 e os números primos grandes 𝑝 e 𝑞, escolhidos de modo que 𝑟 divida 𝑝 – 1 e 𝑞 – 1. Além disso, 𝑟 deve ser relativamente primo a (𝑝 – 1)/ 𝑟 e também a (𝑞 – 1)/ 𝑟 ou seja, mdc (𝑟, ( 𝑝 – 1)/ 𝑟 ) = 1 e mdc (𝑟, (𝑞 – 1)/ 𝑟 ) = 1. Segundo autores Fousse, L., Lafourcade P., & Alnuaimi, M (2011) para decifrar corretamente, devemos considerar 𝑝i = 𝑝1 𝑝2 .... 𝑝k fatorado em números primos distintos. Além disso, 𝑦 ∈ ℤ*n é esolhido 𝑦ϕ𝑝1 ≢ 1 mod 𝑛, onde ℤ*n é o subgrupo multiplicaivo de números inteiros módulo 𝑛 que inclui todos os números menores que e relativamente primos a 𝑟. Então, 𝑛 = 𝑝𝑞 e Φ = 𝑝 –1)(𝑞 – 1) são calculados. Assim, obtemos as respectivas chaves deste esquema:
A chave pública: (𝑦, 𝑛, 𝑟).
A chave secreta: (𝑝, 𝑞).
Cifrar: seja 𝑚 ∈ ℤ𝑟, onde ℤ𝑟 = {0,1,..., 𝑟 – 1} e escolhendo u ∈ ℤ*n um número aleatório temos
Decifrar: este processo ocorre por um processo exausivo para i ∈ ℤ𝑟 tal que
onde a mensagem 𝑚 é retornada com o valor de 𝑚 = i.
Homomorfismo: sejam 𝑚1 e 𝑚2 as mensagens a operar
Logo, esse método é apenas homomórfico aditivo.
Ataque: O Pollard 𝘱 é o algoritmo mais eficiente para o cálculo da decifração, entretanto, a segurança do algoritmo ainda é baseada na fatoração de inteiros, portanto, utiliza-se o GNFS. O melhor algoritmo de ataque para resolver este esquema é Polllard 𝘱, Teske (1998). Supondo que o represente a ordem do grupo, ou seja, influencia diretamente na complexidade computacional do ataque, que é expressa pela seguinte fórmula:
3.4 Naccache-Stern
Este é um esquema de generalização do sistema de criptografia de Benaloh para aumentar sua eficiência computacional Naccache, D. & Stern, J. (1998). Sua segurança se baseia no problema de maior resíduos e funciona no grupo (ℤ/𝑛ℤ)* onde 𝑛 é um produto de dois números primos grandes.
Geração das Chaves: considere uma coleção contendo 𝑘 números primos ímpares pequenos e distintos, dada por {𝑝1, . . . , 𝑝𝑘}. Em seguida, divida esse conjunto ao meio e defina
Defina σ = 𝑢𝑣 = Escolha números primos grandes 𝑎 e 𝑏 de modo que
sejam ambos primos, e defina 𝑛 = 𝑝𝑞. Escolha um inteiro aleatório 𝑔 mod 𝑛 tal que 𝑔 tenha ordem Φ(𝑛)/4. Para cada índice 𝑗 ≤ 𝑘 escolhemos um número aleatório 𝑔𝑗, que não seja uma potência do 𝑝ⱼ- ésimo primo do conjunto inicial, ou seja, 𝑔 Φ (𝑛)/p3 ≢ 1 mod 𝑛. Assim, com uma "probabilidade imperativa", isto é, uma probabilidade muito alta,
terá uma ordem maior ou igual
Quando 𝑘 = 1 o esquema descrito se reduz ao esquema de criptografia de Benaloh, que pode ser visto como um caso particular da construção mais geral apresentada.
A chave pública: (σ, 𝑛, 𝑔).
A chave secreta: (𝑝, 𝑞).
Caso 𝑘 for um número ímpar, a divisão do conjunto de 𝑘 números primos ao meio resulta em duas partes que não possuem o mesmo números de elementos. Para corrigir isso, as definições de 𝑢 e 𝑣 podem ser ajustadas para lidar com o número ímpar de primos, ou seja,
onde [𝑘/2] representa o piso de 𝑘/2, garantindo que 𝑢 contenha [𝑘/2] primos, enquanto 𝑣 contém os primos restantes do índice [𝑘/2] + 1 até 𝑘. Assim, todas as 𝑘 entradas são consideradas adequadamente, mesmo para valores ímpares de 𝑘.
Cifrar: seja 𝑚 ∈ ℤ/σℤ. Escolha um inteiro aleatório 𝑥 tal que 𝑥 ∈ ℤ/𝑛ℤ então
Decifrar: considere 𝑚 mod 𝑝ⱼ para cada ⱼ, e em seguida, aplicamos o Teorema do Resto Chinês para calcular 𝑚ⱼ e 𝑝ⱼ , obtemos assim,
onde 𝑚ⱼ = 𝑚 mod 𝑝i. Como 𝑝ⱼ é escolhido para ser pequeno, o 𝑚ⱼ pode ser recuperado por pesquisa exaustiva, ou seja, comparando E (𝑚ⱼ) para
para 𝑧 ∈ {1, . . . , 𝑝ⱼ – 1}. Obtemdo 𝑚ⱼ para cada 𝑗, segue que 𝑚 pode ser recuperado aplicando diretamente o Teorema do Resto Chinês.
Homomorfismo: sejam 𝑚1 e 𝑚2 mensagens, então
Ataque: como nos métodos anteriores, para resolver o problema da fatoração de inteiros utilizamos GNFS.
3.5 Okamoto-Uchiyama
Em Okamoto, T. & Uchiyama, S. (1998) aparece a proposta de um novo esquema de PHE para melhorar o desempenho computacional, alterando o conjunto onde as criptografias dos esquemas anteriores de HE funcionam e preservam o domínio dos esquemas citados anteriores. Este esquema trabalha no grupo multiplicativo de números inteiros módulo , com 𝑁 definido como 𝑁 = 𝑝2𝑞, onde 𝑝 e 𝑞 são números primos grandes.
Geração das Chaves: escolha um número inteiro aleatório de modo que
Calcule
, onde 𝒽 é um parâmetro para melhorar o desempenho de cifrar, desde que 𝒽 possa ser calculado facilmente para 𝑔 e N.
A chave pública: (N, 𝑔, 𝒽).
A chave secreta: (𝑝, 𝑞).
Cifrar: utilizando a chave pública, considere 𝑚 < 𝑝 e escolha um número inteiro aleatório 𝑟 ∈ {1, . . . ,N − 1} tal que
Decifrar: considere o logaritmo discreto (Borges, F., Portugal, F. & Lara, S. (2007)) com base 𝑔𝑝–1 o grupo é um isomorfismo entre dois grupos ( grupo cíclico H ao grupo aditivo ℤ/𝑝ℤ), ou seja,
para cada 𝑢 do subgrupo ℤ*𝑝2.
Homomorfismo: sejam 𝑚1 e 𝑚2 mensagens, então
Ataque: assim como nos casos anteriores, o algoritmo para resolver o problema da fatoração de inteiros é o GNFS.
3.6 Paillier
Este esquema de criptografia probabilístico é baseado na classe quadrática de resíduos, veja Paillier (1999), verificando se existe um número inteiro 𝑥 tal que 𝑥𝑛 ≡ 𝑎 mod 𝑛2 para um dado inteiro 𝑎.
Geração das Chaves: sejam os números primos grandes 𝑝 e 𝑞 de modo que Sejam
Escolhemos aleatoriamente 𝑔 ∈ ℤ*𝑛2 e verificamos se onde a função L é definida por
para cada 𝑢 do subgrupo ℤ*𝑛2.
A chave pública: (𝑛, 𝑔).
A chave secreta: (𝑝, 𝑞).
Cifrar: sejam 𝑚 uma mensagem e 𝑟 um número escolhido aleatoriamente, então
Decifrar: utilizando a mensagem cifrada E(𝑚) e a função L obtemos
Homomorfismo: sejam , obtemos
Como podemos ver, o esquema de Paillier não permite a multiplicação homomórfica em mensagens cifradas, ou seja, é apenas homomórfico sobre a adição.
Ataque: Como nos métodos anteriores, o algoritmo mais indicado para resolver o problema da fatoração de inteiros é o GNFS.
3.7 Damgård-Jurik
Este esquema é uma generalização do esquema de Paillier Damgård, I., & Jurik, M. (2001) sem perda da propriedade homomórfica, porém utilizando potências mais altas de 𝑛. Uma aplicação deste método é em votação eletrônica1.
Geração das Chaves: escolha aleatoriamente dois números primos grandes 𝑝 e 𝑞 e distintos. Seja 𝑛 = 𝑝𝑞 (como no esquema de RSA) e (como no esquema de Paillier). Escolha um elemento
(o grupo quociente G/H onde G é cíclico mod 𝑛s enquanto H é isomorfo a ℤ*𝑛) tal que
para j conhecido primo relativo de 𝑛 e 𝑥 ∈ 𝘏.
Usando o Teorema do Resto Chinês, escolha tal que
e
. Por exemplo, 𝑑 poderia ser
para algum
caso 𝑠 seja igual a 1 obtemos o esquema original de Paillier.
A chave pública: (𝑛, 𝑔).
A chave secreta: 𝑑.
Cifrar: seja . Selecione um número randômico
tal que
Decifrar: utilizando a mensagem cifrada E(𝑚) e a chave secreta 𝑑 obtemos
Após este processo, substituímos E (𝑚)𝑑 por e efetuamos novamente os cálculos utilizando um algoritmo para resolver o expoente, consultar Damgård, I., & Jurik, M. (2001), assim
Portanto, obtemos a expressão desejada,
Homomorfismo:
Ataque: Como este esquema é uma generalização do esquema de Paillier, o melhor algoritmo para a fatoração é o GNFS.
4 ANÁLISE DAS COMPLEXIDADES DE PHE
Nesta seção, apresentaremos o cálculo das complexidades de tempo de cada algoritmo do seguinte modo: cifrar, decifrar, homomorfismo e ataque. Assim, a complexidade de um algoritmo é uma estimativa do tempo necessário à execução, que esse algoritmo expressa em função das operaçõees aritméticas fundamentais, e do tamanho dos dados de entrada. Abaixo trataremos do cálculo das complexidades dos algoritmos de criptografia de chave pública de PHE, proposto na seção 3. Mostraremos qual o melhor ataque para cada esquema de PHE.
4.1 Performance de PHE
Nesta subseção, descreveremos como efetuamos os cálculos das complexidades dos algoritmos contidos na seção 3. Analisaremos, a complexidade do processo de cifrar mensagens e em seguida os demais processos.
As complexidades de cifrar são: no esquema de RSA, pois executa uma exponenciação modular e consideramos ℯ um valor bem pequeno,
no esquema de Elgamal, pois necessita de duas exponenciações modulares mod 𝑛 e uma multiplicação por escalar
para os esquemas de Benaloh e Naccache-Stern, portanto, necessitam de duas exponenciações modulares mod 𝑛. Além disso, se o esquema computa o produto de exponenciações modulares, então o esquema pode ser otimizado Borges, F., Lara, P., & Portugal, R. (2017).
Notamos que as complexidades de cifrar dos métodos citados acima, são exceto o algoritmo de RSA que é ℯ, onde ℯ = 65537, Pereira, D., Aranha, M., & Borges, F. (2019).
O cálculo das demais complexidades de cifrar são: para o esquema de Okamoto-Uchiyama, pois executa duas exponenciações modulares mod N uma inversão e uma exponenciação modular
esquema de Paillier
no esquema de Damgård-Jurik, se considerarmos 𝑠 = 1 obtemos uma versão do esquema de Paillier, assim, a complexidade é
para cifrar, igual a de Paillier.
Trataremos da complexidade do processo de decifrar de cada esquema. A complexidade de decifrar é para os seguintes esquemas: RSA considerando ℯ < 𝑛 que executará uma exponenciação modular, Elgamal onde 𝑛 é a ordem do grupo, ou seja, uma exponenciação modular e uma inversão e Naccache-Stern de uma exponenciação modular e uma divisão usual sobre inteiros, bem como a aplicação do teorema do Resto Chinês, ou seja,
consideraremos j = 4, para decifrarmos corretamente. Para o esquema de Benaloh a complexidade é
, onde
é o número de bits de i, executará uma inversão e uma exponenciação modular, consideraremos l ≤ 2, caso contrário, teremos problemas para decifrar.
Decifrando o esquema de Okamoto-Uchiyama temos que a complexidade é executando duas exponenciações modulares divididas por duas exponenciações modulares mod N e mais uma mod p A divisão é usual sobre inteiros e torna-se mais rápida. Além disso, o esquema de Paillier tem como complexidade para decifrar de duas exponenciações modulares divididas por duas exponenciações modulares mod 𝑛2 e mais uma mod 𝑛. A divisão é usual sobre inteiros, ou seja,
No esquema de Damgård-Jurik para decifrar a complexidade é de
, ou seja, uma exponenciação modular. Se 𝑠 ≥ 1, então 𝑠 =1 recai no esquema de Paillier, consideraremos 𝑠 = 2, assim para decifrar obtemos a complexidade
.
No homomorfismo utilizamos operações ou aditivas ou multiplicativas em cada esquema. Assim, executamos uma multiplicação modular (MM), nos seguintes esquemas: RSA, Benaloh, Naccache-Stern, Okamoto-Uchiyama, Paillier e Damgård-Jurik. Além disso, no esquema de Elgamal executamos duas multiplicações modulares, uma em cada coordenada da mensagem cifrada.
Como o esquema dos autores Naccache-Stern é probabilístico a chance de decifrar a mensagem corretamente é de sendo assim, 𝑘 deve ser pequeno, pois assim, a probabilidade é maior de recuperar a mensagem cifrada. Por exemplo, escolhendo K = 4 obtemos sucesso, os resultados estão contidos na Tabela 3, onde 𝑛 = 64 bits. Se escolhemos K =16 e 𝑛 = 128 bits, o tempo de execução de decifrar é 2.055𝑚𝑠, para cifrar é 0.036𝑚𝑠 e homomorfismo de 0.088𝑚𝑠. Por outro lado com k = 36, o tempo de cifrar é 0.168ms e do homomorfismo 0.289𝑚𝑠. Portanto, quanto maior o valor de 𝑘, maior será o tempo de execução e também terá mais dificuldades para decifrar o esquema. Além disso, devemos escolher valores que sejam múltiplos de dois, pois 𝑔 tem a ordem de
Na Tabela 3, apresentamos um resumo geral dos esquemas com as suas respectivas complexidades.
Na Tabela 4, apresentamos as complexidades aproximadas, representando o custo de processamento de cada etapa dos esquemas de PHE. As informações fornecidas facilitam a comparação entre os diferentes algoritmos de PHE.
Tabela 3 – Complexidade dos esquemas de PHE
Fonte: autores (2024)
Tabela 4 – Aproximação do custo de cada processo dos esquemas de PHE
Fonte: autores (2024)
Os melhores esquemas de cifragem são o Elgamal e Benaloh, pois suas complexidades são . Como 𝑛 = 𝑝𝑞 é o produto de dois números primos e
, ou seja N > 𝑛 temos a seguinte aproximação:
Portanto, o esquema mais eficiente para decifrar é o Okamoto-Uchiyama. Analisando os esquemas aditivos de PHE, o mais eficiente é o Okamoto-Uchiyama, pois possui a mesma complexidade tanto para cifrar quanto para decifrar. Embora sua complexidade seja
esse esquema se destaca pela sua eficiência. O método de Paillier retorna a mensagem decifrada mod 𝑛2 enquanto o esquema de Damgård-Jurik utiliza mod 𝑛𝑠 para cifragem e 𝑛𝑠+1 para decifração, ou seja, usa valores de 𝑛 de alta ordem, tornando-se mais lento que o Okamoto-Uchiyama.
No que diz respeito aos algoritmos multiplicativos de PHE, o mais eficiente é o RSA,pois executa uma exponenciação modular tanto para cifrar quanto para decifrar, além de uma multiplicação modular no homomorfismo. A complexidade para cifrar é onde , onde ℯ < 𝑛 enquanto para decifrar é
. Já o esquema de Elgamal exige o dobro de exponenciações modulares, tornando-o mais custoso.
Na Figura 2, obtemos o gráfico dos processos de cifrar, decifrar e homomorfismo de cada esquema proposto neste trabalho, com base nos resultados da Tabela 4, consideramos 𝑛 = 2048 bits para execução, exceto no algoritmo de Naccache-Stern, que é de 𝑛 = 64 bits.
Figura 2 – Complexidade dos Esquemas de PHE
Fonte: autores (2024)
Os melhores esquemas de criptografia para operações homomórficas em PHE podem ser classificados com base em suas características específicas. Para operações multiplicativas, o esquema RSA é amplamente utilizado, enquanto para operações aditivas, os esquemas Benaloh e Okamoto-Uchiyama se destacam pela sua eficácia e segurança. Além disso, o esquema Naccache-Stern é notável devido à sua complexidade de tempo . Considerando que 𝑛 = 𝑝 . 𝑞, onde 𝑝 e 𝑞 são números primos, e
, com N > 𝑛, a aproximação
é válida.
No que diz respeito à decodificação, o algoritmo mais eficiente é o esquema Benaloh. Já para o cálculo do homomorfismo, o esquema Damgård-Jurik se destaca como o mais eficaz, apesar de envolver uma multiplicação modular mod 𝑛𝑠. Caso 𝑠 = 1, o esquema recai no Paillier, pois 𝑛𝑠 = 𝑛2 o que leva à suposição de que 𝑠 > 1 para garantir que o esquema de Damgård-Jurik mantenha sua eficiência.
Analisando os algoritmos aditivos de PHE o melhor é o esquema de Damgård-Jurik utiliza para cifrar mod 𝑛𝑠 e para decifrar 𝑛𝑠+1 , ou seja, 𝑛 de alta ordem, este esquema é mais eficiente. O método de Paillier retorna a mensagem decifrada mod 𝑛𝑠. Sendo assim mais lento que o algoritmo de Damgård-Jurik e Okamoto-Uchiyama. Além disso, Okamoto-Uchiyama tem complexidade de e possui a mesma complexidade para cifrar e decifrar.
O melhor algoritmo multiplicativo de PHE é o RSA, pois executa uma exponenciação modular para cifrar e outra para decifrar, bem como uma multiplicação modular no homomorfismo e a complexidade para cifrar é log (ℯ)onde ℯ < 𝑛 e para decifrar é log (𝑛). No esquema de Elgamal temos o dobro de exponenciações modulares.
4.2 Ataque
O algoritmo mais eficiente baseado em fatoração de números inteiros é o General Number Field Sieve. Os esquemas propostos neste trabalho, e baseados neste ataque são: RSA, Elgamal, Naccache-Stern, Okamoto-Uchiyama, Paillier e Damgård-Jurik.
Apresentamos a complexidade de tempo deste ataque na equação (5). O melhor algoritmo de ataque para o esquema de Benaloh é Pollard ρ. A complexidade deste ataque pode ser obtida na equação (12). Na Figura 3, representamos os gráficos das complexidades dos ataques de GNFS e Pollard ρ.
Figura 3 – Complexidade dos Ataques: GNFS e Pollard ρ
Fonte: autores (2024)
Este trabalho revisa os principais algoritmos criptográficos assimétricos aplicados a esquemas de Criptografia Homomórfica (PHE). Além disso, apresenta uma análise detalhada das complexidades teóricas e das implementações práticas de cada etapa dos esquemas criptográficos, incluindo as operações de cifragem, decifragem, homomorfismo e ataques. A análise abrange os algoritmos de PHE: RSA, Elgamal, Benaloh, Naccache-Stern, Okamoto-Uchiyama, Paillier e Damgård-Jurik. Os resultados indicam que o RSA é o esquema mais eficiente para operações multiplicativas, enquanto o Okamoto-Uchiyama se destaca como o melhor para operações aditivas.
Agradeço a agência de fomento CNPQ e a Petrobras pelos auxílios financeiros.
Acar, A., Aksu, H., Uluagac, A. S., &Conti, M. (2018). A survey on homomorphic encryption schemes: Theory and implementation. ACM Comput. Surv., 51(4), 79:1–79:35.
Borges, F., Lara, P., & Portugal, R. (2017). Parallel algorithms for modular multiexponentiation. Applied Mathematics and Computation, 292, 406–416.
Borges, F., Portugal, F.&Lara, S. (2007). Autenticação e o problema do logaritmo discreto. Revista HÍfen, 31(59/60), 106–111. http://revistaseletronicas.pucrs.br/fo/ojs/index.php/hifen/article/view/3884.
Clarkson, J. B. (1994). Dense probabilistic encryption. In Proceedings of the Workshop on Selected Areas of Cryptography. (pp. 120-128). Clarkson University.
Damgård, I., & Jurik, M. (2001). A generalisation, a simplication and some applications of paillier’s probabilistic public-key system. In Kim, K., editor, Public Key Cryptography. (pp. 119-136). Springer Berlin Heidelberg.
Elgamal, T. (1985). A public key cryptosystem and a signature scheme based on discrete logarithms. In Goos, G. Hartmanis, J., editor, Proceedings of CRYPTO 84 on Advances in Cryptology. (pp. 469 - 472). Springer-Verlag.
Fousse, L., Lafourcade, P., & Alnuaimi, M (2011). Benaloh’s dense probabilistic encryption revisited. In Vaudenay, S., & Petit, C., editor, Progress in Cryptology – AFRICACRYPT 2011. (pp. 348-362). Springer Berlin Heidelberg.
Goldwasser, S. & Micali, S. (1982). Probabilistic encryption & how to play mental poker keeping secret all partial information. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing. (pp. 365–377). Association for Computing Machinery.
Halevi, S. (2017). Homomorphic encryption. In Lindell, Y., editor, Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich. (pp. 219–276). Springer International Publishing. https://doi.org/10.1007/978-3-319-57048-8 5.
Kawachi, A., Tanaka, K., & Xagawa, K. (2007). Multi-bit cryptosystems based on lattice problems. In Okamoto, T., & Wang, X., editor, Public Key Cryptography – PKC 2007. (pp. 315-329). Springer Berlin Heidelberg.
Lara, P., & Borges, F. (2008). O algoritmo de fatoração gnfs. In Congrasso Nacional de Matemática Aplicada e Computacional. Coordenação de Sistemas e Redes. http://www.sbmac.org.br/eventos/cnmac/xxxi cnmac/PDF/316.pdf.
Naccache, D. & Stern, J. (1998). A new public key cryptosystem based on higher residues. In Liu, P., Basin, D. A., & Feng, D., editor, Proceedings of the 5th ACM Conference on Computer and Communications Security. (pp. 59–66). Association for Computing Machinery.
Okamoto, T. & Uchiyama, S. (1998). A new public-key cryptosystem as secure as factoring. In Nyberg, K., editor, Advances in Cryptology — EUROCRYPT 98. (pp. 308-318). Springer Berlin Heidelberg.
Paillier, P. (1999). Public-key cryptosystems based on composite degree residuositymclasses. In Stern, J., editor, Advances in Cryptology — EUROCRYPT ’99. (pp.223–238).nSpringer Berlin Heidelberg.
Pandey, G. (2014). A guide to general number field sieve for integer factorization.Investigations in Mathematical Sciences, 4, 83–98.
Pereira, D., Aranha, M., & Borges, F. (2019). HTTPS Keys in the Mediterranean. In 2019 IImWorkshop on Metrology for Industry 4.0 and IoT (MetroInd4.0IoT). (pp. 449–454). IEEE.
Rivest, R. L., Adleman, L. & Dertouzos, M. L. (1978). On data banks and privacy homomorphisms. In DeMillo, R. A., editor, Foundations of Secure Computation. (pp. 169-180). Academia Press.
Rivest, R. L., Shamir, A. & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 21(2), 120–126.
Teske, E. (1998). Speeding up pollard’s rho method for computing discrete logarithms. In Buhler, J. P., editor, Algorithmic Number Theory. (pp. 541-554). Springer Berlin Heidelberg.
Como citar este artigo
Lunkes, A. D. L. Z., & Oliveira, F. B. (2025). Análise da complexidade dos algoritmos de Criptografia Homom´orfica. Ciência e Natura, Santa Maria, v. 47, e87825. DOI: https://doi.org/10.5902/2179460X87825.