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

Ce manuscrit révisé présente HyperFrog, un mécanisme d'encapsulation de clés post-quantique expérimental dont la loi secrète est définie par un processus de croissance de frontière connectée sur une grille de voxels générant un rang cyclique de graphe spécifique, tout en clarifiant rigoureusement la séparation entre les revendications formelles et les modes d'implémentation pratiques.

L'essentiel

🐸 HyperFrog : Le Secret Caché dans un Labyrinthe de Cubes

Imaginez que vous essayez de créer un coffre-fort numérique inviolable pour l'ère des ordinateurs quantiques (ces futurs ordinateurs très puissants qui pourraient casser les codes actuels). C'est le but d'HyperFrog.

Ce papier de recherche ne propose pas un nouveau type de serrure magique, mais plutôt une nouvelle façon de fabriquer la clé qui ouvre cette serrure.

1. Le Problème : Une Clé Trop "Aléatoire"

Dans la plupart des systèmes de sécurité modernes, la clé secrète est comme une suite de pièces de monnaie lancées en l'air : pile ou face, au hasard total. C'est bien, mais les chercheurs pensent qu'on peut faire mieux en ajoutant une structure intelligente à cette clé.

2. La Solution : Construire un Château de Cubes (Le "Mineur")

Au lieu de lancer des pièces au hasard, HyperFrog utilise un processus appelé "Mineur" pour créer la clé.

• L'analogie du Lego : Imaginez un immense cube de Lego de 16x16x16 (4096 petits cubes au total).
• La règle d'or : Le système ne remplit pas tout le cube au hasard. Il commence par un seul cube, puis il ajoute un cube voisin à la fois, comme si on faisait grandir une tache d'encre ou une colonie de champignons.
• Le but : On s'arrête exactement quand on a utilisé 2048 cubes.
• La contrainte : Tous ces cubes doivent être collés les uns aux autres (un seul bloc connecté).

C'est là que ça devient intéressant. Le système vérifie ensuite une propriété mathématique de ce bloc de cubes : son "Cycle Rank" (ou rang cyclique).

• L'analogie du Labyrinthe : Imaginez que vos cubes forment un labyrinthe. Plus il y a de boucles, de passages en rond et de chemins qui reviennent sur eux-mêmes, plus le "Cycle Rank" est élevé.
• HyperFrog rejette les clés qui sont trop simples (comme un simple long couloir) et ne garde que celles qui forment des structures complexes et enchevêtrées, comme un nid d'abeille très dense.

3. La Nouvelle Version (Révision v36) : Plus d'Honnêteté

Le papier explique que les versions précédentes étaient un peu confuses. Elles mélangeaient deux choses :

1. Le Mineur "Officiel" (Formel) : Celui décrit ci-dessus, qui construit le bloc cube par cube pour garantir une structure parfaite. C'est celui qu'on utilise pour la sécurité théorique.
2. Le Mineur "Pratique" (Ingénierie) : Une version plus rapide et moins stricte utilisée pour tester le code, qui peut parfois faire des erreurs ou créer des formes moins parfaites.

Le grand changement de ce papier : Les auteurs disent clairement : "Arrêtez de confondre les deux !"

• Pour la sécurité, on utilise uniquement le Mineur Officiel (le constructeur de blocs parfait).
• Le Mineur Pratique est juste un outil pour les développeurs, comme un brouillon, et ne doit pas être utilisé pour prouver la sécurité.

4. Les Résultats : Ça marche, mais c'est lent (pour l'instant)

Les chercheurs ont testé leur système avec 1670 essais.

• Succès total : À chaque fois, ils ont réussi à créer un bloc de exactement 2048 cubes, tous connectés, avec un labyrinthe très complexe.
• La sécurité : Le système fonctionne très bien pour décrypter les messages (aucune erreur).
• Le bémol : Le système génère des clés très lourdes (environ 2 mégaoctets pour un seul message). C'est comme envoyer un camion pour livrer une lettre. C'est utile pour la recherche, mais pas encore prêt pour votre smartphone.

5. Pourquoi c'est important ?

Ce papier est une leçon d'honnêteté scientifique.

• Au lieu de dire "Notre système est parfait", ils disent : "Voici exactement comment nous fabriquons nos clés, voici ce qui est théorique et ce qui est pratique, et voici ce que nous savons et ce que nous ignorons encore."
• Ils ne prétendent pas avoir résolu tous les problèmes de sécurité, mais ils ont créé un laboratoire transparent où d'autres chercheurs peuvent venir tester si cette méthode de "clé en forme de labyrinthe" résiste aux attaques.

En résumé

HyperFrog, c'est comme si on arrêtait de choisir une clé au hasard dans un tiroir, et qu'on se mettait à sculpter une clé en argile avec des règles très strictes (elle doit avoir un certain poids, être d'une seule pièce, et avoir beaucoup de trous complexes).

Ce papier nous dit : "Regardez comme nous sculptons cette argile. C'est propre, c'est précis, et nous avons séparé le vrai travail d'art de nos brouillons de test. Maintenant, à vous de voir si cette clé est vraiment incassable."

Résumé technique

1. Problème et Contexte

Le cryptage post-quantique a vu l'émergence de mécanismes d'encapsulation de clés (KEM) matures basés sur des problèmes de réseaux (Lattice), de codes ou d'isogénies. Cependant, il reste scientifiquement pertinent d'explorer des constructions expérimentales qui modifient une seule composante de la conception pour en étudier les propriétés.

Le problème central abordé par HyperFrog est la définition d'une distribution de secret structurée au sein d'un schéma LWE (Learning With Errors) non structuré. Contrairement aux KEM standards qui utilisent des secrets binaires non contraints, HyperFrog cherche à générer un secret binaire qui possède des propriétés topologiques spécifiques (un grand « rang de cycle ») tout en restant compatible avec la sécurité LWE.

Les versions précédentes du projet souffraient d'ambiguïtés terminologiques (confusion entre « genre » topologique et rang de cycle de graphe) et d'une séparation floue entre les modes de génération de secrets « formels » (théoriques) et « pratiques » (ingénierie), ce qui rendait les revendications de sécurité imprécises.

2. Méthodologie

La révision (alignée sur la version v36.0 et le schéma de benchmark v3) propose une refonte complète de la méthodologie pour clarifier la loi de distribution du secret et les métriques de performance.

A. Modèle Mathématique et Générateur de Secret

• Grille Voxel : Le secret est défini comme un champ d'occupation binaire sur une grille $16 \times 16 \times 16$ (4096 voxels).
• Invariant Topologique : L'invariant clé n'est plus le « genre » d'une surface, mais le rang de cycle du graphe ($\beta_1$) du graphe d'adjacence à six voisins des voxels occupés. La formule est $\beta_1 = |E| - |V| + C$, où $|E|$ est le nombre d'arêtes, $|V|$ le nombre de sommets et $C$ le nombre de composantes connexes.
• Mineur Formel (Frontière Connexe) : Au lieu d'un échantillonnage aléatoire suivi d'un rejet, le mineur formel utilise un processus de croissance de frontière connectée :
  1. Un voxel de départ est choisi uniformément.
  2. Des voxels de la frontière (voisins non occupés) sont ajoutés un par un de manière aléatoire.
  3. Le processus s'arrête exactement lorsque le poids occupé atteint 2048 voxels.
  4. La forme résultante est acceptée uniquement si son rang de cycle $\beta_1$ dépasse un seuil $\tau$ fourni par l'utilisateur.
  • Garantie : La connectivité est assurée par construction, et le poids est exactement 2048.

B. Cœur Cryptographique (LWE)

• Paramètres : $N=4096$ (taille du vecteur secret), $M=2048$ (lignes de la matrice publique), $q=2^{16}$, et $k=256$ bits encapsulés.
• Structure : Le secret $s$ est binaire. La matrice publique $A$ est générée de manière déterministe à partir d'une graine via ChaCha20. Le vecteur public $b$ est calculé comme $b = As + e \pmod q$, où $e$ est un bruit binomial centré.
• Transformation de Sécurité : Le schéma utilise une transformation de style Fujisaki-Okamoto (FO) dans le modèle d'oracle aléatoire pour atteindre la sécurité contre les attaques à texte chiffré choisi (CCA2).
• Chiffrage de Fichiers : Un KEM partagé est dérivé, puis utilisé pour générer une clé AES-256-GCM. Le système distingue clairement le temps de déverrouillage de la clé secrète (via Argon2id si protégé par mot de passe) du temps de déchiffrement cryptographique.

C. Séparation Formel vs Pratique

Le code distingue explicitement deux modes :

• Mineur Formel : Respecte strictement la loi de croissance connectée et le poids exact. C'est le seul mode soumis aux revendications théoriques.
• Mineur Pratique : Utilise un échantillonnage par rejet sur un bitset aléatoire avec des fallbacks déterministes. Il est réservé aux tests d'ingénierie et exclu des affirmations de sécurité formelles.

3. Contributions Clés

1. Clarification de la Loi de Secret : Remplacement d'un échantillonnage par rejet faible par un processus de croissance connectée explicite, garantissant un poids exact et une connectivité.
2. Séparation Rigoureuse : Distinction nette entre les revendications formelles (basées sur le mineur formel) et les modes d'ingénierie, évitant les confusions dans l'analyse de sécurité.
3. Méthodologie de Benchmark Transparente : Introduction d'un schéma de benchmark (v3) qui décompose les temps d'exécution en :
   • Temps de déverrouillage de la clé secrète (coût Argon2id).
   • Temps de déchiffrement cryptographique pur.
   • Temps total.
   • Diagnostics de correction de décapsulation et statistiques de minage par échantillon.
4. Correction Terminologique : Adoption stricte du terme « rang de cycle de graphe » ($\beta_1$) à la place de « genre », alignant le texte sur la réalité mathématique du code.

4. Résultats Expérimentaux

Les résultats sont basés sur un corpus de 1670 échantillons générés via le mineur formel :

• Stabilité du Mineur :
  • 1670/1670 succès de génération de clés.
  • Poids occupé exactement 2048 pour chaque échantillon.
  • Une seule composante connexe pour chaque échantillon.
  • Rang de cycle observé : Moyenne de 2687,3 (intervalle 2315 à 2856), bien au-dessus des seuils de test ($\tau \in \{6, 8, 10, 12\}$).
• Performance KEM :
  • Encapsulation moyenne : ~25 ms (sur 16 threads).
  • Décapsulation moyenne : ~32 ms (plus lente due à la re-vérification et la validation constante).
  • Le passage à 32 threads n'améliore pas les performances (surcharge de gestion des threads).
• Comparaison Formel vs Pratique :
  • Le mineur pratique produit des poids variables (2030) et des rangs de cycle beaucoup plus faibles (1000), confirmant qu'il ne peut pas remplacer le mineur formel pour l'analyse de sécurité.
• Analyse de Latence Fichier :
  • Le coût dominant pour le déchiffrement de fichiers est le déverrouillage de la clé secrète (Argon2id), et non le déchiffrement cryptographique AES-GCM.
• Limites des Benchmarks : Les seuils de cycle rank testés sont trop faibles par rapport aux valeurs observées, et les budgets de temps trop généreux. Les résultats actuels prouvent la stabilité de l'implémentation, mais ne constituent pas une étude de calibration de la probabilité d'acceptation dans un régime difficile.

5. Signification et Limites

Signification :
HyperFrog se positionne comme une plateforme de recherche transparente et honnête. En séparant clairement la loi de distribution structurée du cœur LWE, l'article permet aux chercheurs d'analyser spécifiquement l'impact des contraintes topologiques (connectivité, poids exact, rang de cycle) sur la sécurité LWE. La méthodologie de benchmark rigoureuse offre un modèle pour évaluer les coûts réels des KEM post-quantiques, y compris les coûts de gestion des clés.

Limites et Problèmes Ouverts :

• Réduction de Sécurité : Aucune réduction n'est prouvée reliant la difficulté du LWE avec cette famille de secrets structurés à la difficulté du LWE standard. C'est la principale question cryptanalytique ouverte.
• Taille des Chiffres : Le texte chiffré est volumineux (~2,1 Mo) car il stocke un vecteur $u$ complet par bit de message. Ce n'est pas optimisé pour le déploiement pratique.
• Calibration : Les seuils de cycle rank utilisés dans les benchmarks ne sont pas assez élevés pour tester les limites de la difficulté de génération.
• Audit de Canal Latéral : L'implémentation n'a pas encore fait l'objet d'un audit complet de canaux latéraux, bien que des améliorations (calculs sans branche) aient été apportées.

En conclusion, ce manuscrit ne prétend pas offrir un système de production, mais fournit une construction expérimentale corrigée, dont les hypothèses et les comportements empiriques sont décrits avec une précision sans précédent, ouvrant la voie à une analyse cryptanalytique ciblée des secrets structurés par graphes.