Secret Sharing visual y esquemas aditivos

La compartición visual de secretos (Naor y Shamir, 1994) divide una imagen en n transparencias, de modo que al superponer k transparencias se revela la imagen secreta, mientras que cualquier número menor no revela nada, ni siquiera a un adversario con capacidad computacional ilimitada.

Cada píxel del secreto se amplía a un bloque de 2x2. Para un píxel negro: ambas partes reciben patrones complementarios que, al superponerse, son completamente negros. Para un píxel blanco: ambas partes reciben el mismo patrón que, al superponerse, tiene un 50 % de negro y se percibe como gris. El ojo percibe la diferencia.

Para cadenas de bits: comparta el secreto S generando R_1, R_2, ..., R_{n-1} aleatorios. Establezca R_n = S XOR R_1 XOR ... XOR R_{n-1}. Al aplicar XOR a las n partes se obtiene S. Cualquier subconjunto de n-1 partes es uniformemente aleatorio y no revela nada sobre S.

La compartición mediante XOR o aditiva es n-de-n: se necesitan todas las partes. El SSS de Shamir es k-de-n: basta con cualquier k partes. La compartición aditiva es más sencilla y rápida; Shamir admite umbrales arbitrarios. Los protocolos MPC suelen utilizar compartición aditiva para las operaciones aritméticas.

Para secretos enteros: comparta S como S = s_1 + s_2 + ... + s_n (mod p). Cada s_i es un elemento aleatorio de Z_p. Para sumar dos valores compartidos A+B, cada participante suma localmente sus partes: (a_i + b_i) mod p. No se necesita comunicación para realizar la suma.

Multiplicar valores compartidos mediante secretos requiere interacción. El método clásico de la terna de Beaver consiste en precalcular una terna aleatoria compartida (a, b, c=ab). Para multiplicar x*y, se revelan (x-a) y (y-b) a todos los participantes; estos valores no revelan nada sobre x ni sobre y. Después, se calcula x*y utilizando la terna.

Un esquema lineal de compartición de secretos (LSSS) implementa cualquier estructura de acceso monótona. Shamir es un LSSS. Los LSSS son el componente básico del cifrado basado en atributos (ABE) y de los sistemas de control de acceso con múltiples autoridades.

La compartición compactada de Shamir incluye varios secretos en un solo polinomio: codifica k secretos como coeficientes de un polinomio de grado (n-k). Esto permite amortizar el coste de comunicación en protocolos MPC cuando es necesario compartir muchos valores simultáneamente.

Los esquemas básicos de compartición no ofrecen protección contra participantes maliciosos que envíen partes no válidas. Verifiable Secret Sharing (VSS) añade compromisos; Robust Secret Sharing añade corrección de errores, de modo que la reconstrucción se complete incluso con t partes incorrectas.

Criptografía visual: autenticación de documentos impresos y papeletas de votación seguras. Compartición aditiva: SPDZ MPC y agregación segura en aprendizaje federado (Google). Esquemas de umbral: copias de seguridad de semillas de billeteras de hardware y gestión empresarial de claves.

Un esquema con rampa (k,n) es más débil: menos de k-d partes revelan información parcial (d niveles de confidencialidad). Se utiliza cuando no se requiere secreto perfecto para las partes parciales, pero la eficiencia de almacenamiento es fundamental. Permite usar partes más cortas que Shamir.

La criptografía visual divide las imágenes en transparencias; la compartición aditiva utiliza XOR para esquemas n-de-n; Shamir admite esquemas k-de-n. MPC utiliza compartición aditiva con ternas de Beaver para la multiplicación. A continuación: firmas de umbral y uso en el mundo real.