Cálculo seguro de varias partes del número de 1s veces el número de 0s en una cadena compartida

Supongamos que hay partes p j , cada una con un bit b j ∈ { 0 , 1 } . Quiero calcular la multiplicación del número de unidades por ceros, es decir, R = ( ∑ b j ) × ( N - ∑ b j ) .$N>2$$p_j$$b_j\in{\{0,1\}}$$R=(\sum{b_j})\times(N-\sum{b_j})$

El cálculo debe ser segura en el sentido de que ninguna de las partes puede aprender más que el resultado final . Por ejemplo, no está bien realizar una suma segura, porque entonces se conocerá ∑ b j , y la suma es sensible en mi problema. Entonces, ¿hay algún protocolo de cómputo seguro existente que se ajuste a la demanda?$R$$\sum{b_j}$

Editar: El número en el problema es grande, al menos más de 1000 . Por lo tanto, se necesita un cálculo eficiente y seguro de múltiples partes Un protocolo de suma segura podría ser eficiente, pero los SMC genéricos, como los circuitos booleanos, pueden ser demasiado intensivos en computación. Entonces necesito un protocolo eficiente.$N$$1000$

Esta respuesta trata sobre soluciones viables basadas en cifrado homomórfico que NO es totalmente homomórfico, ya que este último puede ser extremadamente ineficiente (si hay criptosistemas completamente homomórficos eficientes que sean comparables con los que se proporcionan a continuación en términos de eficiencia, me alegraría escuchar sobre ellos).

Como solo necesita una multiplicación, existen soluciones que son potencialmente menos costosas que el cifrado totalmente homomórfico: [1] y [2]. El último funciona en descomposiciones de bits cifradas de la entrada, por lo que necesitará un protocolo de descomposición de bits como [3] y [6], pero el primero funciona en valores enteros. Solo para completar, el primero se ha extendido a -operand multiplicación en [4], a pesar de que el OP puede no necesitar esto. Estas soluciones no son interactivas y deberían funcionar en el caso de dos partes.$d$

Si tiene más de dos partes y puede permitirse un poco de interacción, entonces [5] proporciona una "puerta de multiplicación segura" que es potencialmente más eficiente y permite un número ilimitado de multiplicaciones. Funciona básicamente mediante la conversión de los valores cifrados homomórficamente en algún tipo de intercambio secreto, multiplica el resultado (de forma interactiva) y luego lo convierte nuevamente en cifrado homomórfico.

[1] Evaluación de fórmulas de 2-DNF en textos cifrados

[2] Criptocomputación no interactiva para NC1

[3] Computación multipartida de rondas constantes incondicionalmente segura para igualdad, comparación, bits y exponenciación

[4] Encriptación aditivamente homomórfica con multiplicaciones de d-operando

[5] Cálculo multiparte a partir del cifrado homomórfico umbral

[6] Conversión binaria eficiente para valores cifrados más completos

Nueva respuesta (10/24): Creo que el siguiente documento proporciona una solución elegante y eficiente a su problema:

• Evaluación de fórmulas de 2-DNF en textos cifrados , Dan Boneh, Eu-Jin Goh, Kobbi Nissim, TCC 2005.

Muestran cómo construir un algoritmo de cifrado de clave pública con las siguientes dos propiedades útiles:$E(\cdot)$

• Aditivamente homomórfico. Dado y E ( y ) , cualquiera puede calcular E $E(x)$$E(y)$ .$E(x+y)$

• Se puede multiplicar (una vez). Dados y E ( y ) (ninguno de los cuales se generó como resultado de una operación de multiplicación), cualquiera puede calcular E ( x ⋅ y ) . Puede usar el resultado en operaciones de suma, pero no puede usarlo en ninguna operación de multiplicación (el resultado de una multiplicación está contaminado, y los valores contaminados no pueden usarse como la entrada a otra multiplicación).$E(x)$$E(y)$$E(x \cdot y)$

La consecuencia es que, dado un polinomio multivariado cuadrático , y dado E ( x 1 ) , ... , E ( x n ) , cualquiera puede calcular un cifrado de Ψ ( x 1 , ... $\Psi(x_1,\dots,x_n)$$E(x_1),\dots,E(x_n)$ . Esto es súper útil para su situación.$\Psi(x_1,\dots,x_n)$

En particular, en su situación, podemos formar el polinomio Tenga en cuenta que este es un polinomio multivariado cuadrático, por lo tanto, dadas todas las E ( b i ) , cualquiera puede calcular E ( Ψ ( b 1 , ... , b N )

Esto sugiere un protocolo natural para su problema, utilizando una versión umbral del esquema de cifrado en el documento mencionado anteriormente:

• Todos generan conjuntamente un par de claves público / privado para una versión umbral de este esquema, de modo que la clave pública sea conocida por todos, pero la clave privada se comparte entre todos (requiere la cooperación de todos los $N$ partes para descifrar un texto cifrado cifrado bajo esta clave pública ) La clave pública se transmite a todos los $N$ participantes.
• Cada participante calcula E ( b i ) y transmite E ( b i ) a todos los demás participantes. Todos verifican que esto se haya hecho honestamente.$i$$E(b_i)$$E(b_i)$
• Cada participante calcula utilizando las propiedades homomórficas de este esquema de cifrado y el conocimiento de E ( b 1 ) , ... , E ( b N ) . Todos verifican que obtuvieron el mismo valor.$E(R) = E(\Psi(b_1,\dots,b_N))$$E(b_1),\dots,E(b_N)$
• Los participantes utilizan conjuntamente el protocolo de descifrado umbral para recuperar R de E ( R ) . (Tenga en cuenta que solo aplicarán el protocolo de descifrado de umbral a este texto cifrado; los participantes honestos se negarán a participar en descifrar cualquier otro texto cifrado).$N$$R$$E(R)$
• Todos prueban de alguna manera (tal vez a través de pruebas ZK) que realizaron cada paso correctamente.

Tendría que completar algunos detalles, pero apuesto a que podría expandir este bosquejo / esquema para obtener un protocolo que resuelva su problema de manera eficiente y segura.

Mi vieja respuesta:

Todavía buscaría un poco más en un protocolo seguro de múltiples partes para calcular la suma .$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$de esto. Hay algunos detalles para resolver y el modelo de amenaza puede no ser lo que esperaba, pero es posible que pueda hacer que algo como esto funcione.