Compartilhamento de tecnologia

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Recursos de aprendizagem:
Criptografia Totalmente Homomórfica I: Teoria e Fundamentos (Professor Yu Yu da Universidade Jiao Tong de Xangai)
Criptografia Totalmente Homomórfica II: Teoria e Construção da Criptografia Totalmente Homomórfica (Professor Xiang Xie)

---

Hoje em dia, os esquemas de criptografia totalmente homomórficos de segunda geração (como BGV e BFV) e de terceira geração são todos baseados em LWE. Agora, os esquemas totalmente homomórficos avançados também são baseados em LWE, portanto, este artigo resume o conhecimento básico de LWE.
Primeiro considere, queremos criptografar um número$e$, agora usando uma série de$a_{eu}$certo$e$Criptografe e obtenha$a_{eu}e$, na verdade, pode ser resolvido resolvendo o máximo divisor comum GCD$e$ .No entanto, se um ruído aleatório for adicionado$e_{eu}$,pegar$a_{eu}e+e_{eu}$, então será difícil resolver$e$ valor. Este processo é meu entendimento simples do LWE. O chamado erro é um ruído.

O processo de cálculo da criptografia totalmente homomórfica é dividido em três etapas: geração de chave KeyGen, criptografia Enc, cálculo homomórfico Eval e descriptografia Dec. ,

Geração de chaves:

Primeiro construa a equação acima,$e\cdot A+e=eA+e$e, em seguida, obtenha a chave pública pk ($-A$e$eA+e$emenda) e a chave privada sk ($e$ e 1 emenda). Portanto, obtém-se que o resultado da multiplicação entre pk e sk é um ruído aleatório e (próximo de 0).

Enc：

A chave pública pk usada para criptografia, r é um vetor aleatório contendo apenas 0 ou 1, e m é a informação a ser criptografada (colocada no bit mais baixo do vetor).

Dez：

Depois de calcular o produto interno da chave privada sk usada para descriptografia e ct, encontre o mod 2 para obter o resultado da descriptografia.

Prova de correção:

Multiplique sk e pk para obter 2e (a condição atendida por KeyGen) e, em seguida, faça o produto interno com r para obter um pequeno ruído uniforme. O resultado final é m + um pequeno ruído uniforme, para que o ruído possa ser eliminado pelo mod 2. Obtenha o resultado da descriptografia m. É por isso que o ruído construído é 2e, não e. Meu entendimento é que, ao construir ruído aleatório de número par, é conveniente usar o mod 2 para eliminar o ruído durante a descriptografia.

Prova de segurança:

Quando pk é pseudo-aleatório e r tem entropia suficientemente alta (isto é, a aleatoriedade é forte?), tanto pk quanto pk vezes r são pseudo-aleatórios. Depois de adicionar vetores naturais e com m, o resultado da criptografia também é pseudo-aleatório.

A seguir está a descrição estereotipada do professor Xiang Xie:
Fórmula de criptografia: texto cifrado c = chave pública pk ✖️ aleatório r + texto simples m
Fórmula de descriptografia: texto simples m = <texto cifrado sk, chave privada sk> mod q mod 2

Nesta base, o mod 2 pode ser usado para descriptografar o valor do texto simples m. Contanto que o ruído seja pequeno o suficiente, a precisão pode ser garantida.
Há algo que precisa ser distinguido aqui: o acima$PE=(A,b=A{e}^{\prime }+2e)$é a solução BGV, e BFV é$PE=(A,b=A{e}^{\prime }+e)$, a diferença é que o BGV codifica informações em bits baixos, enquanto o BFV codifica mensagens em bits altos (será explicado ao aprender BFV).

Eval (homomorfismo aditivo e homomorfismo multiplicativo):

Observe que a adição ou multiplicação homomórfica trará acúmulo significativo de ruído, e a multiplicação tem uma tendência de crescimento quadrática.
Então vamos falar sobre como descriptografar o resultado da multiplicação homomórfica. Você pode ver a seguinte fórmula: A multiplicação de dois textos cifrados é equivalente a fazer o produto tensorial do texto cifrado e da chave privada respectivamente, e então fazer o produto interno. Obviamente, tanto o texto cifrado quanto a chave privada dobraram de tamanho. O exemplo é uma prova de equivalência.

Portanto, a questão é: como restaurar o tamanho do texto cifrado e o tamanho da chave privada após a multiplicação homomórfica? Este é o problema que a troca de chave resolve.

A seguir está a descrição do professor Xiang Xie:

Troca de Chaves

O objetivo é restaurar o tamanho do texto cifrado e da chave privada para um tamanho linear.

Agora encontre a multiplicação dos textos cifrados c1 e c2:

O processo acima é baseado no conceito de decomposição de bits:

A seguir está a descrição do professor Xiang Xie:

O objetivo da troca de chave: converter a chave privada$\tilde{e}$abaixo$\tilde{c}$ Converter para chave privada$e$abaixo$c$,e$\tilde{c}$e$c$Eles são todos criptografados com o mesmo texto simples.
Um conceito central aqui é Key Switching Key (KSK), que significa usar uma chave privada$e$criptografar$\tilde{e}$。

Através do processo de troca de chave, a chave privada pode ser derivada de$e\otimes e$tornou-se linear$e$, enquanto o texto cifrado muda de$\tilde{c}$tornou-se linear$c$ .E pode ser visto na última linha da fórmula que após a troca de chave$⟨c,e⟩$e o original$⟨\tilde{c},e\otimes e⟩$Há uma diferença de ruído entre$2{\tilde{c}}^E\tilde{e}$ , esta parte pode ser muito grande! Portanto, ainda não há como implementar a troca de chave aqui.

Uma matriz de gadget G é introduzida aqui:

Portanto, o processo de troca de chave passa a ser o seguinte:

Neste ponto, o erro adicionado é muito pequeno.
Resumindo, através da troca de chave, a chave privada original$\tilde{e}=e\otimes e$abaixo$\tilde{c}=c\otimes c$, é convertido em uma chave privada$e$abaixo$c$, preste atenção à chave após a troca de chave$e,c$Eles não são os valores originais (verifique novamente).

Para BGV, o ruído de adição aumenta linearmente e o ruído de multiplicação aumenta quadradamente. Embora a comutação de chave possa suportar a multiplicação (limitando sk para se tornar extremamente grande), o ruído é na verdade um ruído muito pequeno adicionado ao ruído de multiplicação original. também é muito grande. Portanto, esse ruído precisa ser ainda mais reduzido.

Redução do módulo

Neste ponto, os cálculos de multiplicação e adição homomórfica com uma pequena profundidade foram implementados através do LWE, usando uma nova chave para cada camada. No entanto, à medida que a profundidade do cálculo se aprofunda, a expansão do ruído é explosiva, por isso ainda não está nivelada. . FHE (pode calcular FHE em uma profundidade especificada).
Agora esperamos implementar um FHE que possa calcular uma certa profundidade sem usar bootstrap, o que requer conversão de módulo.

Não entendo muito bem o processo intermediário. Resumindo, é transformar o texto cifrado c do domínio módulo q para o domínio módulo p (p<).
Aqui está um exemplo específico:
Se a Redução do Módulo não for realizada, o ruído crescerá em uma tendência exponencial dupla à medida que a profundidade se aprofunda, e erros de descriptografia ocorrerão após o nível >= 3.

Se a Redução do Módulo for realizada em cada nível, o ruído também será mantido dentro de uma faixa de valor absoluto, ao custo de uma redução contínua do módulo.

Então, se você deseja implementar um FHE nivelado, você pode definir um módulo$B^e$, então você pode calcular uma profundidade de$e$circuito (onde$B$ é o limite superior de ruído do texto cifrado atualizado).Calculado$e$Após a profundidade, o módulo deve ser reduzido para$B$ , para garantir que não haja nenhum erro na descriptografia neste momento. BGV é um FHE nivelado.