Resumen Técnico: Límites Inferiores para PIR con Preprocesamiento a partir de Criptografía de Caja Negra

1. Planteamiento del Problema

El artículo investiga los límites fundamentales de la Recuperación de Información Privada (PIR) de Servidor Único en el modelo de preprocesamiento. En este entorno, un cliente realiza una fase fuera de línea (offline) para almacenar una pequeña cantidad de estado ($s$ bits) sobre una base de datos de $n$ bits, permitiendo consultas más eficientes en la fase en línea (online). Si bien avances recientes han demostrado esquemas de PIR de servidor único con computación y comunicación de consulta sublineales mediante el aprovechamiento del preprocesamiento (por ejemplo, [CHK22, ZPZS24, LMW23]), los límites teóricos de estas construcciones siguen sin estar claros.

Específicamente, los autores abordan si es posible construir esquemas de PIR de servidor único que:

1. Logren una computación en línea amortizada sublineal (específicamente $o(n/s)$).
2. Dependan de criptografía de caja negra (modelada mediante oráculos criptográficos, incluyendo oráculos aleatorios, ofuscación de caja negra virtual y grupos multilineales genéricos).
3. Soporten PIR Simétrico (SPIR) (donde el cliente solo aprende la entrada consultada) utilizando únicamente funciones de un solo sentido (OWF) durante la fase en línea.

Los límites inferiores previos para PIR con preprocesamiento se limitaban a clases restringidas de esquemas (por ejemplo, que requerían servidores sin codificación, consultas ajenas a la base de datos o interacciones de un solo viaje de ida y vuelta) o dependían de supuestos de complejidad no probados. Este trabajo tiene como objetivo proporcionar límites inferiores incondicionales para una clase más amplia de esquemas que realizan un uso de caja negra de la criptografía.

2. Metodología

El núcleo de la metodología del artículo es la introducción de un nuevo primitivo llamado Dual PIR y una reducción de la PIR estándar con preprocesamiento a este primitivo.

2.1 Dual Private Information Retrieval (Dual PIR)

Los autores definen Dual PIR como una inversión del modelo de preprocesamiento de PIR estándar:

• Fase de Consejo (Advice Phase): Antes de que se conozcan las consultas, el cliente genera una cadena de consejo (transcript) de $t$ bits basada en la base de datos.
• Fase de Pista (Hint Phase): Dada la base de datos, un lote de $k$ índices de consulta y el consejo, el cliente genera una pista de $s$ bits.
• Reconstrucción: Utilizando únicamente los índices de consulta, el consejo y la pista (pero sin acceso a la base de datos), el cliente debe reconstruir las entradas de la base de datos consultadas.

Esta formulación transforma el problema de eficiencia de PIR en un problema de compresión. Si un esquema de PIR es demasiado eficiente (es decir, $t = o(n)$ y $s < k$), implica la existencia de un Dual PIR que comprime $k$ bits de información en $s$ bits utilizando solo $t$ bits de consejo compartido, lo cual es información-teóricamente imposible bajo ciertas condiciones.

2.2 Reducción de PIR a Dual PIR

Los autores construyen una reducción que muestra que cualquier esquema de PIR seguro con preprocesamiento puede transformarse en un esquema de Dual PIR.

• Consejo: Simula la ejecución de la PIR para una consulta fija para generar un registro de comunicación y un conjunto de consultas al oráculo criptográfico del servidor.
• Pista: Re-aleatoriza el estado del cliente para que coincida con el registro fijo para una consulta diferente. Crucialmente, para manejar la naturaleza de caja negra de la criptografía, el algoritmo de la Pista muestrea nuevos oráculos criptográficos que son consistentes con las consultas previas del servidor (usando un oráculo aleatorio compartido para asegurar la consistencia).
• Reconstrucción: Simula el lado del cliente de la consulta de la PIR utilizando el estado muestreado y el registro fijo.

2.3 Conexión con la Predicción de Subclaves

Para probar la imposibilidad de un Dual PIR eficiente, los autores conectan el problema con la predicción de subclaves en criptografía resistente a fugas ([BKR16]). Demuestran que un Dual PIR correcto y eficiente permitiría a un adversario predecir $k$ bits aleatorios de una clave de $n$ bits dada una fuga de $t$ bits, con una probabilidad de éxito que excede los límites de información-teóricos conocidos. Específicamente, si $t < n/2$ y $k = \Omega(s)$, la probabilidad de reconstrucción correcta está acotada por $2^{s - \Omega(k)}$.

3. Contribuciones Clave y Resultados

3.1 Límites Inferiores de Computación

El artículo establece que para cualquier PIR de servidor único con preprocesamiento de cliente que realice uso de caja negra de la criptografía:

• Teorema 1.1: Es imposible lograr tanto una comunicación en línea amortizada de $o(n/s)$ como una operación criptográfica del servidor amortizada de $o(n/s)$.
• Implicación: Cualquier esquema de este tipo debe satisfacer al menos una de las siguientes condiciones:
  1. La comunicación en línea amortizada es $\Omega(n/s)$ bits.
  2. El servidor realiza $\Omega(n/s)$ operaciones de bits criptográficos.
• Rigidez (Tightness): Este límite es óptimo. Los esquemas existentes (por ejemplo, [WR25]) logran $O(n/s)$ de comunicación sin operaciones criptográficas del servidor, mientras que otros (por ejemplo, [ZPZS24]) logran $O(n/s)$ de comunicación sin operaciones criptográficas del servidor pero requieren refrescar el estado del cliente. El límite inferior confirma que no se pueden eludir ambos cuellos de botella simultáneamente.

3.2 Doblemente Eficiente PIR (DEPIR)

Los autores descartan la existencia de PIR Doblemente Eficiente (donde tanto el cliente como el servidor tienen tiempo sublineal) construido a partir de criptografía de caja negra.

• Teorema 1.2: No existe un DEPIR de servidor único con computación de consulta sublineal ($t = o(n)$) para una sola consulta, incluso si el servidor realiza una codificación arbitraria.
• Este resultado se aplica a la DEPIR de clave pública y mejora los resultados de imposibilidad previos que estaban restringidos a consultas de un solo viaje de ida y vuelta con servidores pasivos.

3.3 Límites Inferiores de Comunicación

El artículo deriva límites inferiores de comunicación específicos para clases restringidas de PIR:

• Teorema 1.4: Si un esquema de PIR satisface cualquiera de las siguientes condiciones, requiere $\Omega(n/s)$ de comunicación amortizada:
  1. El servidor realiza $o(n/s)$ operaciones criptográficas.
  2. Las operaciones criptográficas del servidor dependen únicamente del registro de comunicación (uso de criptografía ajena a la base de datos).
  3. El esquema ofrece privacidad perfecta en un modelo idealizado.

3.4 PIR Simétrico (SPIR)

El artículo aborda la construcción de PIR Simétrico (SPIR) con preprocesamiento de cliente, donde el cliente solo aprende la entrada consultada.

• Construcción (Teorema 1.5): Los autores presentan una construcción de SPIR con preprocesamiento de cliente que depende únicamente de Funciones de un Solo Sentido (OWF) durante la fase de consulta en línea. El esquema logra $\tilde{O}(n/s)$ en comunicación y computación, soportando $\tilde{O}(s)$ consultas por fase fuera de línea.
• Limitación (Teorema 1.6): En el modelo de oráculo aleatorio, ningún esquema de este tipo de SPIR puede soportar más de $k > s$ consultas por fase fuera de línea. Esto contrasta con la PIR no simétrica, que puede soportar consultas ilimitadas mediante el refresco del estado. Los autores demuestran que soportar $k > s$ consultas requiere criptografía de clave pública o comunicación lineal.

3.5 PIR Débil

Los límites inferiores se extienden a esquemas de "PIR débil" que proporcionan privacidad solo contra adversarios que realizan un número polinomial de consultas al oráculo criptográfico (similar a los acertijos de Merkle).

• Teorema 1.3 & 1.5: Incluso para adversarios débiles, el tiempo de consulta en línea sublineal es imposible para la PIR de servidor único con preprocesamiento si las partes honestas y el adversario realizan un número comparable de consultas al oráculo.

4. Significado y Reivindicaciones

El artículo afirma resolver la pregunta abierta sobre la mejor eficiencia posible para la PIR de servidor único con preprocesamiento bajo supuestos de criptografía de caja negra.

• Resultados Incondicionales: A diferencia del trabajo previo (por ejemplo, [ISW24]) que dependía de supuestos de complejidad (como la separación de SZK y BPP) o restringía el modelo de consulta (ajena a la base de datos, de un solo viaje de ida y vuelta), estos límites inferiores son incondicionales y se aplican a una clase mucho más amplia de esquemas, incluyendo aquellos con múltiples rondas y consultas dependientes de la base de datos.
• Optimalidad de las Construcciones Actuales: Los resultados validan que las construcciones recientes que logran $\tilde{O}(n/s)$ de comunicación o computación son esencialmente óptimas; no se puede minimizar simultáneamente tanto la comunicación como la computación del servidor por debajo de este umbral sin romper los supuestos de criptografía de caja negra.
• Viabilidad de SPIR: El trabajo demuestra que la PIR Simétrica es alcanzable con solo OWF en la fase en línea, siempre que el número de consultas esté limitado al tamaño del estado almacenado por el cliente ($s$). Esto clarifica la relación entre la simetría (privacidad de los datos) y la capacidad de consulta en el modelo de preprocesamiento.
• Imposibilidad de DEPIR: El artículo descarta definitivamente la existencia de DEPIR de clave pública con computación de consulta sublineal a partir de criptografía de caja negra, resolviendo un problema abierto significativo en el campo.

En resumen, el artículo establece que los "cuellos de botella" identificados en las construcciones recientes de PIR (ya sea alta comunicación o alta computación del servidor) son limitaciones fundamentales inherentes a la criptografía de caja negra, y no meros artefactos de las técnicas de construcción actuales.