¿Cómo puedo permitir el acceso a datos encriptados si solo 2 de cada 3 usuarios proporcionan un secreto?

Se llama encriptación de umbral (o, aquí, descifrado).

Un esquema bien conocido es El intercambio secreto de Shamir . Permite dividir un valor secreto en acciones n , de modo que cualquier acción t es suficiente para reconstruir el secreto. n y t se pueden elegir a voluntad (aunque usted querrá tener n mayor que t en la práctica) . Para el problema de encriptación de umbral, aplica el esquema de Shamir en la clave de descifrado. Cuando t los titulares de acciones se encuentran, pueden reconstruir la clave de descifrado y luego descifrar los datos.

Aunque el esquema de Shamir está bien (de hecho, es probable que sea seguro incluso contra atacantes con infinitas capacidades computacionales; muy pocos algoritmos criptográficos pueden afirmar que son igualmente seguros), tiene una limitación que es la siguiente: reconstruye un < em> secreto . Esto lo convierte de alguna manera en "un disparo": si los titulares de acciones reconstruyen el secreto, entonces tienen el secreto. Cada uno de ellos podrá realizar más descifrados solo simplemente recordando el secreto reconstruido.

Dependiendo de su contexto, esto puede o no ser un problema. Por ejemplo, hay sistemas de votación que utilizan el cifrado homomórfico (por ejemplo, con ElGamal), donde los votos cifrados se suman sin descifrarlos (ese es el punto del homomorfismo); pero el recuento final aún debe ser descifrado. Aquí queremos el descifrado de umbral: varias autoridades deben colaborar entre sí para realizar el descifrado. De esa manera, las autoridades se mantienen en jaque. Sin embargo, si aprenden la propia clave privada en el proceso, luego cada autoridad podrá descifrar los votos individuales, lo que anula todo el propósito.

Si estos problemas se aplican a su contexto, entonces debe hacer más matemáticas. Hay esquemas de descifrado de umbral que permiten, por ejemplo, un descifrado de ElGamal de umbral, de manera que el titular de la acción t debe comunicarse entre sí para cada instancia de descifrado, intercambiando "mensajes parcialmente descifrados. ". La clave privada nunca se reconstruye realmente, pero su acción (el descifrado) se reproduce gradualmente.

Existe una gran cantidad de teorías sobre los sistemas criptográficos de umbral, con varias características (cuántas acciones, a qué valores de umbral posibles, el esquema resiste bien cuando algún titular de acciones hace trampa activamente, cuántos mensajes se deben intercambiar, etc.) Si su problema actual puede resolverse con el esquema de Shamir, entonces, por supuesto, hágalo. Es razonablemente fácil de implementar (en particular, compartir archivos es fácil si realiza todos los cálculos en GF (2 ⁸ ) ).

Lo que estás buscando es Shamir Secret Sharing . El objetivo es que, dado un grupo de usuarios de k , cualquier n de ellos trabajando juntos puede descifrar los datos. Por otro lado, un grupo de menos de n usuarios no debería poder obtener información sobre la clave de descifrado.

La idea general de cómo funciona esto utiliza cierta geometría. Supongamos que queremos que dos usuarios puedan descifrar. Imagina el plano 2D estándar con un eje horizontal y vertical. Para configurar el sistema, elige un punto aleatorio en el eje vertical entre 0 y, por ejemplo, 2 ^ 128; esto corresponde a una clave de 128 bits.

A continuación, elige una línea aleatoria en el plano que intersecta ese punto. Usted le dice a cada uno de sus usuarios las coordenadas de un punto en esa línea (cada usuario aprende un punto diferente). Cualquiera de los dos usuarios pueden combinar sus puntos para averiguar qué línea eligió, literalmente, conectando los puntos, y de ahí averiguar cuál es la clave.

Si desea que más de dos usuarios necesiten trabajar juntos, elige un polinomio de orden superior (como una parábola, para tres usuarios) en lugar de una línea.

Hay un punto técnico al que me estoy refiriendo, a saber, que en lugar de usar la multiplicación y la suma estándar, define estas operaciones de una manera especial. (Hablando matemáticamente, trabajas en un campo finito). De manera informal, la razón de esto es que puede asignar puntos de usuarios desde un rango bien definido (con coordenadas x e y entre 0 y 2 ^ 128 - 1, por ejemplo) mientras evita que eliminen posibles valores clave (a menos que trabajen junto con el número especificado de personas).

Estoy seguro de que hay un nombre formal para esto, pero se me escapa. Una solución sería generar una clave de 256 bits con 64 caracteres hexadecimales.

Da los caracteres clave de Alicia 1-22 y 22-43. Dale a Bob los personajes clave 22-43 y 43-64. Dale a Carol los caracteres clave 1-22 y 43-64.

De esta manera, cualquiera de los dos puede realizar el descifrado, pero nadie tiene la clave completa.

El problema aquí es que solo hay alrededor de 22 caracteres / 85 bits de datos faltantes de Alice, Bob o Carol para fuerza bruta. Tal vez si cifras con algo como enlace que tiene una clave de hasta 448 bits, eso resolvería ese problema.