⚛️ quantum physics

Constant-Rate Certified Deletion

Este artículo presenta un marco unificado que actualiza una amplia clase de primitivas criptográficas para admitir la eliminación certificada de tasa constante en el modelo simple sin supuestos adicionales, logrando las primeras construcciones de este tipo que preservan la seguridad eterna y permiten la verificabilidad pública bajo supuestos de dureza estándar.

Autores originales: Kai-Min Chung, Tzu-Hsiang Huang, Wei-Hsiang Hung, Shota Yamada

Publicado 2026-10-05

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Kai-Min Chung, Tzu-Hsiang Huang, Wei-Hsiang Hung, Shota Yamada

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

En el mundo digital moderno, el derecho al olvido es un concepto legal que exige más que simplemente borrar un archivo; requiere la prueba de que los datos se han ido verdaderamente. Este es un desafío fundamental porque la información clásica, como un mensaje de texto o una foto, puede copiarse infinitamente. Incluso si un archivo se bloquea con un código secreto, un avance futuro en la computación o una filtración de la clave podrían permitir que un adversario lo desbloquee y recupere el contenido original. La única forma de garantizar que los datos hayan sido borrados es confiar en las leyes de la física, específicamente en las extrañas reglas de la mecánica cuántica. En el reino cuántico, la información se comporta de manera diferente: no puede copiarse perfectamente, y el acto de medirla inevitablemente la perturba. Esta naturaleza destructiva ofrece una oportunidad única: si una pieza de datos se almacena en un estado cuántico, uno puede obligar a un usuario a medirla de una manera específica para demostrar que la ha destruido, dejándole sin forma de recuperar la información original.

Durante años, los investigadores han trabajado en un método llamado eliminación certificada, que permite a un usuario generar un certificado que pruebe que ha eliminado un secreto. Sin embargo, un gran obstáculo siempre ha sido la eficiencia. Los métodos anteriores requerían una cantidad masiva de almacenamiento cuántico para proteger incluso una mínima cantidad de datos. Para cifrar un solo bit de información, estos esquemas antiguos necesitaban un número de partículas cuánticas que crecía linealmente con el nivel de seguridad, lo que hacía que el sistema fuera poco práctico para mensajes grandes. Era como intentar enviar una postal pero necesitar un almacén lleno de contenedores de transporte solo para proteger la tinta del papel. Esta ineficiencia significaba que, aunque el concepto era teóricamente sólido, era demasiado pesado para ser útil en aplicaciones del mundo real como la mensajería segura o el almacenamiento en la nube.

Un equipo de investigadores ha resuelto ahora este problema desarrollando un nuevo marco de trabajo que logra una eliminación certificada de tasa constante. Esto significa que la cantidad de almacenamiento cuántico requerido crece en proporción directa al tamaño del mensaje, en lugar de explotar con los requisitos de seguridad. En su nuevo sistema, la sobrecarga es mínima; para un mensaje grande, los datos cuánticos necesarios son solo ligeramente mayores que el propio mensaje, permitiendo una tasa de eficiencia que antes se consideraba imposible en entornos estándar. Lograron esto creando un método unificado que funciona para una amplia variedad de herramientas criptográficas, incluyendo sistemas utilizados para el cifrado de clave pública, el acceso basado en atributos y el cifrado totalmente homomórfico, que permite realizar cálculos sobre datos cifrados.

Los investigadores demostraron que su enfoque funciona para dos tipos distintos de codificaciones cuánticas. El primer tipo se basa en un método similar al famoso protocolo BB84, que se utiliza para la distribución segura de claves. El segundo tipo utiliza estructuras más complejas conocidas como estados de coset de subespacios, que permiten funciones más avanzadas como la delegación ciega y el arrendamiento de software seguro. En ambos casos, el nuevo marco permite que el mensaje sea cifrado y luego eliminado con un certificado que es verificado sin necesidad de confiar en la persona que realiza la eliminación. Crucialmente, esta eficiencia se logra sin introducir ningún nuevo supuesto no probado sobre la dureza de los problemas matemáticos; se basa únicamente en los mismos fundamentos que utilizaron los esquemas criptográficos originales.

Más allá de simplemente hacer el proceso más rápido y ligero, el equipo también mostró cómo hacer que la verificación de la eliminación sea pública. En muchos escenarios de seguridad, no basta con que solo el remitente sepa que los datos han desaparecido; un tercero o un auditor público debería poder verificar la eliminación sin necesidad de tener acceso a las claves secretas. Los intentos previos de añadir esta característica de verificación pública destruyeron las ganancias de eficiencia, requiriendo una cantidad lineal de datos adicionales que anulaba los beneficios. Los investigadores superaron esto utilizando una técnica que involucra firmas restringidas, un tipo de firma digital que puede ser verificada por cualquier persona pero que solo puede crearse bajo condiciones específicas. Al combinar esto con su marco de tasa constante, crearon un sistema donde cualquiera puede verificar que los datos han sido eliminados, y el sistema sigue siendo lo suficientemente eficiente como para manejar mensajes grandes.

El trabajo proporciona una solución unificada que actualiza una amplia clase de primitivas criptográficas para soportar esta eliminación verificable de alta eficiencia. Por primera vez, es posible tener un sistema donde los datos cuánticos requeridos para proteger un mensaje son aproximadamente del mismo tamaño que el mensaje mismo, mientras se garantiza que los datos pueden ser borrados de forma comprobable. Este avance elimina la sobrecarga significativa que anteriormente hacía que la eliminación certificada fuera poco práctica, abriendo la puerta para que estas características de seguridad cuántica se integren en las futuras tecnologías de preservación de la privacidad. Los investigadores demostraron que estos resultados se mantienen incluso contra adversarios con capacidad de cómputo ilimitada, siempre que el certificado de eliminación se verifique con éxito, asegurando que los datos se hayan ido para siempre de una manera que los sistemas clásicos nunca podrán lograr.

Resumen Técnico: Eliminación Certificada de Tasa Constante

1. Planteamiento del Problema

El artículo aborda el desafío fundamental de la Eliminación Certificada (CD) en criptografía. La CD permite que un usuario demuestre a un tercero que ha eliminado un fragmento de datos, incluso si los datos fueron previamente cifrados. Esto se motiva por el "derecho al olvido" en las regulaciones de privacidad (por ejemplo, el RGPD).

En el mundo clásico, la CD es imposible porque la información clásica puede copiarse arbitrariamente; un adversario podría retener una copia del texto cifrado y descifrarlo más tarde si la clave secreta se filtra. La información cuántica ofrece una solución mediante el teorema de no clonación y el principio de incertidumbre, que impiden que un adversario copie un estado y lo mida en dos bases incompatibles simultáneamente.

Sin embargo, las construcciones de CD existentes en el modelo plano (sin oráculos aleatorios) sufren de una ineficiencia crítica: requieren un número lineal de qubits ( $\Theta(\lambda)$ ) para cifrar un solo bit clásico. Esto resulta en un costo de comunicación total de $\Theta(n\lambda)$ para un mensaje de $n$ bits, lo que produce una tasa subconstante ( $O(\log \lambda)/\Theta(\lambda)$ ). La barrera principal para lograr una CD de tasa constante (donde el número de qubits es proporcional al tamaño del mensaje, $O(n)$ ) es la técnica de prueba utilizada en trabajos previos (específicamente [BK23]), que depende de "adivinar" toda la cadena del mensaje para retrasar la dependencia de la longitud real del mensaje. Este paso de adivinación incurre en una pérdida de seguridad exponencial en la longitud del mensaje, lo que lo hace inviable para mensajes largos.

2. Metodología

Los autores proponen un marco unificado para superar la barrera de la pérdida de seguridad exponencial, permitiendo la CD de tasa constante para dos clases amplias de primitivas: aquellas basadas en estados BB84 y aquellas basadas en estados de coset de subespacios.

Innovaciones Técnicas Centrales

Adivinación por Posición con Extractores Lineales:
En lugar de adivinar toda la cadena del mensaje (lo que causa una pérdida exponencial), los autores emplean una estrategia de adivinación posición por posición. Reemplazan el extractor XOR simple (usado en [BK23]) con un extractor lineal de alta tasa basado en un código de Distancia Máxima Separable (MDS) sobre un cuerpo finito $\mathbb{F}$ .
- El mensaje $m$ es enmascarado usando un mapa lineal $R$ aplicado a un estado cuántico, más un relleno (pad) aleatorio $r$ .
- La prueba de seguridad procede adivinando un elemento de cuerpo a la vez del mensaje. Para evitar que el adversario gane información sobre las partes no adivinadas, los autores introducen un nuevo relleno aleatorio $r$ que aplica un one-time pad computacional al filtrado (leakage) de los bits restantes del mensaje.
Muestreo Diferido y Purificación:
Para restaurar el argumento de "cortar y elegir" (cut-and-choose) en el entorno de tasa constante, los autores difieren el muestreo de la cadena de bases $\theta$ (o los parámetros del subespacio) hasta después de que el adversario emita su certificado de eliminación.
- Utilizan técnicas de purificación para tratar el estado cuántico como un par EPR entrelazado entre el desafiante y el adversario.
- Al introducir el relleno aleatorio $r$ , pueden retrasar la elección de $\theta$ sin alterar la distribución conjunta de la visión del adversario. Esto permite que el desafiante mida el estado en la base correcta solo después de verificar el certificado, asegurando que el adversario haya medido efectivamente en la base incorrecta para los bits relevantes.
Predicados Verificables Eficientemente:
Un paso crucial en la prueba es transferir el argumento de seguridad de un "mundo ideal" (donde el cifrado es trivial) a un "mundo real" (donde el cifrado depende de suposiciones computacionales). Los autores definen un predicado verificable eficientemente que verifica si el estado residual del adversario satisface una condición estructural específica (por ejemplo, ser cercano a un estado donde los errores son dispersos).
- Para los estados BB84, esto implica aplicar una transformada de Fourier y usar la capacidad de corrección de errores del código MDS para recuperar el vector de error.
- Para los estados de coset de subespacios, utilizan una ingeniosa estrategia de purificación que separa el filtrado del estado entrelazado, sorteando los problemas de entrelazamiento que afectaron a intentos previos de aplicar esta técnica a los estados de coset.
Verificabilidad Pública mediante Firmas Restringidas:
Para lograr una Eliminación Verificable Públicamente (PVD) sin sacrificar la tasa constante, los autores incorporan Firmas Restringidas (CS) basadas en la suposición de Solución de Enteros Cortos (SIS).
- En lugar de firmar qubits individuales (lo que añadiría un exceso lineal), firman toda la superposición del estado cuántico de forma coherente.
- Utilizan una clave de firma restringida asociada con un predicado que verifica si una cadena pertenece al conjunto válido definido por la codificación cuántica (por ejemplo, $T_{x,\theta}$ ).
- Al aprovechar la privacidad de la función de las CS y funciones hash 4-independientes (para simular un oráculo aleatorio), aseguran que la firma de la superposición no filtre información sobre el mensaje subyacente o la base, manteniendo al mismo tiempo un tamaño de firma que es polinómico en el parámetro de seguridad $\lambda$ pero independiente de la longitud del mensaje $n$ .

3. Contribuciones Clave y Resultados

A. Eliminación Certificada de Tasa Constante para Estados BB84

Los autores establecen un teorema para CD basado en estados BB84 que logra una tasa de $(1-\epsilon)$ para cualquier $\epsilon > 0$ constante.

Alcance: Se aplica a primitivas de tipo "todo o nada" (all-or-nothing), incluyendo Esquemas de Compromiso, Cifrado de Clave Secreta (SKE), Cifrado de Clave Pública (PKE), Cifrado Basado en Atributos (ABE), Cifrado Totalmente Homomórfico (FHE), Cifrado de Liberación de Tiempo y Cifrado de Testigo.
Mecanismo: Utiliza códigos MDS sobre cuerpos finitos y la técnica de adivinación por posición.
Resultado: El costo de comunicación es de $O(n)$ qubits para un mensaje de $n$ bits, una mejora significativa respecto al anterior $\Theta(n\lambda)$ .

B. Eliminación Certificada de Tasa Constante para Estados de Coset de Subespacios

Los autores extienden el marco a los estados de coset de subespacios, logrando una tasa de $1/4$ .

Alcance: Se aplica a primitivas más allá de "todo o nada", incluyendo Delegación Ciega, Arrendamiento de Software Seguro, Cifrado Funcional (FE), Ofuscación de Funcionalidad Diferente (diO) y CCA-PKE.
Mecanismo: Utiliza una novedosa técnica de purificación que evita las barreras de entrelazamiento presentes en las pruebas basadas en BB84 cuando se aplican a estados de coset.
Resultado: Esta es la primera construcción de tasa constante para estas primitivas avanzadas en el modelo plano.

C. Eliminación Certificada Verificable Públicamente (PVD)

Bajo la dureza de la suposición SIS, los autores construyen esquemas de PVD que preservan la propiedad de tasa constante.

Significancia: Las construcciones de PVD anteriores requerían un exceso lineal (destruyendo la tasa) o dependían de suposiciones fuertes como la Ofuscación de Indistinguibilidad (iO).
Resultado: El artículo proporciona los primeros esquemas de PVD de tasa constante tanto para primitivas basadas en BB84 como en estados de coset, asumiendo solo SIS.

4. Significancia y Reivindicaciones

El artículo afirma resolver un problema de larga data en la criptografía cuántica: construir esquemas de eliminación certificada con tasa constante en el modelo plano manteniendo la seguridad eterna (seguridad contra adversarios ilimitados después de la eliminación).

Superación de Barreras: El trabajo identifica y supera explícitamente la "barrera de la adivinación" inherente a la técnica de prueba de [BK23], que anteriormente limitaba la CD a longitudes de mensaje logarítmicas.
Marco Unificado: Proporciona un compilador genérico que actualiza una amplia gama de primitivas criptográficas para soportar CD sin introducir nuevas suposiciones más allá de las requeridas por las primitivas subyacentes (excepto SIS para PVD).
Eficiencia Práctica: Al reducir el exceso de qubits de lineal en el parámetro de seguridad a un factor constante, los resultados hacen que la eliminación certificada sea teóricamente viable para aplicaciones de datos a gran escala.
Modestia: Los autores señalan que, aunque logran tasas constantes, la tasa para estados BB84 es aproximadamente $1/3$ (o $1-\epsilon$ con parámetros desequilibrados) y $1/4$ para estados de coset, en lugar de acercarse a 1. También reconocen que su compilador PVD para primitivas de estados de coset de subespacios no se extiende actualmente a todas las primitivas de "más allá de todo o nada" (como diO o FE) debido a las dificultades para descomputar coherentemente las firmas dentro de las funcionalidades clásicas, aunque sí funciona para CCA-PKE.

En resumen, este trabajo demuestra que la eliminación certificada puede lograrse con alta eficiencia (tasa constante) y fuertes garantías de seguridad (seguridad eterna y verificabilidad pública) utilizando suposiciones de redes estándar, marcando un paso significativo hacia la viabilidad práctica de la eliminación de datos segura contra ataques cuánticos.