HIC Is All You Need: PAPKE poscuántico explicado

Las contraseñas suelen verse como la parte antigua de la seguridad: útiles, familiares y frágiles. El cifrado de clave pública suele verse como la parte moderna: potente, asíncrono y dependiente de claves públicas auténticas.

Password-Authenticated Public-Key Encryption conecta esas dos ideas. Este artículo explica el primitivo PAPKE original, por qué no es lo mismo que cifrar un archivo con una contraseña, y cómo este artículo, HIC Is All You Need, acerca la construcción a instanciaciones poscuánticas prácticas.

El problema: las claves públicas también necesitan autenticación

El cifrado de clave pública resuelve un problema: un remitente puede cifrar para la clave pública de un destinatario. Pero deja otro abierto: ¿cómo sabe el remitente que esa es realmente la clave pública del destinatario?

En sistemas reales, esa autenticidad suele venir de PKI, certificados, un directorio de confianza, un proveedor de mensajería o una comparación manual de huellas. Esos mecanismos son útiles, pero no siempre están disponibles, son simples o son deseables.

Password-Authenticated Public-Key Encryption, o PAPKE, pregunta si una contraseña compartida y corta puede autenticar una clave pública sin convertir esa clave o los cifrados posteriores en una herramienta para probar contraseñas fuera de línea.

Qué añade PAPKE

El artículo PAPKE original de Bradley, Camenisch, Jarecki, Lehmann, Neven y Xu introdujo Password-Authenticated Public-Key Encryption como un primitivo que combina cifrado de clave pública con autenticación por contraseña.

A alto nivel, PAPKE permite que el destinatario publique una clave pública reutilizable autenticada con una contraseña compartida y memorizable. Un remitente que conoce la contraseña puede usar esa clave pública autenticada y cifrar un mensaje de forma asíncrona.

Un atacante que sustituya o manipule esa clave pública no debería poder montar un ataque de intermediario salvo que pueda adivinar la contraseña en línea. Al mismo tiempo, observar la clave pública autenticada o los cifrados no debería permitir probar contraseñas fuera de línea.

La advertencia es importante: la autenticación de la clave pública es tan fuerte como la contraseña compartida. PAPKE no es una solución mágica para contraseñas débiles o reutilizadas. Si la contraseña se revela más tarde, un atacante puede reconocer la clave pública autenticada y enviar nuevos mensajes cifrados al destinatario, pero eso no descifra por sí solo los mensajes ya cifrados; esos siguen dependiendo de la clave secreta del destinatario y de la seguridad del esquema de cifrado subyacente.

• Clave pública reutilizable: el destinatario puede publicar una vez una clave pública autenticada con contraseña y recibir mensajes cifrados más tarde.
• Comunicación asíncrona: el remitente puede cifrar sin ejecutar primero un intercambio de claves interactivo con el destinatario.
• Autenticación por contraseña: la contraseña autentica qué clave pública se acepta; no se trata como una clave de cifrado de alta entropía.
• Resistencia a diccionario fuera de línea: la clave pública autenticada y los cifrados no deben convertirse en verificadores baratos de contraseñas.

Cómo funciona PAPKE a alto nivel

Un modelo mental útil es separar PAPKE en configuración y cifrado.

Durante la configuración, el destinatario crea un par de claves de cifrado de clave pública. Luego la clave pública se transforma o protege usando la contraseña compartida, de modo que un remitente que conoce la contraseña pueda recuperar o validar la clave pública correcta.

Durante el cifrado, el remitente usa la contraseña para procesar la clave pública autenticada. Si la contraseña es correcta, obtiene la clave pública real de cifrado y cifra normalmente. Si la contraseña es incorrecta, el proceso no debe revelar suficiente información para probar conjeturas fuera de línea.

Esto es distinto del cifrado simétrico ordinario basado en contraseña. Si un atacante obtiene un texto cifrado protegido por contraseña, puede probar una contraseña, derivar una clave, descifrar y comprobar si el resultado parece texto normal. Eso es una prueba de diccionario fuera de línea. PAPKE conserva la estructura del cifrado de clave pública, pero usa la contraseña para autenticar la clave pública e impedir que la clave autenticada o los cifrados se conviertan en un oráculo barato de comprobación de contraseñas.

Por qué la construcción original usaba un cifrado ideal

La construcción PAPKE genérica del artículo original usa un esquema de cifrado de clave pública anónimo y seguro frente a CCA junto con un cifrado ideal sobre el dominio de las claves públicas.

Esto crea una tensión inusual. En el cifrado de clave pública ordinario, la clave pública está pensada para ser pública: cualquiera puede conocerla, copiarla y cifrar para ella. En PAPKE, la clave pública real sigue desempeñando ese papel después de la autenticación, pero la clave pública autenticada por contraseña no debe revelar suficiente estructura para que un atacante compruebe conjeturas de contraseña.

La intuición es que la contraseña oculta o transforma la clave pública para que parezca aleatoria a quien no conoce la contraseña. El modelo de cifrado ideal es una abstracción teórica limpia para esa operación.

Esa abstracción es útil en una prueba, pero incómoda de implementar. Los cifradores de bloque estándar operan sobre bloques fijos como 128 bits, mientras que las claves públicas modernas, especialmente las poscuánticas, son objetos estructurados mucho más grandes.

Por qué PAPKE poscuántico es más difícil

Muchas construcciones clásicas de tipo PAPKE y PAKE dependen de álgebra similar a Diffie-Hellman. Grandes ordenadores cuánticos tolerantes a fallos romperían los supuestos detrás de esos grupos clásicos, y estimaciones recientes de recursos hacen más concreta la presión migratoria. Un informe de Google Quantum AI estima que el algoritmo de Shor contra logaritmos discretos de curvas elípticas de 256 bits podría ejecutarse en minutos en algunas arquitecturas futuras de reloj rápido con menos de medio millón de qubits físicos. Un preprint de Oratomic/Caltech argumenta que códigos de corrección de errores de alta tasa y qubits atómicos reconfigurables podrían llevar instancias criptográficamente relevantes de Shor al rango de 10.000 a 100.000 qubits, con tiempos de ejecución más largos. Son estimaciones de recursos, no ataques desplegados, pero explican por qué la migración poscuántica se trata como urgente.

Una idea natural es reemplazar el cifrado de clave pública subyacente por un PKE o KEM poscuántico. Pero no es un reemplazo directo de ingeniería. La construcción todavía necesita una forma de autenticar claves públicas con contraseña sin filtrar estructura ni habilitar ataques de diccionario fuera de línea.

Aquí importan el tamaño y la estructura de las claves poscuánticas. Si la construcción espera un cifrado ideal sobre el dominio de claves públicas, y esas claves son grandes objetos basados en retículos o códigos, instanciar ese cifrado de forma eficiente se convierte en un obstáculo central.

HIC Is All You Need

En este artículo, Arriaga, Mestel, Oupicky, Ronne, Skrobot et al. proponen una forma de rodear ese obstáculo.

En lugar de requerir un cifrado ideal completo sobre el dominio de claves públicas, la construcción usa un Half-Ideal Cipher, o HIC. HIC fue introducido en un trabajo anterior de EUROCRYPT 2023 como una relajación de un cifrado ideal que aún puede bastar para ciertos protocolos autenticados por contraseña.

La idea es pragmática: no instanciar un objeto idealizado más fuerte de lo que la prueba realmente necesita. Si basta un objeto más débil y más eficiente de realizar, la construcción poscuántica se vuelve mucho más plausible.

La construcción resultante, PAPKE-HIC, se presenta como un esquema PAPKE seguro en UC construido a partir de un esquema de cifrado de clave pública y un HIC.

Qué necesita la variante poscuántica

El artículo de HIC no afirma que cualquier esquema poscuántico pueda incorporarse a ciegas. Mantiene la necesidad original de cifrado de clave pública anónimo y seguro frente a CCA, y precisa un punto de la prueba PAPKE-IC.

A alto nivel, el esquema de cifrado debe comportarse lo bastante bien para que las claves públicas autenticadas por contraseña y los cifrados no filtren el tipo equivocado de información ni creen comportamiento ambiguo de descifrado.

• Seguridad CCA: el PKE subyacente debe seguir siendo confidencial incluso frente a ataques adaptativos de texto cifrado elegido. Esto es más fuerte y más preciso que decir solo que los cifrados son difíciles de invertir.
• Anonimato de cifrado: un texto cifrado no debe revelar bajo qué clave pública fue cifrado, incluso cuando el atacante conoce las claves candidatas.
• Claves públicas pseudo-uniformes: las claves públicas generadas deben ser computacionalmente difíciles de distinguir de la distribución de claves que la construcción basada en HIC espera manipular.
• Robustez de descifrado: un texto cifrado no debe descifrar válidamente a mensajes contradictorios bajo distintas claves secretas de una forma que rompa la prueba del protocolo. El artículo captura la versión necesaria como DROB-CCA y la relaciona con nociones de robustez más fuertes.

Instanciaciones concretas

El artículo hace después la construcción más concreta. Estudia PAPKE-HIC construido a partir de una capa estándar de cifrado KEM+DEM usando ML-KEM, FrodoKEM y Classic McEliece. ML-KEM y FrodoKEM encajan en el análisis mediante la transformación Fujisaki-Okamoto con hash de prefijo, que da una ruta directa hacia la propiedad de robustez de descifrado necesaria. Classic McEliece es más delicado: el artículo discute una variante modificada y una transformación de clave pública hasheada como forma más de caja negra de obtener la robustez requerida. El código de benchmarks es público en el repositorio PAPKE-HIC benchmarks, implementado en C++ con Botan para primitivas criptográficas y Catch2 para mediciones. Los benchmarks muestran el punto práctico de HIC: para ML-KEM, PAPKE-HIC necesita una operación hash-to-group donde PAPKE-IC necesita varias; para cifrado con Classic McEliece, la variante HIC se reporta en torno a 0,26x el tiempo de la variante PAPKE-IC con Feistel de 8 rondas.

El significado práctico

La promesa de PAPKE es cifrado asíncrono sin PKI basado en una contraseña compartida. Encaja en situaciones donde dos personas pueden acordar una contraseña pero no quieren depender de certificados, proveedores de cuentas o comparaciones manuales de huellas.

La promesa de PAPKE-HIC es mover esa misma idea al contexto poscuántico. En lugar de depender de supuestos Diffie-Hellman, la construcción puede instanciarse con herramientas de cifrado de clave pública poscuánticas adecuadas.

La advertencia es que esto es diseño de protocolos criptográficos, no una simple función de aplicación. La seguridad no viene de mezclar una contraseña con una clave pública. Viene de un primitivo especificado cuidadosamente, un modelo de prueba y requisitos precisos sobre el esquema de cifrado subyacente y la transformación de clave pública basada en HIC.

La idea principal

PAPKE es útil porque trata las contraseñas como una herramienta para autenticar claves públicas, sin renunciar al objetivo de impedir ataques de diccionario fuera de línea.

El trabajo PAPKE original define el primitivo y su relación con PAKE. HIC Is All You Need muestra cómo la idea genérica de PAPKE puede hacerse práctica en dirección poscuántica al reemplazar un componente difícil de cifrado ideal por una construcción Half-Ideal Cipher.

En pocas palabras: las contraseñas pueden autenticar claves públicas, el cifrado de clave pública puede soportar mensajes asíncronos y las variantes poscuánticas se vuelven realistas cuando la transformación de la clave pública se diseña con la abstracción criptográfica adecuada.

Referencias

• Bradley et al.: Password-Authenticated Public-Key Encryption
• Arriaga, Mestel, Oupicky, Ronne, Skrobot: HIC Is All You Need
• Freitas Dos Santos, Gu, Jarecki: Randomized Half-Ideal Cipher on Groups
• Babbush et al.: Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities
• Cain et al.: Shor's algorithm is possible with as few as 10,000 reconfigurable atomic qubits
• PAPKE-HIC benchmark implementation repository