Transferencia inconsciente

Tipo de protocolo de criptografía

En criptografía , un protocolo de transferencia ajena ( OT ) es un tipo de protocolo en el que un remitente transfiere una de muchas piezas de información potencialmente disponibles a un receptor, pero no sabe qué pieza (si hay alguna) se ha transferido.

La primera forma de transferencia inconsciente fue introducida en 1981 por Michael O. Rabin . ^[1] En esta forma, el remitente envía un mensaje al receptor con probabilidad 1/2, mientras que el remitente permanece inconsciente de si el receptor recibió o no el mensaje. El esquema de transferencia inconsciente de Rabin se basa en el criptosistema RSA . Una forma más útil de transferencia inconsciente llamada transferencia inconsciente 1–2 o "transferencia inconsciente 1 de 2", fue desarrollada más tarde por Shimon Even , Oded Goldreich y Abraham Lempel , ^[2] con el fin de construir protocolos para computación multipartita segura . Se generaliza a "transferencia inconsciente 1 de n ", donde el usuario obtiene exactamente un elemento de la base de datos sin que el servidor sepa qué elemento fue consultado y sin que el usuario sepa nada sobre los otros elementos que no fueron recuperados. La última noción de transferencia inconsciente es un fortalecimiento de la recuperación de información privada , en la que la base de datos no se mantiene privada.

Claude Crépeau demostró que la transferencia inconsciente de Rabin es equivalente a una transferencia inconsciente de 1-2. ^[3]

Estudios posteriores han revelado que la transferencia obvia es un problema fundamental e importante en criptografía. Se considera uno de los problemas críticos en el campo, debido a la importancia de las aplicaciones que se pueden construir en base a ella. En particular, es completa para computación multipartita segura : es decir, dada una implementación de transferencia obvia es posible evaluar de forma segura cualquier función computable en tiempo polinomial sin ninguna primitiva adicional. ^[4]

El protocolo de transferencia inconsciente de Rabin

En el protocolo de transferencia inconsciente de Rabin, el remitente genera un módulo público RSA N = pq donde p y q son números primos grandes y un exponente e relativamente primo a λ(N) = ( p  − 1)( q  − 1). El remitente cifra el mensaje m como m ^e mod N .

1. El remitente envía N , e y m ^e  mod  N al receptor.
2. El receptor elige un x aleatorio  módulo  N y envía x ²  mod  N al emisor. Nótese que mcd( x , N ) = 1 con una probabilidad abrumadora, lo que garantiza que hay 4 raíces cuadradas de x ²  mod  N .
3. El remitente encuentra una raíz cuadrada y de x ²  mod  N y envía y al receptor.

Si el receptor descubre que y no es ni x ni − x módulo N , podrá factorizar N y, por lo tanto, descifrar ^m para recuperar m (consulte el cifrado de Rabin para obtener más detalles). Sin embargo, si y es x o − x  módulo  N , el receptor no tendrá información sobre m más allá del cifrado. Dado que cada residuo cuadrático módulo N tiene cuatro raíces cuadradas, la probabilidad de que el receptor aprenda m es 1/2.

1–2 transferencia inconsciente

En un protocolo de transferencia inconsciente 1–2, Alice, la emisora, tiene dos mensajes m ₀ y m ₁ , y quiere asegurarse de que el receptor solo aprenda uno. Bob, el receptor, tiene un bit b y desea recibir m _b sin que Alice aprenda b . El protocolo de Even, Goldreich y Lempel (que los autores atribuyen parcialmente a Silvio Micali ) es general, pero se puede instanciar utilizando el cifrado RSA de la siguiente manera.

1. Alice tiene dos mensajes y quiere enviarle exactamente uno de ellos a Bob. Bob no quiere que Alice sepa cuál de ellos recibe. ${\displaystyle m_{0},m_{1}}$
2. Alice genera un par de claves RSA, que comprende el módulo , el exponente público y el exponente privado . ${\displaystyle N}$ ${\displaystyle e}$ ${\displaystyle d}$
3. También genera dos valores aleatorios y se los envía a Bob junto con su módulo y exponente públicos. ${\displaystyle x_{0},x_{1}}$
4. Bob elige entre 0 o 1 y selecciona . ${\displaystyle b}$ ${\displaystyle x_{b}}$
5. Bob genera un valor aleatorio y lo utiliza para cegar mediante el cálculo , que luego envía a Alice. ${\displaystyle k}$ ${\displaystyle x_{b}}$ ${\displaystyle v=(x_{b}+k^{e}){\bmod {N}}}$
6. Alice combina ambos valores aleatorios para producir: y . Ahora será igual a y el otro será un valor aleatorio sin sentido. Sin embargo, como Alice no sabe el valor de que eligió Bob, no puede determinar cuál de y es igual a . ${\displaystyle v}$ ${\displaystyle k_{0}=(v-x_{0})^{d}{\bmod {N}}}$ ${\displaystyle k_{1}=(v-x_{1})^{d}{\bmod {N}}}$ ${\displaystyle k_{b}}$ ${\displaystyle k}$ ${\displaystyle b}$ ${\displaystyle k_{0}}$ ${\displaystyle k_{1}}$ ${\displaystyle k}$
7. Ella combina los dos mensajes secretos con cada una de las claves posibles, y , y se los envía a Bob. ${\displaystyle m'_{0}=(m_{0}+k_{0}){\bmod {N}}}$ ${\displaystyle m'_{1}=(m_{1}+k_{1}){\bmod {N}}}$
8. Bob sabe , por lo tanto puede calcular . Sin embargo, como no sabe , no puede calcular y, por lo tanto, no puede determinar . ${\displaystyle k}$ ${\displaystyle m_{b}=(m'_{b}-k){\bmod {N}}}$ ${\displaystyle d}$ ${\displaystyle k_{1-b}=(v-x_{1-b})^{d}{\bmod {N}}}$ ${\displaystyle (m_{1-b}){\bmod {N}}}$

1 de cadanortetransferencia inconsciente ya-fuera de-nortetransferencia inconsciente

Un protocolo de transferencia inconsciente de 1 de n puede definirse como una generalización natural de un protocolo de transferencia inconsciente de 1 de 2. En concreto, un emisor tiene n mensajes y el receptor tiene un índice i , y el receptor desea recibir el i -ésimo de los mensajes del emisor, sin que el emisor conozca i , mientras que el emisor quiere asegurarse de que el receptor reciba solo uno de los n mensajes.

La transferencia no intencional 1 de n no es comparable con la recuperación de información privada (PIR). Por un lado, la transferencia no intencional 1 de n impone un requisito de privacidad adicional para la base de datos: es decir, que el receptor aprenda como máximo una de las entradas de la base de datos. Por otro lado, la PIR requiere una comunicación sublineal en n , mientras que la transferencia no intencional 1 de n no tiene tal requisito. Sin embargo, suponer que la PIR es de un solo servidor es una suposición suficiente para construir la Transferencia no intencional 1 de 2. ^[5]

El protocolo de transferencia inconsciente 1 de n con comunicación sublineal fue construido por primera vez (como una generalización del PIR de servidor único) por Eyal Kushilevitz y Rafail Ostrovsky . ^[6] Moni Naor y Benny Pinkas, ^[7] William Aiello, Yuval Ishai y Omer Reingold , ^[8] Sven Laur y Helger Lipmaa propusieron construcciones más eficientes . ^[9] En 2017, Kolesnikov et al., ^[10] propusieron un protocolo de transferencia inconsciente 1 de n eficiente que requiere aproximadamente 4 veces el costo de la transferencia inconsciente 1-2 en un entorno amortizado.

Brassard , Crépeau y Robert generalizaron aún más esta noción a la transferencia inconsciente k - n , ^[11] en la que el receptor obtiene un conjunto de k mensajes de la colección de n mensajes. El conjunto de k mensajes puede recibirse simultáneamente ("de manera no adaptativa"), o pueden solicitarse consecutivamente, y cada solicitud se basa en los mensajes recibidos previamente. ^[12]

Transferencia inconsciente generalizada

La transferencia ajena k - n es un caso especial de transferencia ajena generalizada, que fue presentado por Ishai y Kushilevitz. ^[13] En ese contexto, el emisor tiene un conjunto U de n mensajes, y las restricciones de transferencia están especificadas por una colección A de subconjuntos permisibles de U . El receptor puede obtener cualquier subconjunto de los mensajes en U que aparezca en la colección A . El emisor debe permanecer ajeno a la selección realizada por el receptor, mientras que el receptor no puede aprender el valor de los mensajes fuera del subconjunto de mensajes que eligió obtener. La colección A es monótona decreciente, en el sentido de que está cerrada bajo contención (es decir, si un subconjunto dado B está en la colección A , también lo están todos los subconjuntos de B ). La solución propuesta por Ishai y Kushilevitz utiliza las invocaciones paralelas de la transferencia ajena 1-2 mientras hace uso de un modelo especial de protocolos privados. Más tarde, se publicaron otras soluciones basadas en el intercambio de secretos: una de Bhavani Shankar, Kannan Srinathan y C. Pandu Rangan [ ^14] y otra de Tamir Tassa ^{[15] .}

Orígenes

A principios de los años setenta, Stephen Wiesner introdujo un primitivo llamado multiplexación en su artículo seminal "Codificación conjugada", que fue el punto de partida de la criptografía cuántica . ^[16] Desafortunadamente, tardó más de diez años en publicarse. Aunque este primitivo era equivalente a lo que más tarde se denominó transferencia ajena 1-2 , Wiesner no vio su aplicación a la criptografía.

Transferencia inconsciente cuántica

Los protocolos de transferencia inconsciente pueden implementarse con sistemas cuánticos . A diferencia de otras tareas en criptografía cuántica , como la distribución de claves cuánticas , se ha demostrado que la transferencia inconsciente cuántica no puede implementarse con seguridad incondicional, es decir, la seguridad de los protocolos de transferencia inconsciente cuántica no puede garantizarse únicamente a partir de las leyes de la física cuántica . ^[17]

Véase también

• k-anonimato
• Computación segura entre múltiples partes
• Prueba de conocimiento cero
• Recuperación de información privada

Referencias

1. Michael O. Rabin . "Cómo intercambiar secretos sin que nadie se dé cuenta". Informe técnico TR-81, Aiken Computation Laboratory, Universidad de Harvard, 1981. Versión manuscrita escaneada y mecanografiada en el archivo eprint.iacr.org. Archivado el 23 de noviembre de 2021 en Wayback Machine . Versión mecanografiada disponible en la página de inicio de Dousti.
2. S. Even, O. Goldreich y A. Lempel, "Un protocolo aleatorio para la firma de contratos", Communications of the ACM , Volumen 28, Número 6, págs. 637–647, 1985.
3. Claude Crépeau . "Equivalencia entre dos tipos de transferencia inconsciente". En Advances in Cryptology – CRYPTO '87, volumen 293 de Lecture Notes in Computer Science, páginas 350–354. Springer, 1988
4. Joe Kilian. "Fundación de la criptografía en la transferencia ajena", Actas del 20.º Simposio anual de la ACM sobre la teoría de la computación (STOC), 1988. Artículo publicado en el portal de la ACM (se requiere suscripción)
5. Giovanni Di Crescenzo, Tal Malkin , Rafail Ostrovsky: La recuperación de información privada de una única base de datos implica una transferencia inconsciente. EUROCRYPT 2000: 122-138
6. Eyal Kushilevitz, Rafail Ostrovsky: La replicación NO es necesaria: una base de datos única, recuperación de información computacionalmente privada. FOCS 1997: 364-373
7. Moni Naor y Benny Pinkas (1990). Evaluación de polinomios inconscientes Archivado el 12 de agosto de 2017 en Wayback Machine 31.° STOC
8. William Aiello, Yuval Ishai y Omer Reingold (2001) Transferencia inconsciente con precio: cómo vender bienes digitales Archivado el 27 de marzo de 2016 en Wayback Machine EUROCRYPT '01 Actas de la Conferencia internacional sobre la teoría y la aplicación de técnicas criptográficas: avances en criptología, páginas 119-135
9. Sven Laur y Helger Lipmaa (2007). "Un nuevo protocolo para la divulgación condicional de secretos y sus aplicaciones". En Jonathan Katz y Moti Yung, editores, ACNS , Lecture Notes in Computer Science 4521 : 207–225. Springer, Heidelberg.
10. Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek y Ni Trieu (2017). "Resolución de problemas obvia y eficiente por lotes con aplicaciones para la intersección de conjuntos privados" Archivado el 11 de julio de 2017 en Wayback Machine . En Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers y Shai Halevi, editores, ACM CCS 16, páginas 818-829. ACM Press, octubre de 2016.
11. Gilles Brassard , Claude Crépeau y Jean-Marc Robert. "Revelación de secretos con un método de todo o nada". En Advances in Cryptology – CRYPTO '86, volumen 263 de LNCS, páginas 234-238. Springer, 1986.
12. Moni Naor y Benny Pinkas. "Transferencia inconsciente con consultas adaptativas". En Advances in Cryptology – CRYPTO '99, volumen 1666 de LNCS, páginas 573–590. Springer, 1999.
13. Yuval Ishai y Eyal Kushilevitz. "Protocolos privados de mensajes simultáneos con aplicaciones". En Proc. of ISTCS'97, IEEE Computer Society, páginas 174-184, 1997.
14. Bhavani Shankar, Kannan Srinathan y C. Pandu Rangan. "Protocolos alternativos para la transferencia generalizada de información ajena a la realidad". En Proc. of ICDCN'08, LNCS 4904, páginas 304–309, 2008.
15. Tamir Tassa. "Transferencia generalizada por ignorancia mediante intercambio de secretos". Designs, Codes and Cryptography, Volumen 58:1, páginas 11-21, enero de 2011. Artículo en openu.ac.il. Archivado el 1 de abril de 2011 en Wayback Machine.
16. Stephen Wiesner, "Codificación conjugada", Sigact News, vol. 15, núm. 1, 1983, págs. 78-88; manuscrito original escrito alrededor de 1970.
17. Lo, H.-K. (1997). "Inseguridad de los cálculos cuánticos seguros". Phys. Rev. A . 56 (2): 1154–1162. arXiv : quant-ph/9611031 . Código Bibliográfico :1997PhRvA..56.1154L. doi :10.1103/PhysRevA.56.1154. S2CID  17813922. Archivado desde el original el 21 de julio de 2019 . Consultado el 21 de julio de 2019 .

Enlaces externos

• Colección de enlaces web de Helger Lipmaa sobre el tema