Cálculo multipartidário seguro do número de 1s vezes o número de 0s em uma sequência compartilhada

Suponha que haja partes , cada uma com um pouco . Eu quero calcular a multiplicação do número de vezes o número de zeros, ou seja, .p j b j ∈ { 0 , 1 } R = ( ∑ b j ) × ( N - ∑ b j$N>2$$p_j$$b_j\in{\{0,1\}}$$R=(\sum{b_j})\times(N-\sum{b_j})$

O cálculo deve ser seguro no sentido de que nenhum partido pode aprender mais do que o resultado final . Por exemplo, não há problema em executar uma soma segura, porque então se tornará conhecido e a soma é sensível no meu problema. Então, existe algum protocolo de computação seguro existente que atenda à demanda?∑ b $R$$\sum{b_j}$

Edit: O número no problema é grande, pelo menos mais de . É necessária uma computação multipartidária segura e eficiente. Um protocolo de soma segura pode ser eficiente, mas SMC genérico, como circuitos booleanos, pode exigir muita computação. Então, eu preciso de um protocolo eficiente.$N$$1000$

Esta resposta é sobre soluções viáveis ​​baseadas em criptografia homomórfica que NÃO é totalmente homomórfica, pois a última pode ser extremamente ineficiente (se houver sistemas criptográficos eficientes e totalmente homomórficos comparáveis ​​aos fornecidos abaixo em termos de eficiência, ficaria feliz em ouvir sobre eles).

Como você só precisa de uma multiplicação, existem soluções potencialmente mais baratas que a criptografia totalmente homomórfica: [1] e [2]. O último funciona em decomposições de bits criptografadas da entrada, portanto, será necessário um protocolo de decomposição de bits como [3] e [6], mas o primeiro funciona com valores inteiros. Apenas para completar, o primeiro foi estendido para a multiplicação do operado em [4], mesmo que o OP possa não precisar disso. Essas soluções não são interativas e devem funcionar no caso de duas partes.$d$

Se você tiver mais de duas partes e puder pagar alguma interação, [5] fornecerá uma "porta de multiplicação segura" que é potencialmente mais eficiente e permite um número ilimitado de multiplicações. Funciona basicamente convertendo os valores criptografados homomorficamente em algum tipo de compartilhamento secreto, multiplica o resultado (interativamente) e depois o converte novamente em criptografia homomórfica.

[1] Avaliando fórmulas 2-DNF em textos cifrados

[2] Criptocomputador não interativo para NC1

[3] Computação multilateral segura incondicionalmente com rodadas constantes para igualdade, comparação, bits e exponenciação

[4] Criptografia aditivamente homomórfica com multiplicações do d-operando

[5] Computação multipartidária a partir da criptografia homomórfica de limite

[6] Conversão binária eficiente para valores criptografados em Paillier

Nova resposta (24/10): Acho que o artigo a seguir fornece uma solução elegante e eficiente para o seu problema:

• Avaliação de fórmulas 2-DNF em textos cifrados, Dan Boneh, Eu-Jin Goh, Kobbi Nissim, TCC 2005.

Eles mostram como criar um algoritmo de criptografia de chave pública com as duas propriedades úteis a seguir:$E(\cdot)$

• Aditivamente homomórfico. Dados e E ( y ) , qualquer um pode calcular E ( x + y ) .$E(x)$$E(y)$$E(x+y)$

• Pode multiplicar (uma vez). Dado e E ( y ) (nenhum dos quais foi gerado como resultado de uma operação de multiplicação), qualquer um pode calcular E ( x ⋅ y ) . Você pode usar o resultado em operações de adição, mas não pode usá-lo em nenhuma operação de multiplicação (o resultado de uma multiplicação está corrompido e os valores contaminados não podem ser usados ​​como entrada para outra multiplicação).$E(x)$$E(y)$$E(x \cdot y)$

A conseqüência é que, dado um polinômio quadrático multivariado e dado E ( x 1 ) , … , E ( x n ) , qualquer um pode calcular uma criptografia de Ψ ( x 1 , … , x n ) . Isso é super útil para a sua situação.$\Psi(x_1,\dots,x_n)$$E(x_1),\dots,E(x_n)$$\Psi(x_1,\dots,x_n)$

Em particular, em sua situação, podemos formar o polinômio Observe que este é um polinômio quadrático multivariado, portanto, considerando todos os E ( b i ) , qualquer um pode calcular E ( Ψ ( b 1 , … , b N )

Isso sugere um protocolo natural para o seu problema, usando uma versão de limite do esquema de criptografia no documento mencionado acima:

• Todos juntos geram um par de chaves pública / privada para uma versão limiar desse esquema, de modo que a chave pública seja conhecida por todos, mas a chave privada seja compartilhada entre todos (requer cooperação de todas as partes para descriptografar um texto cifrado criptografado sob essa chave pública ) A chave pública é transmitida a todos os N participantes.$N$$N$
• $i$$E(b_i)$$E(b_i)$
• $E(R) = E(\Psi(b_1,\dots,b_N))$$E(b_1),\dots,E(b_N)$
• $N$$R$$E(R)$
• Todo mundo prova de alguma forma (talvez por meio de provas do ZK) que eles executaram cada etapa corretamente.

Você precisaria preencher alguns detalhes, mas aposto que você poderia expandir este esboço / estrutura de tópicos para obter um protocolo que resolvesse seu problema de maneira eficiente e segura.

Minha antiga resposta:

$S = \sum_j b_j$

$S<N/2$

$S$$R$$S$$R$$Q$$S \in \{Q,N-Q\}$

$i,j$$E(c_{i,j})$$c_{i,j} = b_i \oplus b_j$$\oplus$$E$$\sum_{i<j} c_{i,j}=R$disso. Há alguns detalhes a serem resolvidos e o modelo de ameaça pode não ser o que você esperava, mas é possível que você consiga fazer algo assim funcionar.