💻 computer science

What Can Verifiable Decapsulation Tests Certify? Pass Bounds and Fault-Recognition Limits for FO-Based KEMs

Este artículo establece límites teóricos y de reconocimiento de fallos para la verificación de Mecanismos de Encapsulación de Claves basados en Fujisaki-Okamoto, demostrando que las pruebas de decapsulación de caja negra están fundamentalmente limitadas por eventos de acierto de lista localizados y probando que las operaciones fuera del cono de soporte activo no pueden ser certificadas debido a las inherentes compensaciones entre solidez y completitud.

Autores originales: José Luis Delgado Jiménez

Publicado 2026-06-04

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: José Luis Delgado Jiménez

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

Imagina que estás contratando a un cerrajero para construir una bóveda de alta seguridad (un Mecanismo de Encapsulamiento de Claves, o KEM). Quieres estar seguro de que no tomó un atajo, como saltarse el paso de revisar su trabajo antes de entregarte la llave.

En el mundo de la criptografía post-cuántica, hay una forma estándar de verificar este trabajo llamada transformada de Fujisaki–Okamoto (FO). Es como una comprobación de "re-encriptación": el cerrajero desencripta un mensaje, lo vuelve a encriptar y compara el resultado con el original. Si coinciden, la llave es buena. Si el cerrajero se salta esta comprobación, podría entregarte la llave correcta por accidente, o podría entregarte una incorrecta.

Este artículo introduce una nueva forma, súper estricta, de probar a estos cerrajeros mediante la Decapsulación Verificable. Aquí está el desglose de lo que los autores descubrieron, utilizando analogías simples.

1. El truco del "Testigo Oculto"

Los autores proponen una modificación donde la clave final no solo se basa en el mensaje, sino también en un "testigo" oculto (un código secreto generado durante la revisión).

La Analogía: Imagina que el cerrajero tiene que escribir un código secreto en un papel después de terminar su trabajo, pero antes de entregarte la llave. Este código queda entonces encerrado dentro de la propia llave.
La Prueba: Tú (el evaluador) le das al cerrajero una caja cerrada. Él debe abrirla, hacer su trabajo, generar ese código secreto y entregarte la llave.
El Engaño: No le dices al cerrajero cuál debería ser el código secreto. Solo lo sabrás después. Si el cerrajero se saltó la revisión, no sabrá cuál es el código secreto. Si adivina el código equivocado, la llave que te entregue será incorrecta.

2. El problema de la "Caja Negra"

El artículo plantea: ¿Podemos demostrar que el cerrajero realmente hizo el trabajo simplemente mirando la llave que nos entregó?

Los autores dicen sí, pero con límites. Descubrieron que la prueba solo puede certificar que el cerrajero hizo el trabajo si el código secreto era verdaderamente impredecible.

El Límite de la "Lista de Aciertos": Imagina que el cerrajero es un tramposo que intenta adivinar el código secreto. Si tiene una lista de 100 códigos posibles, tiene una probabilidad de 1 entre 100 de acertar por pura suerte. El artículo demuestra que la probabilidad de que el cerrajero pase la prueba está directamente ligada al tamaño de su "lista de adivinación".
La Conclusión: Si el cerrajero pasa la prueba, es porque hizo el trabajo correctamente o porque tuvo una suerte increíble con un intento de adivinación. La prueba no puede distinguir entre "trabajo duro" y "adivinación afortunada" a menos que podamos demostrar que la adivinación era imposible.

3. El "Cono de Dependencia" (Lo que no puedes ver)

Esta es la parte más profunda del artículo. Los autores definen un "Cono de Dependencia".

La Analogía: Piensa en el trabajo del cerrajero como un árbol. El "código secreto" es el fruto en la parte superior de la copa. El "Cono de Dependencia" es el conjunto específico de ramas y hojas que deben ser tocadas para que crezca ese fruto.
El Descubrimiento: Si el cerrajero se salta un paso que está fuera de este cono (como pulir una hoja que no afecta al fruto), ninguna prueba de caja negra puede demostrar que se lo saltó.
¿Por qué? Porque puedes construir un cerrajero "falso" que se salte ese paso específico pero produzca exactamente el mismo fruto (llave) y el mismo rastro de papel. Para un observador externo, el cerrajero falso es idéntico al real.
La Regla: Solo puedes certificar que el cerrajero hizo el trabajo si el paso omitido estaba dentro del cono que conduce al código secreto. Si está fuera, la prueba es ciega ante ello.

4. Dos formas de pasar la prueba

El artículo muestra dos formas en las que se puede demostrar que un cerrajero hizo el trabajo:

La ruta de la "Seguridad de la Fuente": Si el código secreto se genera de una manera matemáticamente probada como impredecible (como un generador de números aleatorios perfecto), entonces pasar la prueba demuestra que el trabajo fue realizado.
La ruta de la "Entropía": Si el código secreto es lo suficientemente largo y desordenado (alta entropidad), la probabilidad de adivinarlo es tan minúscula que es prácticamente cero. El artículo calcula exactamente qué tan largo y desordenado debe ser el código para que la prueba sea fiable.

5. Pruebas del mundo real (ML-KEM y HQC)

Los autores probaron esta teoría en dos estándares criptográficos del mundo real: ML-KEM (utilizado en FIPS 203) y HQC.

El Experimento: Crearon versiones "mutantes" del código que omitían pasos intencionadamente (como saltarse la re-verificación o ignorar parte de la comparación).
Los Resultados:
- Fallos de Vinculación (Binding Faults): Cuando el mutante se saltó la parte que genera el código secreto, la prueba los atrapó el 100% de las veces.
- Fallos de Decisión (Decision Faults): Cuando el mutante se saltó un paso que solo importaba para malos inputs (como una caja malformada), la prueba no los atrapó en los inputs buenos. Esto demuestra que la prueba es tan buena como los inputs que se le proporcionan.
- Fallos Simétricos (Symmetric Faults): Si el mutante se saltó el paso tanto en el lado del emisor como en el del receptor, la prueba falló al atraparlos cuando se probaron a sí mismos (porque coincidían entre ellos). Pero cuando se probaron contra una referencia "honesta", la prueba los atrapó.

6. La trampa del "Autotest"

Un hallazgo importante es que probarse a uno mismo no es suficiente.

La Analogía: Si un estudiante escribe un examen y luego califica su propio examen, podría darse una nota de aprobado incluso si hizo trampas, porque sabe cómo deberían verse las respuestas.
El Veredicto del Artículo: Para verificar realmente el trabajo, necesitas una prueba de Referencia Honesta. Necesitas una parte independiente y confiable (el "soporte" o harness) para comprobar el trabajo contra una verdad oculta. Si el sistema solo se comprueba a sí mismo, puede ocultar muchos tipos de trampas.

Resumen de las afirmaciones

Lo que la prueba certifica: Certifica que el sistema computó un valor de "testigo secreto" específico.
Lo que la prueba NO puede certificar: No puede certificar que el sistema realizó cada uno de los pasos del algoritmo, solo los pasos que influyen directamente en ese testigo secreto.
La regla del "Cono": Si un paso está fuera del "cono" de influencia que conduce al testigo secreto, una prueba de caja negra no puede demostrar que se realizó.
La regla de la "Adivinación": La prueba es tan fuerte como la dificultad de adivinar el testigo secreto. Si el testigo es corto, el sistema puede pasar la prueba mediante la adivinación.

En resumen, este artículo proporciona un libro de reglas matemáticas sobre cómo construir un "detector de mentiras" para el código criptográfico. Nos dice exactamente qué puede ver ese detector de mentiras, a qué es ciego y cómo hacer que el "código secreto" sea lo suficientemente difícil de adivinar para que el detector de mentiras sea fiable.

Resumen Técnico: Pruebas de Desencapsulación Verificables para KEMs basados en FO

Planteamiento del Problema

Los Mecanismos de Encapsulación de Claves (KEMs) post-cuánticos basados en la transformación de Fujisaki–Okamoto (FO) dependen de una comprobación de desencapsulación crítica: el algoritmo debe desencriptar un criptograma, re-derivar la aleatoriedad de la encriptación, recomputar el criptograma y compararlo con el recibido antes de derivar la clave compartida. Si bien esta comprobación es crítica para la seguridad, las pruebas estándar de entrada-salida de caja negra suelen fallar al detectar fallos de implementación específicos. Una implementación podría omitir partes de la computación de re-encriptación o alterar la lógica de selección de ramas y, aun así, devolver la clave compartida esperada en criptogramas generados honestamente, eludiendo efectivamente la comprobación de seguridad sin activar un fallo en un entorno de pruebas estándar.

El artículo aborda la cuestión de qué se puede certificar formalmente sobre la ejecución de estas comprobaciones de desencapsulación mediante pruebas de caja negra, específicamente cuando el KEM está aumentado con códigos de confirmación.

Metodología y Modelo

Los autores proponen una teoría formal de desencapsulación FO aumentada con códigos de confirmación probada bajo un entorno de referencia honesto (honest-reference harness).

La Construcción Aumentada

El modelo extiende los KEMs estándar basados en FO introduciendo un testigo de confirmación oculto $W$ en la derivación de la clave final.

Encapsulación: Genera un criptograma y un valor de confirmación interno $W$ . La clave final $K$ se deriva como $K = G_K(\langle \text{good}, B, W \rangle)$ , donde $B$ es un prefijo de la transcripción localizado y $G_K$ es un oráculo aleatorio.
Desencapsulación: Recomputa el criptograma y el testigo de confirmación $W'$ . La clave final se deriva solo si $W' = W$ .
Entorno de Referencia Honesto (Honest-Reference Harness): El entorno de pruebas proporciona la entrada de desencapsulación (criptograma, claves) pero retiene el testigo oculto $W$ y la clave final $K$ . El SUT (Sistema Bajo Prueba) debe consultar el oráculo aleatorio $G_K$ con la tupla correcta $\langle \text{good}, B, W \rangle$ para producir la clave correcta.

Marco Teórico

El artículo define una lista de consultas de clave final localizada $Q_G(B)$ , que representa el conjunto de testigos candidatos que el SUT consulta contra el oráculo aleatorio. El núcleo de la metodología es acotar la probabilidad de que un SUT defectuoso pase la prueba (es decir, devuelva la clave correcta) analizando la probabilidad de un "acierto de lista" (list-hit): el evento de que el testigo oculto $W$ esté en $Q_G(B)$ .

El análisis distingue entre:

Pruebas de Referencia Honesta (Honest-Reference Testing): Comparar el SUT contra un par sound (sólido) generado por referencia.
Pruebas de Sí Mismo Honestas (Honest-Self Testing): Comparar el SUT contra sí mismo (tanto la encapsulación como la desencapsulación provienen del SUT).
Conos de Dependencia (Dependency Cones): Identificar el conjunto de operaciones que realmente influyen en el vector objetivo observable (la transcripción y la clave final).

Contribuciones Clave

1. Teorema de Detectabilidad de Acierto de Lista Estrecho

El resultado central (Teorema 5.1) establece que para cualquier SUT $q$ -localizado, la probabilidad de paso bajo un entorno de referencia honesto está acotada por:
$\text{Pass} \leq \delta_{\Pi_C} + \epsilon_{\text{alias}} + \epsilon_{\text{fresh}} + \Pr[W \in Q_G(B)] + 2^{-\kappa}$
Donde:

$\delta_{\Pi_C}$ es el error de corrección honesta.
$\epsilon_{\text{alias}}$ contabiliza el aliasing adversario (colisiones en la codificación de la clave final).
$\epsilon_{\text{fresh}}$ contabiliza los defectos de frescura de la clave final (filtración del punto oculto).
$\Pr[W \in Q_G(B)]$ es el término de acierto de lista (list-hit term), que representa la probabilidad de que el SUT adivine el testigo oculto.
$2^{-\kappa}$ es el término de coincidencia del oráculo aleatorio.

El artículo demuestra que este límite es estrecho (Teorema 5.2): cualquier predictor de $W$ desde la vista del SUT induce un SUT de una sola consulta con una probabilidad de paso que coincide con la tasa de éxito del predictor. Por lo tanto, el término de acierto de lista es la obstrucción fundamental medida por el entorno.

2. Dos Rutas para Acotar el Término de Acierto de Lista

El artículo proporciona dos métodos distintos para acotar el término de acierto de lista inevitable:

Ruta de Seguridad de la Fuente (cUP-faithful): Si el entorno es "fiel a la cUP de la fuente" (faithful to the source confirmation-code unpredictability game), la probabilidad de acierto de lista está acotada por $q \cdot \epsilon_{\text{cUP}}$ , donde $\epsilon_{\text{cUP}}$ es la ventaja de un adversario de candidato único en el juego de la fuente. Esto transfiere las pruebas de seguridad de la fuente al contexto de pruebas con una pérdida lineal en el número de consultas.
Ruta Entrópica: Si el testigo $W$ tiene una entropía mínima condicional promedio $\lambda$ dada la vista del SUT, la probabilidad de acierto de lista está acotada por $q \cdot 2^{-\lambda}$ . Esta ruta admite códigos de diagnóstico (por ejemplo, sufijos de hash truncados) donde los límites de cUP de la fuente pueden no aplicarse directamente.

3. Límite Inferior del Cono de Dependencia (Resultado Negativo)

El artículo demuestra una limitación fundamental de la certificación de caja negra (Teorema 5.37). Si una operación se encuentra fuera del cono de dependencia activo de soporte (support-active dependency cone) del objetivo observable de la confirmación (es decir, cambiar esa operación no cambia la transcripción observable ni la clave final en el soporte honesto), entonces ninguna prueba de referencia honesta de caja negra puede certificar su ejecución sobre una clase de implementación que contenga la correspondiente "erradicación" (una versión del código que omite la operación).

Para tales operaciones, los errores de solidez ( $\alpha$ ) y completitud ( $\beta$ ) de cualquier certificador satisfacen $\alpha + \beta \geq 1$ .
Esto implica que, sin instrumentación adicional, entradas malformadas o un conjunto de objetivos más amplio, las pruebas de caja negra no pueden distinguir entre la ejecución correcta y la erradicación de operaciones fuera del cono.

4. Instanciaciones y Artefacto

La teoría se instancia en dos familias:

ML-KEM (FIPS 203): Analiza la línea de código de confirmación de la fuente (usando coeficientes no comprimidos seleccionados) y una variante de artefacto de diagnóstico (ML-KEM-CD1) utilizando un código de hash de un byte.
HQC (Especificación de Agosto 2025): Analiza variantes de FO con sal que derivan el código de confirmación de la cola de truncamiento del criptograma. El artículo define HQC-TailEnt, un supuesto requerido para acotar el término de acierto de lista para estos códigos derivados de la cola.

Los autores proporcionan FO-FaultBench, un artefacto reproducible que contiene:

Líneas base fijadas (mlkem-native, HQC Agosto 2025).
Variantes transformadas (VSFO/CD1, CD*).
Catálogos de mutantes (fallos de vinculación, fallos de decisión, fallos simétricos).
Registros JSONL congelados de ejecuciones experimentales.

Resultados Experimentales

Las campañas del artefacto validan las afirmaciones teóricas:

Fallos de Vinculación (Binding Faults): Los fallos que omiten o sobrescriben el código de confirmación son detectados bajo pruebas de referencia honesta, ya que alteran la entrada de la clave final.
Fallos de Solo Decisión (Decision-Only Faults): Los fallos que solo afectan la selección de ramas (por ejemplo, seleccionar siempre la clave "buena") no son detectados bajo criptogramas honestos, pero sí bajo entornos malformados o diferenciales. Esto confirma la limitación de coincidencia de soporte.
Fallos Simétricos: Los fallos aplicados tanto a la encapsulación como a la desencapsulación pasan las pruebas de sí mismo pero fallan las pruebas de referencia honesta, demostando la necesidad del modelo de pares.
Acierto Probabilístico: Los mutantes que adivinan el código de confirmación pasan con una probabilidad que escala con la longitud del código retenido ( $2^{-L}$ ), coincidiendo con los límites de entropía teóricos.
Presupuestos de Rango: Los experimentos en variantes de HQC (CD1 vs. CD*) muestran que aumentar los bits de la cola retenida (de 5 a 37 bits) reduce significativamente la probabilidad de paso de los mutantes de adivinación, validando la ruta entrópica.

Significado y Reivindicaciones

El artículo afirma proporcionar una teoría formal de la prueba de códigos de confirmación que delinea precisamente lo que las pruebas de caja negra pueden y no pueden certificar para los KEMs basados en FO.

Reivindicaciones Positivas: El artículo establece que la vinculación del código de confirmación crea una señal detectable para los fallos de re-encriptación, siempre que el término de acierto de lista esté acotado por la cUP de la fuente o la entropía condicional. Ofrece un marco riguroso para interpretar los resultados de las pruebas como evidencia de clases de fallos específicas.
Reivindicaciones Negativas: El artículo establece explícitamente que las pruebas de referencia honesta de caja negra tienen límites inherentes. No pueden certificar operaciones fuera del cono de dependencia (por ejemplo, la ejecución completa de la re-encriptación si solo se vincula un subconjunto de coeficientes) sin cambiar el objetivo del entorno o añadir instrumentación.
Modestia: Los autores enfatizan que los teoremas de prueba son declaraciones clásicas del Modelo de Oráculo Aleatorio (ROM). No vuelven a probar la seguridad IND-CCA de los KEMs subyacentes, sino que se apoyan en los análisis de fuente citados para la seguridad a nivel de construcción. La "seguridad" de las líneas aumentadas es heredada de la fuente; la contribución del artículo es la señal de prueba y la interpretación de las probabilidades de paso bajo configuraciones de entorno específicas.

Este trabajo sirve como un puente entre los juegos de seguridad teóricos (cUP, fCOR) y las pruebas de implementación prácticas, proporcionando una "gramática de reclamos" para interpretar los resultados experimentales en implementaciones de KEM post-cuánticos.