Esquemas BGV e BFV para operações com inteiros

BGV (Brakerski-Gentry-Vaikuntanathan, 2012) é um esquema de FHE em níveis baseado em RLWE. Ele é compatível com adições e multiplicações arbitrárias sobre textos claros inteiros empacotados. "Em níveis" significa que ele processa circuitos de até uma profundidade fixa L sem reinicialização.

BGV e BFV codificam textos claros como polinômios em Z_t[x]/(x^n+1), em que t é um módulo pequeno do texto claro (por exemplo, t=65537). Cada polinômio codifica n valores inteiros, um por coeficiente. A aritmética sobre os textos cifrados opera simultaneamente em todos os n valores — paralelismo SIMD.

O BGV reduz o ruído por meio da troca de módulo: após cada multiplicação, o módulo do texto cifrado q é reduzido de Q_L para Q_{L-1}. Isso divide o ruído por Q_L/Q_{L-1}, mantendo-o dentro dos limites que permitem a descriptografia. A profundidade L do circuito corresponde a L níveis de módulo.

BFV (Brakerski/Fan-Vercauteren, 2012) é semelhante ao BGV, mas usa uma estratégia diferente de gerenciamento de ruído: invariância de escala. O BFV não exige troca de módulo; em vez disso, ele reescala o texto cifrado após a multiplicação. É mais simples de implementar e usado no Microsoft SEAL.

Por meio do Teorema Chinês do Resto sobre o anel do texto claro, cada texto cifrado pode conter n/2 valores inteiros independentes (posições). Uma operação de adição de textos cifrados adiciona todos os n/2 pares em paralelo. Uma multiplicação multiplica todos os pares. Vazão: n/2 operações com inteiros por operação sobre texto cifrado.

Após multiplicar dois textos cifrados de grau 1, o resultado tem grau 2 (3 componentes). A relinearização usa chaves de avaliação (chaves de relinearização) para converter o resultado de volta ao grau 1, ao custo de ruído adicional. Essa etapa é necessária após cada multiplicação.

from seal import EncryptionParameters, scheme_type, SEALContext, KeyGenerator, Encryptor, Evaluator, Decryptor parms = EncryptionParameters(scheme_type.bfv) parms.set_poly_modulus_degree(4096) parms.set_coeff_modulus(CoeffModulus.BFVDefault(4096)) parms.set_plain_modulus(PlainModulus.Batching(4096, 20))

A rotação do texto cifrado desloca ciclicamente as n/2 posições do texto claro. É útil para: redução por soma (acumular todas as posições em uma), multiplicação matriz-vetor (rotacionar e acumular) e convoluções (deslocar e multiplicar). Requer chaves de Galois (chaves de rotação pré-calculadas).

BFV com n=8192: adição de aproximadamente 10 µs e multiplicação de aproximadamente 5 ms (com relinearização). Reinicialização, se necessária: 30-60 segundos. Lote de 4096 inteiros: aproximadamente 1 µs amortizado por inteiro em cada multiplicação. Inviável em tempo real, mas viável para análises offline.

Ao escolher n e q: o SEAL recomenda n=4096 para segurança de 128 bits com Q < 2^109; n=8192 para circuitos maiores. O padrão de HE (homomorphicencryption.org) fornece tabelas de parâmetros. Utilize sempre os parâmetros recomendados — escolhas personalizadas podem comprometer facilmente a segurança.

Consultas a bancos de dados criptografados (pesquisar registros criptografados sem descriptografá-los). Análise genômica privada (calcular estatísticas sobre DNA criptografado). Agregações financeiras criptografadas (somar saldos de contas criptografados sem visualizar os indivíduos). Avaliação segura de modelos.

BGV e BFV realizam aritmética inteira criptografada usando RLWE. A codificação em lote fornece paralelismo SIMD. O BGV usa troca de módulo; o BFV usa invariância de escala. A relinearização restaura o grau após a multiplicação. Próximo: CKKS para aritmética aproximada e aprendizado de máquina.