En criptografía , un protocolo de recuperación de información privada (PIR) es un protocolo que permite a un usuario recuperar un elemento de un servidor en posesión de una base de datos sin revelar qué elemento se recupera. PIR es una versión más débil de la transferencia inconsciente 1 de cada n , donde también se requiere que el usuario no obtenga información sobre otros elementos de la base de datos.
Una forma trivial, pero muy ineficiente de lograr PIR es que el servidor envíe una copia completa de la base de datos al usuario. De hecho, este es el único protocolo posible (en la configuración clásica o cuántica [1] ) que le da a la información del usuario privacidad teórica para su consulta en una configuración de servidor único. [2] Hay dos formas de abordar este problema: hacer que el servidor esté limitado computacionalmente o asumir que hay varios servidores que no cooperan, cada uno con una copia de la base de datos.
El problema fue introducido en 1995 por Chor, Goldreich, Kushilevitz y Sudan [2] en el entorno de la teoría de la información y en 1997 por Kushilevitz y Ostrovsky en el entorno computacional. [3] Desde entonces, se han descubierto soluciones muy eficientes. Se puede lograr PIR de base de datos única (computacionalmente privada) con comunicación constante (amortizada) y PIR de base de datos k (teoría de la información) se puede hacer con comunicación.
Avances en PIR computacional
El primer esquema PIR computacional de base de datos única para lograr una complejidad de comunicación menor que fue creado en 1997 por Kushilevitz y Ostrovsky [3] y logró una complejidad de comunicación de para cualquier , dónde es el número de bits en la base de datos. La seguridad de su esquema se basaba en el bien estudiado problema de la residuosidad cuadrática . En 1999, Christian Cachin, Silvio Micali y Markus Stadler [4] lograron una complejidad de comunicación polilogarítmica. La seguridad de su sistema se basa en el supuesto de ocultación de Phi . En 2004, Helger Lipmaa [5] logró una complejidad de comunicación logarítmica al cuadrado, dónde es la longitud de las cuerdas y es el parámetro de seguridad. La seguridad de su sistema se reduce a la seguridad semántica de un criptosistema aditivamente homomórfico de longitud flexible como el criptosistema Damgård-Jurik . En 2005, Craig Gentry y Zulfikar Ramzan [6] lograron una complejidad de comunicación log-cuadrado que recupera bits log-cuadrados (consecutivos) de la base de datos. La seguridad de su esquema también se basa en una variante del supuesto de ocultación de Phi. La tasa de comunicación finalmente se redujo apor Aggelos Kiayias , Nikos Leonardos , Helger Lipmaa , Kateryna Pavlyk , Qiang Tang , en 2015. [7]
Todo el protocolo PIR computacional de comunicación sublineal anterior requería una complejidad computacional lineal de operaciones de clave pública. En 2009, Helger Lipmaa [8] diseñó un protocolo PIR computacional con complejidad de comunicación y el peor de los casos de cálculo de operaciones de clave pública. Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky y Amit Sahai han considerado técnicas de amortización que recuperan bits no consecutivos . [9]
Como lo muestran Ostrovsky y Skeith, [10] los esquemas de Kushilevitz y Ostrovsky [3] y Lipmaa [5] utilizan ideas similares basadas en el cifrado homomórfico . El protocolo de Kushilevitz y Ostrovsky se basa en el criptosistema Goldwasser-Micali, mientras que el protocolo de Lipmaa se basa en el criptosistema Damgård-Jurik .
Avances en la teoría de la información PIR
Lograr la seguridad de la teoría de la información requiere suponer que hay varios servidores que no cooperan, cada uno con una copia de la base de datos. Sin esta suposición, cualquier protocolo PIR teóricamente seguro de la información requiere una cantidad de comunicación que es al menos del tamaño de la base de datos n . Los protocolos PIR multiservidor que toleran los servidores no receptivos o maliciosos / coludidos se denominan robustos o bizantinos robustos, respectivamente. Estos temas fueron considerados por primera vez por Beimel y Stahl (2002). Un sistema ℓ-servidor que puede operar donde solo k de los servidores responden, ν de los servidores responden incorrectamente, y que puede soportar hasta t servidores en colusión sin revelar la consulta del cliente se llama " t -private ν-Byzantine robusto k -out -de-ℓ PIR "[DGH 2012]. En 2012, C. Devet, I. Goldberg y N. Heninger (DGH 2012) propusieron un esquema óptimamente robusto que es bizantino-robusto paraque es el valor máximo teórico. Se basa en un protocolo anterior de Goldberg que utiliza el uso compartido secreto de Shamir para ocultar la consulta. Goldberg ha lanzado una implementación de C ++ en Sourceforge . [11]
Relación con otras primitivas criptográficas
Las funciones unidireccionales son necesarias, pero no se sabe que sean suficientes, para la recuperación de información privada computacionalmente no trivial (es decir, con comunicación sublineal) de una sola base de datos. De hecho, Giovanni Di Crescenzo , Tal Malkin y Rafail Ostrovsky demostraron que tal protocolo implicaba una transferencia inconsciente (ver más abajo). [12]
La transferencia ajena , también llamada PIR simétrica, es PIR con la restricción adicional de que el usuario no puede aprender ningún elemento que no sea el solicitado. Se denomina simétrico porque tanto el usuario como la base de datos tienen un requisito de privacidad.
Las funciones de hash criptográficas resistentes a colisiones están implícitas en cualquier esquema PIR computacional de una ronda, como lo muestran Ishai, Kushilevitz y Ostrovsky. [13]
Variaciones PIR
La motivación básica para la recuperación de información privada es una familia de protocolos de dos partes en la que una de las partes (el remitente ) posee una base de datos y la otra parte (el receptor ) quiere consultarla con ciertas restricciones y garantías de privacidad. Entonces, como resultado del protocolo, si el receptor quiere el valor i-ésimo en la base de datos, debe aprender la entrada i-ésima , pero el remitente no debe aprender nada sobre i . En un protocolo PIR general, un remitente computacionalmente ilimitado no puede aprender nada sobre i, por lo que teóricamente se preserva la privacidad. Desde que se planteó el problema de la PIR, se han perseguido diferentes enfoques para su solución y se han propuesto algunas variaciones.
Un protocolo CPIR (recuperación de información privada computacionalmente) es similar a un protocolo PIR: el receptor recupera un elemento elegido por él de la base de datos del remitente, de modo que el remitente no obtiene conocimiento sobre qué elemento fue transferido. [8] La única diferencia es que la privacidad está protegida contra un remitente delimitado por polinomios. [14]
Se utiliza un protocolo CSPIR (recuperación de información privada simétrica computacionalmente) en un escenario similar en el que se utiliza un protocolo CPIR. Si el remitente posee una base de datos y el receptor desea obtener el i-ésimo valor en esta base de datos, al final de la ejecución de un protocolo SPIR, el receptor no debería haber aprendido nada sobre los valores en la base de datos que no sea el i-ésimo uno. [14]
Implementaciones PIR
Se han implementado numerosos esquemas PIR computacional y PIR teórico de la información en la literatura. Aquí hay una lista incompleta:
- Percy ++ [11] incluye implementaciones de [AG 2007, DGH 2012, CGKS 1998, Goldberg 2007, HOG 2011, LG 2015].
- Popcorn [15] es una implementación de PIR adaptada a los medios [GCMSAW 2016].
- RAID-PIR [16] es una implementación del esquema ITPIR de [DHS 2014].
- SealPIR [17] es una implementación rápida de CPIR [ACLS 2018].
- upPIR [18] es una implementación de ITPIR [Cappos 2013].
- XPIR [19] es una implementación rápida de CPIR [ABFK 2014].
Notas
- ^ Baumeler, Ämin; Broadbent, Anne (17 de abril de 2014). "La recuperación de información privada cuántica tiene una complejidad de comunicación lineal". Revista de criptología . 28 : 161-175. arXiv : 1304.5490 . doi : 10.1007 / s00145-014-9180-2 .
- ^ a b Chor, Benny; Kushilevitz, Eyal; Goldreich, Oded; Sudán, Madhu (1 de noviembre de 1998). "Recuperación de información privada" (PDF) . Revista de la ACM . 45 (6): 965–981. CiteSeerX 10.1.1.51.3663 . doi : 10.1145 / 293347.293350 .
- ^ a b c Kushilevitz, Eyal; Ostrovsky, Rafail (1997). "No se necesita replicación: base de datos única, recuperación de información privada computacionalmente". Actas del 38º Simposio Anual sobre Fundamentos de la Ciencia de la Computación . Miami Beach, Florida, EE.UU .: IEEE Computer Society. págs. 364–373. CiteSeerX 10.1.1.56.2667 . doi : 10.1109 / SFCS.1997.646125 . ISBN 978-0-8186-8197-4.
- ^ Cachin, Christian; Micali, Silvio; Stadler, Markus (1999). "Recuperación de información privada computacionalmente con comunicación polilogarítmica". Avances en Criptología - EUROCRYPT '99 . Praga, República Checa: Springer-Verlag. págs. 402–414. doi : 10.1007 / 3-540-48910-X_28 . ISBN 978-3-540-48910-8.
- ^ a b Lipmaa, Helger (2005). "Un protocolo de transferencia ajeno con comunicación Log-Squared". Actas de la 8ª Conferencia Internacional sobre Seguridad de la Información (ISC 2005) . Apuntes de conferencias en Ciencias de la Computación. 3650 . Singapur: Springer-Verlag. págs. 314–328. CiteSeerX 10.1.1.73.8768 . doi : 10.1007 / 11556992_23 . ISBN 978-3-540-31930-6.
- ^ Gentry, Craig; Ramzan, Zulfikar (2005). "Recuperación de información privada de base de datos única con tasa de comunicación constante". ICALP . LNCS. 3580 . Saltador. págs. 803–815. CiteSeerX 10.1.1.113.6572 . doi : 10.1007 / 11523468_65 .
- ^ Kiayias, Aggelos; Leonardos, Nikos; Lipmaa, Helger; Pavlyk, Kateryna; Tang, Qiang (2015). "Recuperación de información privada de tasa óptima de cifrado homomórfico". Actas sobre tecnologías de mejora de la privacidad 2015 . 2015 . DE GRUYTER. págs. 222–243. doi : 10.1515 / popets-2015-0016 .
- ^ a b Lipmaa, Helger (2010). "Primer protocolo CPIR con cálculo dependiente de datos". Actas de la XII Conferencia Internacional sobre Seguridad de la Información y Criptología . Apuntes de conferencias en Ciencias de la Computación. 5984 . Seúl, Corea: Springer-Verlag. págs. 193–210. CiteSeerX 10.1.1.215.7768 . doi : 10.1007 / 978-3-642-14423-3_14 . ISBN 978-3-642-14423-3.
- ^ Ishai, Yuval; Kushilevitz, Eyal; Ostrovsky, Rafail; Sahai, Amit (2004). "Códigos de lote y sus aplicaciones" (PDF) . STOC'04 . ACM. págs. 262-271. doi : 10.1145 / 1007352.1007396 . Consultado el 23 de octubre de 2015 .
- ^ Ostrovsky, Rafail; Skeith III; William E. (2007). "Una encuesta de recuperación de información privada de base de datos única: técnicas y aplicaciones". Actas de la Décima Conferencia Internacional sobre Práctica y Teoría en Criptografía de Clave Pública . Springer-Verlag. págs. 393–411. doi : 10.1007 / 978-3-540-71677-8_26 . ISBN 978-3-540-71677-8.
- ^ a b Percy ++ / PIR en C ++ en SourceForge
- ^ Di Crescenzo, Giovanni; Malkin, Tal; Ostrovsky, Rafail (2000). "Recuperación de información privada de base de datos única implica transferencia ajena". Eurocrypt 2000 . LNCS. 1807 . Saltador. págs. 122-138. doi : 10.1007 / 3-540-45539-6_10 .
- ^ Ishai, Yuval; Kushilevitz, Eyal; Ostrovsky, Rafail (2005). "Condiciones suficientes para un hash resistente a colisiones". Actas de la Segunda Conferencia de Teoría de la Criptografía . Cambridge, MA, Estados Unidos: Springer-Verlag. págs. 445–456. doi : 10.1007 / 978-3-540-30576-7_24 . ISBN 978-3-540-30576-7.
- ^ a b San Juan, Felipe (2005). "Una implementación de Java de un protocolo de recuperación de información privada simétrica computacionalmente (cSPIR) de una sola base de datos" (PDF) . Informe técnico de la Universidad de Yale YALEU / DCS / TR-1333 .
- ^ "Palomitas de maíz" (PDF) . Archivado desde el original (PDF) el 21 de agosto de 2016 . Consultado el 26 de mayo de 2016 .
- ^ "grupo de cifrado / RAID-PIR" . GitHub . Consultado el 26 de mayo de 2016 .
- ^ "SealPIR" . Github . Consultado el 7 de junio de 2018 .
- ^ "upPIR" . uppir.poly.edu . Archivado desde el original el 25 de junio de 2016 . Consultado el 26 de mayo de 2016 .
- ^ "Equipo XPIR / XPIR" . GitHub . Consultado el 26 de mayo de 2016 .
Ver también
- k-anonimato
- Código decodificable localmente
Referencias
- A. Beimel, Y. Ishai, E. Kushilevitz y J.-F. Raymond. Rompiendo elbarrera para la recuperación de información privada basada en la información. Actas del 43 ° Simposio anual del IEEE sobre fundamentos de la informática , Vancouver, Canadá, páginas 261-270, 2002.
- A. Beimel e Y. Stahl, Recuperación robusta de información privada basada en la teoría de la información , en Actas de la 3ª Conferencia Internacional sobre Seguridad en las Redes de Comunicación (SCN'02), págs. 326–341, 2003. La cita es de DGH 2012, op. cit.
- [DGH 2012] Casey Devet, Ian Goldberg y Nadia Heninger , Recuperación de información privada óptimamente robusta , 21º Simposio de seguridad de USENIX, agosto de 2012.
- [AG 2007] C. Aguilar-Melchor y P. Gaborit. Un protocolo de recuperación de información privada computacionalmente eficiente basado en celosía , Western European Workshop on Research in Cryptology (WEWoRC), 2007.
- [CGKS 1998] B. Chor, O. Goldreich, E. Kushilevitz y M. Sudan, Recuperación de información privada , Journal of the ACM, 45 (6): 965–981, 1998.
- [Goldberg 2007] I. Goldberg, Mejora de la solidez de la recuperación de información privada , Simposio IEEE sobre Seguridad y Privacidad (S&P), 2007.
- [HOG 2011] R. Henry, F. Olumofin e I. Goldberg, PIR práctico para el comercio electrónico , Conferencia ACM sobre seguridad informática y de comunicaciones (CCS), 2011.
- [LG 2015] W. Lueks e I. Goldberg, Escalado sublineal para la recuperación de información privada de múltiples clientes , Conferencia Internacional sobre Criptografía Financiera y Seguridad de Datos (FC), 2015.
- [DHS 2014] D. Demmler, A. Herzberg y T. Schneider, RAID-PIR: Practical multi-server PIR , In Cloud computing security workshop (CCSW), 2014.
- [ABFK 2014] C. Aguilar-Melchor, J. Barrier, L. Fousse y M.-O. Killijian, "XPIR: Recuperación de información privada para todos", Cryptology ePrint Archive, Informe 2014/1025, 2014.
- [GCMSAW 2016] T. Gupta, N. Crooks, W. Mulhern, S. Setty, L. Alvisi y M. Walfish, [1] Consumo de medios escalables y privados con palomitas de maíz. USENIX NSDI, marzo de 2016.
- [Cappos 2013] J. Cappos, Evitar la optimización teórica para recuperar actualizaciones de seguridad de manera eficiente y privada , Conferencia internacional sobre criptografía financiera y seguridad de datos (FC), 2013.
- Sergey Yekhanin. Nuevos códigos decodificables localmente y esquemas de recuperación de información privada, ECCC TR06-127 , 2006.
- [ACLS 2018] S. Angel, H. Chen, K. Laine, S. Setty, PIR con consultas comprimidas y procesamiento de consultas amortizadas , IEEE Symposium on Security and Privacy (S&P), 2018.
enlaces externos
- Enlaces web de Helger Lipmaa sobre transferencias ajenas y PIR
- Sitio web de William Gasarch sobre PIR, incluidos artículos de encuestas
- El sitio web de Rafail Ostrovsky contiene artículos y encuestas de PIR