The HyperFrog Cryptosystem: High-Genus Voxel Topology as a Trapdoor for Post-Quantum KEMs

A continuación presento un resumen técnico detallado del artículo "The HyperFrog Cryptosystem: Connected Graph Cycle Rank as a Structured Secret Distribution for an Experimental Post Quantum KEM", basado en la revisión v36.0 y el esquema de referencia v3.

1. El Problema y el Contexto

El criptosistema HyperFrog es un mecanismo de encapsulamiento de claves (KEM) experimental diseñado para la era post-cuántica. Su objetivo principal es explorar la viabilidad de utilizar distribuciones de secretos estructuradas basadas en topología de grafos dentro de un esquema de Aprendizaje con Errores (LWE) no estructurado.

• Desafío: La mayoría de los KEMs post-cuánticos estándar utilizan secretos binarios no estructurados o distribuciones gaussianas. HyperFrog intenta reemplazar esto con un secreto generado mediante un proceso de "minería" en una cuadrícula de voxels (cubos 3D), donde la estructura del secreto (conectividad y complejidad topológica) es parte integral de la ley de distribución.
• Riesgo: Las versiones anteriores del documento mezclaban conceptos informales (como "género" topológico) con implementaciones de ingeniería, lo que generaba ambigüedad sobre qué ley de distribución se estaba analizando formalmente y cuáles eran las garantías de seguridad.

2. Metodología y Diseño

La arquitectura de HyperFrog se divide en tres capas conceptuales:

A. Generador de Secretos (El "Miner")

Esta es la innovación central. En lugar de muestrear bits aleatorios independientes, el secreto se genera en una cuadrícula de 16 × 16 × 16 voxels (4096 posiciones).

• Proceso de Crecimiento de Frontera Conectada: El nuevo "minero formal" no rechaza muestras aleatorias. Comienza con un voxel semilla elegido uniformemente y crece añadiendo iterativamente voxels vecinos no ocupados elegidos al azar hasta alcanzar un peso exacto de 2048 voxels ocupados.
• Invariante Topológico: Se calcula el rango de ciclos del grafo ($\beta_1$) del grafo de adyacencia de seis vecinos de los voxels ocupados. La fórmula es $\beta_1 = E - V + C$ (donde $E$ son aristas, $V$ vértices y $C$ componentes conexas).
• Condicionamiento: El proceso solo acepta la forma si el rango de ciclos es mayor o igual a un umbral $\tau$ definido por el usuario.
• Separación Formal/Práctica: El código distingue explícitamente entre el Minero Formal (crecimiento de frontera, peso exacto, sin fallback) y el Minero Práctico (muestreo aleatorio con fallbacks para pruebas de ingeniería). El artículo solo hace afirmaciones formales sobre el minero formal.

B. Núcleo Algebraico (LWE)

• Estructura: Utiliza un LWE no estructurado con parámetros conservadores: $N=4096$, $M=2048$, módulo $q=2^{16}$ (65536).
• Clave Pública: Se deriva de una semilla de 32 bytes mediante un cifrador de flujo (ChaCha20) para expandir la matriz $A$.
• Ruido: Se utiliza una distribución binomial centrada.
• Transformación: Se aplica una transformación de estilo Fujisaki-Okamoto (FO) en el modelo de oráculo aleatorio para lograr seguridad contra ataques de texto cifrado elegido (CCA2).

C. Implementación y Benchmarking

• Tamaño de Cifrado: Intencionalmente grande (~2.10 MB) porque almacena un vector $u$ completo por cada bit de mensaje (256 bits).
• Desglose de Métricas: La metodología de benchmarking separa el tiempo de desbloqueo de clave secreta (derivación de contraseña con Argon2id) del tiempo de descifrado criptográfico (ruta del KEM), evitando confusiones en las mediciones de rendimiento.

3. Contribuciones Clave

1. Clarificación de la Ley de Distribución: Se redefine el secreto no como una distribución casi uniforme, sino como una ley estructurada y no uniforme definida por el crecimiento de frontera en grafos de voxels con peso exacto y rango de ciclos alto.
2. Corrección Terminológica: Se elimina el uso informal de "género" y se adopta rigurosamente el rango de ciclos del grafo ($\beta_1$) como la métrica topológica precisa.
3. Separación de Afirmaciones: Se establece una distinción estricta entre el modo de ingeniería (práctico) y el modo formal, asegurando que las afirmaciones de seguridad y los benchmarks se basen únicamente en el minero formal.
4. Metodología de Benchmark Transparente: Introducción de un esquema de referencia (v3) que reporta diagnósticos por muestra (éxito, tiempo, métricas de minería) y separa costos de desbloqueo de contraseñas de costos criptográficos.

4. Resultados Experimentales

El corpus de benchmarks (1670 muestras formales) arroja los siguientes hallazgos:

• Estabilidad del Minero: El minero formal generó 1670 muestras exitosas sin tiempos de espera (timeouts).
• Propiedades del Secreto:
  • Peso ocupado: Exactamente 2048 en el 100% de los casos.
  • Conectividad: 1 componente conexo en el 100% de los casos.
  • Rango de Ciclos ($\beta_1$): Osciló entre 2315 y 2856, con una media de 2687.3.
• Corrección: Todas las 1670 pruebas de descapsulación fueron exitosas (recuperación exacta de archivos).
• Rendimiento:
  • La encapsulación promedió ~25 ms y la descapsulación ~32 ms en configuraciones de 16 hilos.
  • El uso de 32 hilos introdujo sobrecarga en lugar de mejorar el rendimiento, indicando que la carga de trabajo es ligera para la gestión de hilos en este entorno.
  • Nota Importante: Los umbrales de rango de ciclos utilizados en las pruebas ($\tau \in \{6, 8, 10, 12\}$) son extremadamente bajos comparados con los valores observados (~2600). Por lo tanto, las pruebas actuales miden la estabilidad de la implementación, no la dificultad de aceptación de un umbral alto.

5. Significado y Limitaciones

• Significado: HyperFrog demuestra que es posible construir un KEM post-cuántico donde la estructura del secreto se define mediante propiedades topológicas de grafos discretos, manteniendo un núcleo algebraico conservador (LWE). Proporciona un marco transparente para estudiar cómo las correlaciones estructuradas en los secretos afectan la seguridad.
• Limitaciones y Advertencias:
  • Sin Reducción de Seguridad: No se afirma que la distribución de secretos estructurada sea tan segura como las distribuciones binarias estándar. La seguridad depende de la hipótesis de que el LWE sigue siendo duro para esta familia específica de secretos.
  • Ancho de Banda: El tamaño del cifrado (~2.1 MB) es prohibitivo para la mayoría de las aplicaciones prácticas actuales.
  • Calibración Pendiente: Los umbrales de prueba actuales no son lo suficientemente estrictos para probar la resistencia del minero bajo condiciones de rechazo estricto. Se necesita un estudio futuro para calibrar umbrales más altos.
  • Auditoría de Canales Laterales: Aunque se han mejorado las protecciones (código sin ramas), el sistema no ha sido auditado completamente contra canales laterales.

Conclusión: El documento presenta a HyperFrog no como un sistema listo para su despliegue, sino como una plataforma de investigación transparente y honesta. Su valor principal radica en la claridad con la que define su ley de secretos estructurados y separa las afirmaciones teóricas de las implementaciones de ingeniería, invitando a la comunidad criptográfica a analizar la seguridad de los secretos basados en grafos conectados.