Seguridad Multi-Copia en Criptografía Inclonable

Información Básica

• ID del Artículo: 2510.12626
• Título: Multi-Copy Security in Unclonable Cryptography
• Autores: Alper Çakan, Vipul Goyal, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa
• Clasificación: quant-ph cs.CR (Física Cuántica, Criptografía y Seguridad)
• Fecha de Publicación: 14 de octubre de 2024 (Preimpresión en arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2510.12626v1

Resumen

La criptografía inclonable aprovecha el principio cuántico de no-clonación para proteger funciones criptográficas de ser copiadas. Aunque la mayoría de los trabajos existentes abordan la seguridad básica de una sola copia, el concepto más fuerte de seguridad multi-copia sigue siendo en gran medida inexplorado. Este artículo introduce un compilador universal que, asumiendo únicamente la existencia de funciones unidireccionales, actualiza primitivos inclon ables resistentes a colusión para lograr seguridad multi-copia. Utilizando este marco, los autores obtienen las primeras construcciones de seguridad multi-copia para moneda cuántica de clave pública (denominada moneda cuántica), cifrado de un único descifrador, cifrado inclonable, entre otros. El artículo también introduce un concepto extendido de moneda cuántica—moneda cuántica actualizable—que permite verificación débil bajo suposiciones más débiles y puede actualizarse a verificación completamente pública bajo suposiciones más fuertes mediante información clásica adicional publicada por el banco.

Antecedentes de Investigación y Motivación

Problema Central

El problema central que aborda este artículo es la actualización de seguridad de una sola copia a seguridad multi-copia. En criptografía inclonable, la investigación tradicional se ha enfocado principalmente en la configuración de no-clonación 1→2 (donde un adversario obtiene una copia de un estado cuántico puro pero no puede producir dos copias), mientras que la configuración más general q→q+1 (donde el adversario obtiene q copias pero no puede producir q+1 copias) ha sido menos estudiada.

Importancia del Problema

La seguridad multi-copia es significativa por las siguientes razones:

1. Ventaja Operacional: La igualdad de estados puros puede verificarse eficientemente mediante la prueba SWAP, lo cual es útil en aplicaciones
2. Anonimato: Múltiples copias del mismo estado puro proporcionan naturalmente garantías de anonimato
3. Motivación Conceptual: Múltiples copias de un estado puro corresponden al mismo objeto físico, mientras que estados muestreados de la misma distribución pueden ser diferentes

Limitaciones de Métodos Existentes

Los resultados existentes de seguridad multi-copia son muy limitados:

• Mosca y Stebila propusieron el concepto de moneda cuántica pero solo construyeron en el modelo de oráculo cuántico
• Algunos trabajos solo implementan conceptos de seguridad de oráculo más débiles
• Falta una conversión genérica de seguridad resistente a colusión a seguridad multi-copia

Contribuciones Principales

1. Compilador Universal Propuesto: Proporciona un compilador universal que actualiza primitivos inclon ables resistentes a colusión a seguridad multi-copia, asumiendo únicamente la existencia de funciones unidireccionales
2. Primeras Construcciones de Seguridad Multi-Copia: Obtiene las primeras construcciones de seguridad multi-copia para moneda cuántica, cifrado de un único descifrador, cifrado inclonable, entre otros
3. Moneda Cuántica Actualizable: Introduce un nuevo concepto que permite proporcionar diferentes niveles de garantías de seguridad bajo diferentes intensidades de suposiciones
4. Herramientas Técnicas: Construye un compilador de cifrado de un único descifrador de una sola copia a resistente a colusión, así como el primer esquema de cifrado inclonable seguro para múltiples desafíos

Explicación Detallada del Método

Definición de Tareas

Seguridad Multi-Copia: Para cualquier t polinomial, dado t copias del mismo estado cuántico puro, ningún adversario puede producir t+1 copias válidas. Esto difiere de la seguridad resistente a colusión, donde se proporcionan t estados generados independientemente.

Técnica Principal: Compilador de Purificación (Purification Compiler)

Teorema Principal (Teorema 7)

Sea GenState un algoritmo QPT con salida clásica determinista, donde la longitud de aleatoriedad es r(λ). Para la clave PRS k y la clave PRF K, se define:

$|ψ_{z,k,K}⟩ = \sum_x α_{k,x}|x⟩ ⊗ |φ_{z,F(K,x)}⟩$

donde $\sum_x α_{k,x}|x⟩$ es el estado producido por el esquema PRS, y $|φ_{z,F(K,x)}⟩$ es el estado obtenido al invocar GenState(z;F(K,x)).

Idea Central: A través de PRS y PRF, es posible convertir t estados generados independientemente en t copias del mismo estado, siendo computacionalmente indistinguibles.

Principio de Funcionamiento del Compilador

1. Fase de Consulta de Estado: El retador recibe del adversario el número t de copias solicitadas; originalmente ejecuta GenState(st) t veces usando aleatoriedad independiente
2. Después de la Modificación: El retador produce t estados idénticos: $\sum_x α_{k_i,x}|x⟩ ⊗ |φ_x⟩$ donde $|φ_x⟩ = \text{GenState}(st; F(K_i,x))$
3. Seguridad: Basada en la seguridad de PRS y PRF, el experimento modificado es computacionalmente indistinguible del experimento original

Ejemplos de Aplicación

1. Construcción de Moneda Cuántica

Compilador Basado en PRS:

• Configuración: Utiliza esquema mini-clave de clave pública, firma digital y PRS
• Estado del Banco: Contiene clave de firma, clave PRF y clave PRS
• Generación de Billete: Crea estado $|$⟩ = \sum_x α_x|x⟩|sn_x⟩|\text{Sign}(sgk, sn_x)⟩|$_x⟩$
• Verificación: Mide todos los registros excepto el registro mini-billete, verifica firma y mini-billete

2. Cifrado de Un Único Descifrador

Compilador de Una Clave a Resistente a Colusión:

• Utiliza cifrado funcional como capa intermedia
• Construye circuito REone.pk para manejar diferentes modos de cifrado
• Asegura seguridad en la prueba mediante ordenamiento de etiquetas

3. Cifrado Inclonable

Conversión de SDE a UE:

• Intercambia los roles de texto cifrado y clave
• Aprovecha la técnica de relleno de una sola vez
• Se basa en seguridad de búsqueda de desafío único resistente a colusión

Configuración Experimental

Marco de Análisis Teórico

Este artículo realiza principalmente análisis teórico, probando seguridad a través de una serie de experimentos híbridos:

1. Secuencia Híbrida: Construye una secuencia de experimentos híbridos computacionalmente indistinguibles
2. Argumento de Reducción: Reduce la seguridad de la nueva construcción a la seguridad de los primitivos subyacentes
3. Selección de Parámetros: Asegura que la pérdida de seguridad sea despreciable mediante selección apropiada de parámetros

Técnicas de Prueba de Seguridad

Prueba de Seguridad de Moneda Cuántica

• Hyb0 a Hyb1: Seguridad PRF
• Hyb1 a Hyb2: Lema de distribución de rango pequeño de estado cuántico de lectura única
• Híbridos Posteriores: Seguridad de firma digital BZ y esquema mini

Técnica de Implementación de Umbral

Utiliza la técnica de implementación de umbral de Zhandry et al.:

• TI_t(P): Implementación de umbral para POVM P
• Propiedades: Si la prueba pasa, la probabilidad de éxito del estado post-medición es al menos t

Resultados Experimentales

Resultados Teóricos Principales

Eficiencia de Construcción

1. Moneda Cuántica: Basada en ofuscación de subespacio oculto y funciones unidireccionales
2. Cifrado de Un Único Descifrador: Basado en iO polinomialmente seguro y funciones unidireccionales
3. Cifrado Inclonable: Basado en iO polinomialmente seguro y funciones unidireccionales

Garantías de Seguridad

• Seguridad Multi-Copia: Para cualquier número polinomial de copias
• Modelo Estándar: No depende del oráculo aleatorio
• Suposiciones Óptimas: Suposiciones más débiles en comparación con trabajos existentes

Análisis Comparativo

Comparación con Trabajos Existentes

vs. Poremba et al. PRV24:

• Este Artículo: Seguridad multi-copia ilimitada, conceptos de seguridad estándar
• PRV24: Multi-copia acotada, concepto de seguridad de oráculo
• Intensidad de Suposiciones: Este artículo requiere iO, PRV24 solo requiere funciones unidireccionales

vs. Ananth et al. AMP25:

• Este Artículo: Seguridad de eliminación autenticada estándar
• AMP25: Concepto de seguridad de oráculo
• Escenarios Aplicables: Este artículo soporta configuraciones reutilizables y de clave pública

Trabajo Relacionado

Desarrollo de Criptografía Inclonable

1. Moneda Cuántica: De la codificación conjugada de Wiesner a esquemas modernos de clave pública
2. Protección de Copia: Protección cuántica de copia de programas
3. Alquiler Seguro: Transferencia de derechos de uso temporal de claves
4. Eliminación Autenticada: Eliminación de datos comprobable

Multi-Copia vs Resistente a Colusión

• Resistente a Colusión: Múltiples estados generados independientemente
• Multi-Copia: Múltiples copias del mismo estado cuántico puro
• Diferencias Técnicas: Requieren diferentes técnicas de análisis y reducciones de seguridad

Conclusiones y Discusión

Conclusiones Principales

1. Proporciona por primera vez un compilador universal de seguridad resistente a colusión a seguridad multi-copia
2. Resuelve el problema de construcción de moneda cuántica en el modelo estándar
3. Implementa versiones de seguridad multi-copia de múltiples primitivos inclon ables importantes

Limitaciones

1. Intensidad de Suposiciones: Algunas construcciones requieren suposiciones criptográficas más fuertes (como iO)
2. Problemas de Eficiencia: El compilador puede introducir gastos computacionales adicionales
3. Alcance de Aplicación: Requiere que los algoritmos subyacentes tengan salida clásica determinista

Direcciones Futuras

1. Optimización de Suposiciones: Buscar construcciones basadas en suposiciones más débiles
2. Mejora de Eficiencia: Optimizar la implementación concreta del compilador
3. Nuevas Aplicaciones: Explorar aplicaciones de seguridad multi-copia en otros primitivos criptográficos

Evaluación Profunda

Fortalezas

1. Avance Teórico: Resuelve el importante problema teórico de seguridad multi-copia
2. Universalidad: Proporciona un marco unificado aplicable a múltiples primitivos
3. Innovación Técnica: Combina ingeniosamente técnicas de PRS, PRF y pruebas cuánticas
4. Completitud: Proporciona soluciones completas desde el marco teórico hasta construcciones concretas

Deficiencias

1. Practicidad: Basado en suposiciones teóricas más fuertes, el despliegue real puede enfrentar desafíos
2. Análisis de Eficiencia: Carece de análisis de eficiencia concreto y discusión de optimización
3. Selección de Parámetros: La selección de ciertos parámetros de seguridad carece de orientación concreta

Impacto

1. Contribución Teórica: Proporciona herramientas teóricas importantes para criptografía inclonable
2. Significado Inspirador: Proporciona nuevas ideas y métodos para investigaciones posteriores
3. Potencial de Aplicación: Tiene perspectivas de aplicación en criptografía cuántica, cadenas de bloques y otros campos

Escenarios Aplicables

1. Sistemas de Moneda Cuántica: Moneda digital que requiere protección contra falsificación y anonimato
2. Protección de Derechos de Autor Digital: Protección de copia de software y contenido
3. Computación Segura Multiparte: Computación de preservación de privacidad en entornos cuánticos

Referencias

El artículo cita literatura importante en criptografía cuántica, criptografía inclonable y herramientas matemáticas relacionadas, incluyendo:

• Trabajo original de moneda cuántica de Wiesner
• Moneda cuántica de clave pública de Aaronson-Christiano
• Estados cuánticos pseudoaleatorios de Ji-Liu-Song
• Técnicas de prueba cuántica de Zhandry
• Trabajos recientes en cifrado inclonable y alquiler seguro

Evaluación General: Este es un artículo de criptografía teórica de alta calidad que resuelve un importante problema abierto en criptografía inclonable, proporcionando un marco teórico elegante y construcciones concretas que tienen un impacto significativo en el desarrollo de este campo.