Aplicar operações homomórficas em grandes dados criptografados

Aug 18 2020

Atualmente experimentando criptografia homomórfica usando a biblioteca PALISADE .

Quero aplicar operações simples, como adições e multiplicações em grandes entradas criptografadas. Por exemplo, a entrada A[3200]e a entrada de B[4096]vetores / matrizes de valores int são criptografados. Com essas duas entradas Enc(A)e Enc(B)quero aplicar uma multiplicação:

EvalMult(Enc(A[0]), Enc(B[42])) 

*0 and 42 denoting the indexes of the corresponding inputs
** no SIMD needed

No que me diz respeito, a implementação dos requisitos descritos acima pode ser resolvida de duas maneiras diferentes:

  1. Empacote as entradas em um único texto cifrado (tipo SIMD) e para as operações que eu poderia usar EvalIndexAt()para obter o valor correto da entrada criptografada.

  2. Criptografe cada valor de A e B separadamente.

Não tenho certeza de qual das soluções descritas seria a melhor em termos de eficiência . A primeira abordagem tem a grande vantagem de que apenas um processo de criptografia para toda a entrada é necessário, mas isso vem com a desvantagem de que sempre tenho que acessar o elemento correto usando o EvalAtIndex()método e quanto maiores as entradas, mais lento o cálculo dos resultados EvalAtIndexKeyGen(). (Pelo menos na minha máquina)

A segunda abordagem parece se encaixar melhor porque EvalAtIndex()não é necessária, mas ela vem com o custo de criptografar cada valor separadamente, o que leva algum tempo.

Alguma recomendação de pensamentos?

Respostas

1 YuriyPolyakov Aug 19 2020 at 15:00

Obrigado pela pergunta.

O principal benefício da abordagem nº 1 (SIMD) é que você pode realizar adição e multiplicação de vetores (de 4096 ou mais inteiros / números reais) usando uma única adição ou multiplicação homomórfica (muito eficiente). Rotação (chamada EvalAtIndexem PALISADE) é uma operação extra que permite acessar índices individuais ou fazer soma eficiente (como no produto interno), multiplicação de matriz, etc. Esta abordagem também tem um fator de expansão de texto cifrado muito menor (por 4096x ou mais) do que abordagem # 2. Geralmente a opção nº 1 é preferida na prática (e não consigo pensar em nenhum caso de uso real em que eu gostaria de ir com a opção nº 2).

Para minimizar o custo de multiplicação, talvez você possa compactar o vetor em blocos contíguos de modo que precise de uma única rotação para um bloco. Por exemplo,

EvalMult(Enc(A[0:5]),Enc(B[42:47))

Outra técnica que você pode usar é EvalFastRotation(disponível apenas para CKKS e BGVrns no PALISADE v1.10.x). Se você precisar de várias rotações do mesmo texto cifrado, pode pré-calcular algo para o texto cifrado e, em seguida, usar rotações mais baratas (o maior benefício é obtido para a troca de chave BV) - consultehttps://gitlab.com/palisade/palisade-development/-/blob/master/src/pke/examples/advanced-real-numbers.cpp Por exemplo.

Existem também maneiras de minimizar o número de chaves a serem geradas se você precisar de várias rotações (calcule apenas cerca de uma raiz quadrada do número de rotações necessárias), por exemplo, usando a técnica de passo de bebê, passo gigante, descrita em https://eprint.iacr.org/2018/244 (essas técnicas podem ser implementadas em seu aplicativo baseado em PALISADE).

Você também pode usar uma ordem especial de empacotamento de um vetor se o padrão para realizar a multiplicação for conhecido (desta forma, sua rotação irá preparar vários blocos através do vetor usando uma única operação de rotação). As rotações são cíclicas (agrupamento) em CKKS e BGVrns quando os # slots de texto simples (tamanho do lote) é igual a ring dimension/ 2. Se você tiver um vetor menor do que isso, você sempre pode clonar / replicar o vetor pequeno quantas vezes forem necessárias para preencher ring dimension/ 2.

Em resumo, a maior melhoria de eficiência pode ser alcançada se você pensar em seu problema em termos de vetores do tipo SIMD. Em seguida, você pode reformular seu problema / modelo para aproveitar ao máximo o conjunto de ferramentas que o HE oferece. De certa forma, isso é semelhante à programação usando instruções vetorizadas, por exemplo, AVX ou programação orientada a matriz (como em MATLAB).