Resumen Técnico: SHARD – División de Residuos Basada en Claves de Celda para la Alineación Resistente en la Recuperación Densa Privada

1. Planteamiento del Problema

Los embeddings densos son la base de la búsqueda semántica moderna y de la Generación Aumentada por Recuperación (RAG). Sin embargo, un almacén de vectores filtrado compromete efectivamente el texto subyacente, como lo demuestran ataques recientes que incluyen alineación de pocos disparos (few-shot), inversión de cero disparos (zero-shot) y traslación de espacio no supervisada. Estos ataques explotan una debilidad fundamental en las defensas ligeras existentes: el almacén de vectores protegido es una geometría global única.

Las defensas actuales suelen recurrir a un enfoque "global-lineal": comprimir los embeddings mediante truncamiento SVD, aplicar una rotación ortogonal secreta única y utilizar Cuantización de Producto (PQ) para el indexado. El artículo argumenta que este enfoque es frágil porque cualquier geometría global puede ser alineada con un espacio de referencia conocido. Una vez que un atacante recupera la rotación secreta (usando aproximadamente $k = d/2$ pares de texto plano conocidos mediante Procrustes Ortogonal), la protección colapsa, permitiendo la recuperación casi exacta del texto. Además, las defensas estándar enfrentan un dilema: la Privacidad Diferencial (DP) destruye la utilidad de clasificación antes de proporcionar una privacidad significativa, mientras que el Cifrado Totalmente Homomórfico (FHE) es demasiado costoso computacionalmente para la búsqueda top-$k$ a gran escala.

2. Metodología: La Construcción de Shard

El artículo introduce Shard, una transformación de embedding que preserva la recuperación diseñada para eliminar el "eje débil" de la alineación global en lugar de enmascarar la distorsión. Shard divide el espacio de embedding en dos componentes y aplica protecciones distintas a cada uno:

1. Prefijo Público ($u$): El embedding es centrado y rotado. Los $d_{pub}$ componentes principales superiores (direcciones de alta varianza) forman un prefijo público corto. Este se utiliza para la recuperación de Etapa 1 (ANN) mediante un índice de Cuantización de Producto público.
2. Residuo Privado ($r$): Las dimensiones restantes ($d_{priv} = d - d_{pub}$) forman el residuo privado.
   • División Basada en Claves de Celda: El espacio residual se particiona en $C$ celdas gruesas (definidas por el prefijo público $u$).
   • Claves Locales: A cada celda $c$ se le asigna una clave ortogonal secreta única $H_c$ (un producto de reflexiones de Householder).
   • Almacenamiento: El servidor almacena el prefijo $u_i$ y el fragmento de residuo con clave $z_i = H_{c(i)} r_i$.
   • Procesamiento de la Consulta:
     • Etapa 1: El cliente utiliza el prefijo público $u_q$ para recuperar una lista corta de candidatos localmente.
     • Etapa 2 (Reclasificación): Para cada candidato, el cliente cifra el residuo de la consulta $r_q$ bajo CKKS (cifrado homomórfico) como $H_{c(i)} r_q$. El servidor calcula el producto interno $\langle H_{c(i)} r_q, z_i \rangle$ en modo texto cifrado-texto plano.
     • Recuperación Exacta: Debido a que $H_c$ es ortogonal, las claves se cancelan: $\langle H_c r_q, H_c r_i \rangle = \langle r_q, r_i \rangle$. El servidor devuelve puntuaciones cifradas que se descifran al producto interno exacto de los residuos originales.

El parámetro $C$ interpola entre la base global ($C=1$, una clave global) y las micro-claves por documento ($C=N$, una clave por documento).

3. Contribuciones Clave

El artículo realiza las siguientes contribuciones específicas en relación con el trabajo anterior (específicamente el sistema híbrido global-lineal previo de los autores):

• División de Residuos Basada en Claves de Celda: Una construcción que reemplaza una única geometría global por $C$ subespacios con claves locales, evitando que un único ataque de alineación recupere todo el almacén.
• Reclasificación de Dimensiones Completas: A diferencia de las bases de truncamiento SVD que reclasifican en un espacio reducido, Shard reclasifica en el espacio de dimensiones completas (prefijo + residuo), recuperando la calidad de recuperación bruta perdida por el truncamiento.
• Resistencia a la Alineación Escalable: El artículo establece una ley de escala donde el costo de un ataque de alineación de texto plano conocido difuso crece por un factor de $\approx C$. Recuperar el marco nativo requiere $O(C \cdot d_{priv})$ anclajes en lugar de $O(d)$.
  আছে
• Reducción de la Filtración Pública: Al exponer solo un prefijo corto ($d_{pub} \ll d$), el índice público filtra significativamente menos estructura de vecindad.
• Evaluación Consciente del Ataque: El artículo evalúa Shard contra familias de atacantes más fuertes (lineal aprendido, MLP no lineal y no supervisado) y lo compara con defensas conscientes de la distorsión (ruido DP), demostrando que el uso de claves proporciona resistencia donde el ruido falla.

4. Resultados Experimentales

Los experimentos se realizaron utilizando embeddings en caché de cinco codificadores (incluyendo multilingual-E5 y BGE-M3) a través de BEIR, MIRACL y un corpus de 1 millón de documentos de la Wikipedia rusa.

• Utilidad (nDCG@10): Shard recupera el techo de clasificación del espacio bruto. En tareas de BEIR donde el truncamiento SVD causó una caída de 2 a 8 puntos en nDCG@10, Shard igualó la base bruta (por ejemplo, 0.638 frente a 0.637 bruto) exponiendo un canal público de solo 1/4 a 1/2 de su ancho.
• Resistencia a la Alineación:
  • Base Global: Recuperada con ~200 anclajes (para $d=384$).
  • Shard ($C=64$): Requirió ~25,600 anclajes.
  • Shard ($C=256$): Requirió ~102,400 anclajes (mediana).
  • Robustez del Atacante: Los atacantes lineal aprendido, MLP no lineal y no supervisado no funcionaron mejor que el ataque estándar de Procrustes Ortogonal; ninguno superó el umbral de anclajes de $d_{priv}$ para una sola celda.
• Filtración del Índice Público: El prefijo público reveló significativamente menos estructura de vecindad que la base. Para un prefijo de $d/4$, el solapamiento de NN@10 cayó de 0.76 (base) a 0.55 (Shard).
• Límite de Micro-Clave: Cuando $C=N$ (claves por documento), la filtración del grafo de residuos cae a 0.00, y el sistema se vuelve invinculable (AUC de re-clave $\approx 0.5$).
• Comparación con Ruido DP: Una defensa de DP consciente de la distorsión igualó la utilidad de Shard solo con $\sigma=0$ (sin ruido), donde la desanonimización era del 100%. Cualquier ruido añadido para reducir la desanonimización degradó la utilidad por debajo del rendimiento de Shard. Shard logró alta utilidad con 0% de desanonimización.
• Limitaciones Observadas:
  • Ataques Dirigidos: Un atacante dirigido que concentre anclajes en la celda de una víctima específica solo necesita $\approx d_{priv}$ anclajes, independientemente de $C$.
  • Referencia de Solapamiento: Si un atacante posee un corpus de referencia con solapamiento, el prefijo público (incluso si está clave con una única clave global) permite la desanonimización una vez que se recupera dicha clave.
  • Patrones de Acceso: Al igual que la base, Shard no oculta los patrones de acceso (qué documentos son reclasificados).

5. Significado y Reivindicaciones

El artículo posiciona a Shard como una defensa geométrica consciente del ataque, declarando explícitamente que no es una garantía criptográfica para los documentos almacenados.

• Logro Central: Shard desplaza la relación de compromiso entre privacidad y precisión al eliminar la vulnerabilidad de la "geometría global única". Permite una reclasificación exacta de dimensiones completas (preservando la utilidad) mientras hace que la alineación del residuo privado sea computacionalmente costosa para atacantes difusos.
• Filosofía de Diseño: El trabajo mueve la privacidad de los embeddings desde la optimización contra un sustituto de distorsión ($\sigma_{rec}$) hacia el endurecimiento contra superficies de ataque específicas (alineación y filtración de índices).
• Reivindicaciones Modestas: Los autores son explícitos sobre lo que Shard no hace:
  • No protege contra ataques dirigidos que concentran anclajes en una sola celda.
  • No evita la desanonimización mediante corpus de referencia con solapamiento si se recupera la clave del prefijo público.
  • No oculta los patrones de acceso.
  • La rotación secreta es una capa de ofuscación empírica, no un primitivo criptográfico.

El artículo concluye que Shard ofrece una familia ajustable de transformaciones (mediante el parámetro $C$) que pueden ser revocadas a nivel de celda, proporcionando una defensa práctica y medida contra los ataques de alineación modernos en sistemas de recuperación densa, siempre que el sistema se componga con otras primitivas (como PIR) para manejar los patrones de acceso y los solapamientos de referencia.