En criptografía , un protocolo de transferencia inconsciente ( OT ) es un tipo de protocolo en el que un remitente transfiere una de las muchas piezas de información potencialmente a un receptor, pero permanece ajeno a qué pieza (si corresponde) se ha transferido.
La primera forma de transferencia inconsciente fue introducida en 1981 por Michael O. Rabin . 1 De esta forma, el remitente envía un mensaje al receptor con probabilidad 1/2, mientras que el remitente permanece ajeno a 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 crear protocolos para el cálculo seguro de varias partes.. Se generaliza a "1 de n transferencias ajenas" 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 1-2. 3
El trabajo posterior ha revelado que la transferencia inconsciente es un problema fundamental e importante en la criptografía. Se considera uno de los problemas críticos en el campo, por la importancia de las aplicaciones que se pueden construir en base a él. En particular, está completo para el cálculo seguro de varias partes : es decir, dada una implementación de transferencia inconsciente, es posible evaluar de forma segura cualquier función computable de tiempo polinomial sin ninguna primitiva adicional. 4
El protocolo de transferencia inconsciente de Rabin
En el protocolo de transferencia ajeno de Rabin, el remitente genera un público RSA módulo N = pq , donde p y q son grandes números primos , y un exponente e relativamente primos para λ (N) = ( p - 1) ( q - 1). El remitente cifra el mensaje m como m e mod N .
- El remitente envía N , e y m e mod N al receptor.
- El receptor elige un x módulo N aleatorio y envía x 2 mod N al remitente. Nota que mcd ( x , N ) = 1 con abrumadora probabilidad, lo que asegura que hay 4 raíces cuadradas de x 2 mod N .
- El remitente encuentra una raíz cuadrada y de x 2 mod N y envía y al receptor.
Si el receptor encuentra que y no es x ni - x módulo N , el receptor podrá factorizar N y, por lo tanto, descifrar m e para recuperar m (consulte Cifrado Rabin para más detalles). Sin embargo, si y es x o - x mod N , el receptor no tendrá información sobre m más allá del cifrado. Dado que cada módulo de residuo cuadrático N tiene cuatro raíces cuadradas, la probabilidad de que el receptor aprenda m es 1/2.
1-2 transferencias ajenas
En un protocolo de transferencia inconsciente 1-2, Alice el remitente tiene dos mensajes m 0 y m 1 , y Bob el receptor tiene un bit b , y el receptor desea recibir m b , sin que el remitente aprenda b , mientras que el remitente quiere asegúrese de que el receptor reciba solo uno de los dos mensajes. El protocolo de Even, Goldreich y Lempel (que los autores atribuyen parcialmente a Silvio Micali ) es general, pero se puede crear una instancia utilizando el cifrado RSA de la siguiente manera.
Alicia | Beto | |||||
---|---|---|---|---|---|---|
Cálculo | Secreto | Público | Público | Secreto | Cálculo | |
Mensajes a enviar | ||||||
Genere un par de claves RSA y envíe una porción pública a Bob | Recibir clave pública | |||||
Genera dos mensajes aleatorios | Recibe mensajes aleatorios | |||||
Escoger y generar aleatoriamente | ||||||
Calcule el cifrado de , ciego con y enviar a Alice | ||||||
Uno de estos será igual , pero Alice no sabe cuál. | ||||||
Envía ambos mensajes a Bob | Recibe ambos mensajes | |||||
Bob descifra el ya que sabe cual que seleccionó antes. |
- Alice tiene dos mensajes, y desea enviar exactamente uno de ellos a Bob. Bob no quiere que Alice sepa cuál recibe.
- Alice genera un par de claves RSA, que comprende el módulo , el exponente público y el exponente privado
- Ella también genera dos valores aleatorios, y se los envía a Bob junto con su módulo público y exponente.
- Bob elige para ser 0 o 1, y selecciona el primero o el segundo .
- Genera un valor aleatorio y persianas por computación , que le envía a Alice.
- Alice no sabe (y con suerte no puede determinar) cuál de y Bob eligió. Ella aplica sus dos valores aleatorios y obtiene dos valores posibles para: y . Uno de estos será igual a y puede ser descifrado correctamente por Bob (pero no Alice), mientras que el otro producirá un valor aleatorio sin sentido que no revela ninguna información sobre .
- Combina los dos mensajes secretos con cada una de las posibles claves, y y se los envía a Bob.
- Bob sabe cuál de los dos mensajes se puede desenmascarar con , por lo que puede calcular exactamente uno de los mensajes
Transferencia 1-de- n inconsciente y transferencia k -out-of- n inconsciente
Un protocolo de transferencia inconsciente de 1 de n se puede definir como una generalización natural de un protocolo de transferencia inconsciente de 1 de 2. Específicamente, un remitente tiene n mensajes y el receptor tiene un índice i , y el receptor desea recibir el i -ésimo entre los mensajes del remitente, sin que el remitente aprenda i , mientras que el remitente quiere asegurarse de que el receptor reciba solo uno de los mensajes del remitente. los n mensajes.
La transferencia inconsciente 1 de cada n es incomparable a la recuperación de información privada (PIR). Por un lado, la transferencia 1 de cada n inconsciente impone un requisito de privacidad adicional para la base de datos: a saber, que el receptor aprenda como máximo una de las entradas de la base de datos. Por otro lado, PIR requiere comunicación sublineal en n , mientras que 1 de n transferencia inconsciente no tiene tal requisito. Sin embargo, asumir la PIR de un solo servidor es una suposición suficiente para construir una transferencia oblivious 14 de 1 de 2 .
El protocolo de transferencia 1 de n inconsciente con comunicación sublineal fue construido por primera vez (como una generalización de PIR de servidor único) por Eyal Kushilevitz y Rafail Ostrovsky 15 . Construcciones más eficientes fueron propuestos por Moni Naor y Benny Pinkas , 10 William Aiello , Yuval Ishai y Omer Reingold , 11 Sven Laur y Helger Lipmaa . 12 . En 2017, Kolesnikov et al. , 13 propusieron un protocolo de transferencia inconsciente 1-n eficiente que requiere aproximadamente 4 veces el costo de una transferencia inconsciente 1-2 en un entorno amortizado.
Brassard , Crépeau y Robert generalizaron aún más esta noción a k - n transferencia inconsciente, 5 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 ("no adaptativamente"), o pueden solicitarse consecutivamente, con cada solicitud basada en mensajes previos recibidos. 6
Transferencia inconsciente generalizada
k - n La transferencia inconsciente es un caso especial de transferencia inconsciente generalizada, que fue presentada por Ishai y Kushilevitz. 7 En ese entorno, el remitente tiene un conjunto U de n mensajes, y las limitaciones de transferencia se especifican mediante una colección A de subconjuntos permisibles de U . El receptor puede obtener cualquier subconjunto de los mensajes en U que aparece en la colección A . El remitente 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 B dado 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 1-2 transferencias inconscientes mientras hace uso de un modelo especial de protocolos privados. Más tarde, otras soluciones que se basan en el intercambio secreto se publicaron - uno por Bhavani Shankar, Kannan Srinathan y C. Pandu Rangan , 8 y otro por Tamir Tassa. 9
Orígenes
A principios de los setenta, Stephen Wiesner introdujo una primitiva llamada multiplexación en su artículo seminal "Codificación conjugada", que fue el punto de partida de la criptografía cuántica . [1] Desafortunadamente, tardó más de diez años en publicarse. Aunque este primitivo era equivalente a lo que más tarde se denominó transferencia inconsciente 1-2 , Wiesner no vio su aplicación a la criptografía.
Transferencia cuántica inconsciente
Los protocolos para la transferencia inconsciente se pueden implementar con sistemas cuánticos . A diferencia de otras tareas de la criptografía cuántica , como la distribución de claves cuánticas , se ha demostrado que la transferencia cuántica inconsciente no se puede implementar con seguridad incondicional, es decir, la seguridad de los protocolos de transferencia cuántica inconsciente no se puede garantizar solo a partir de las leyes de la física cuántica . [1]
Ver también
- k-anonimato
- Computación multipartita segura
- Prueba de conocimiento cero
- Recuperación de información privada
Referencias
- ^ 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 .
- ^ 0. Stephen Wiesner, "Codificación conjugada", Sigact News, vol. 15, no. 1, 1983, págs. 78-88; manuscrito original escrito alrededor de 1970.
- ^ 1. Michael O. Rabin. "Cómo intercambiar secretos por transferencia ajena". Informe técnico TR-81, Laboratorio de Computación Aiken, Universidad de Harvard, 1981.Escritura a mano escaneada + versión mecanografiada en el archivo eprint.iacr.org. Versiónmecanografiadadisponible enla página de inicio de Dousti.
- ^ 2. S. Even, O. Goldreich y A. Lempel, "Un protocolo aleatorio para la firma de contratos",Comunicaciones de la ACM, Volumen 28, Número 6, pág. 637–647, 1985.Documento en la página de Catuscia Palamidessi
- ^ 3. Claude Crépeau. "Equivalencia entre dos sabores 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. "Criptografía fundacional en transferencias ajenas", Actas, 20º Simposio anual de ACM sobre la teoría de la computación (STOC), 1988.Documento en el portal de ACM (se requiere suscripción)
- ^ 5. Gilles Brassard,Claude CrépeauyJean-Marc Robert. "Revelación de secretos de todo o nada". En Advances in Cryptology: CRYPTO '86, volumen 263 de LNCS, páginas 234–238. Springer, 1986.
- ^ 6. Moni NaoryBenny Pinkas. "Transferencia ajena con consultas adaptables". En Advances in Cryptology: CRYPTO '99, volumen 1666 de LNCS, páginas 573–590. Springer, 1999.
- ^ 7. 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.
- ^ 8. Bhavani Shankar, Kannan Srinathan y C. Pandu Rangan. "Protocolos alternativos para la transferencia inconsciente generalizada". En Proc. de ICDCN'08, LNCS 4904, páginas 304–309, 2008.
- ^ 9. Tamir Tassa. "Transferencia inconsciente generalizada por intercambio secreto". Diseños, códigos y criptografía, volumen 58: 1, páginas 11–21, enero de 2011.Documento en openu.ac.il
- ^ 10. Moni NaoryBenny Pinkas(1990). Evaluación polinomialajena 31st STOC
- ^ 11. William Aiello,Yuval IshaiyOmer Reingold(2001)Priced Oblivious Transfer: How to Sell Digital GoodsEUROCRYPT '01 Actas de la Conferencia Internacional sobre Teoría y Aplicación de Técnicas Criptográficas: Avances en Criptología, páginas 119-135
- ^ 12. 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.
- ^ 13. Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek y Ni Trieu (2017). "Prf inconsciente por lotes eficiente con aplicaciones a la intersección de conjuntos privados". 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.
- ^ 14. Giovanni Di Crescenzo, Tal Malkin, Rafail Ostrovsky: La recuperación de información privada de una sola base de datos implica una transferencia ajena. EUROCRYPT 2000: 122-138
- ^ 15. Eyal Kushilevitz, Rafail Ostrovsky: NO se necesita replicación: base de datos ÚNICA, recuperación de información privada computacional. FOCS 1997: 364-373
enlaces externos
- Colección de enlaces web de Helger Lipmaa sobre el tema