FALCON expliqué mathématiquement

1. De quoi il s'agit

Un avis publié sur McGesund n'est pas un simple champ de texte dans une base de données qu'il faudrait croire sur parole. Il est signé numériquement au moment de son envoi, et chaque visiteur peut ensuite recalculer cette signature dans son propre navigateur.

Pour une partie de ces signatures, nous utilisons FALCON — plus précisément FN-DSA-512 et FN-DSA-1024. Cet article explique ce qui se passe alors sur le plan mathématique.

Un point important d'emblée :

FALCON n'est pas un chiffrement. Le texte de l'avis est justement fait pour être lu. FALCON ne prouve pas la confidentialité, mais l'origine et l'intégrité.

---

2. Ce qui est signé exactement

Ce n'est pas le texte courant qui est signé, mais un objet de données compact qui fixe le texte sans ambiguïté :

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<ID de l'entreprise>",
  "c":   "<ID de l'avis>",
  "h":   "<SHA-256 du texte de l'avis>",
  "rh":  "<SHA-256 de l'ensemble du jeu de données soumis>",
  "rv":  1,
  "qh":  "<SHA-256 de l'enveloppe QR, uniquement pour les avis par QR>",
  "iat": 1757203200
}

C'est notre message $m$. Il lie ensemble :

1. à quelle entreprise l'avis se rapporte (f),
2. de quel avis il s'agit (c),
3. quel texte se trouvait derrière — sous forme de condensé (h),
4. quel jeu de données a été soumis dans son ensemble (rh) : texte, cœurs, statut géographique et indications de motif, sérialisés de façon canonique puis hachés, dans la version de schéma rv,
5. de quel QR code provient l'avis (qh) — pour un avis sans QR, le champ disparaît,
6. quand la signature a été apposée (iat).

Un seul caractère modifié dans le texte de l'avis brise cette chaîne. C'est précisément le but — et depuis rh, il en va de même pour un cœur déplacé après coup ou un statut géographique modifié.

---

3. Le problème de fond

Un lecteur qui arrive sur le profil d'une entreprise se pose deux questions :

1. Cet avis provient-il réellement du système McGesund ?
2. A-t-il été modifié après coup ?

Pour cela, il existe une paire de clés :

• une clé privée — elle reste dans le service de signature
• une clé publique — tout le monde peut l'avoir

La signature se fait avec la clé privée, la vérification avec la clé publique. Et ce sur l'appareil du lecteur, pas sur notre serveur.

---

4. Pourquoi FALCON ?

Beaucoup de procédés de signature actuels reposent sur des problèmes difficiles pour les ordinateurs classiques, mais qui pourraient devenir nettement plus faciles pour des ordinateurs quantiques suffisamment grands.

Pour un avis, cela compte davantage que pour un message éphémère : un avis doit encore être vérifiable dans cinq ou dix ans. Qui signe aujourd'hui signe pour toute la durée de vie de l'entrée.

FALCON repose donc sur la cryptographie fondée sur les réseaux euclidiens :

On construit un réseau facile à décrire mathématiquement, dans lequel une certaine tâche de recherche est extrêmement difficile.

---

5. Qu'est-ce qu'un réseau euclidien ?

Deux vecteurs :

Toutes les combinaisons à coefficients entiers

forment un réseau de points. Par exemple :

L'essentiel est ceci :

Le réseau lui-même est facile à décrire. Y trouver certaines propriétés est très difficile.

---

6. Le secret, ce sont les vecteurs courts

La tâche difficile classique s'énonce ainsi :

C'est le Shortest Vector Problem, le problème du vecteur le plus court. En dimension deux, on peut le résoudre par essais successifs. FALCON travaille en dimension 512 ou 1024 — là, c'est sans espoir.

FALCON n'a toutefois pas besoin du plus court vecteur en soi, mais de quelque chose d'apparenté : trouver, pour un point cible donné, un point du réseau qui en soit proche. Là encore, c'est difficile sans la bonne information complémentaire.

---

7. Des polynômes plutôt que des nombres

FALCON utilise un réseau NTRU et calcule avec des polynômes. Donc avec des listes de coefficients plutôt qu'avec des nombres isolés :

Les calculs se font dans l'anneau

Cela signifie :

• $\mathbb{Z}_q$ : calcul modulo $q$. Pour $q=7$ par exemple, $10\equiv3$, car $10-7=3$.
• $x^n=-1$ : maintient les polynômes à une longueur fixe.

FALCON utilise concrètement :

---

8. L'astuce centrale

La clé privée est constituée de quatre petits polynômes

vérifiant l'équation NTRU

Ces quatre-là forment ensemble une base secrète et bien conditionnée du réseau — une description du réseau à partir de vecteurs courts.

La clé publique est pour l'essentiel un unique polynôme :

De $h$ découle le même réseau, mais dans une base peu maniable faite de vecteurs longs :

C'est là tout le cœur de FALCON. Les deux bases décrivent le même réseau. Simplement, l'une est utilisable pour calculer et l'autre non.

On peut se le représenter comme un plan de ville : la carte complète est publique. Ce qui est secret, c'est la connaissance des raccourcis.

---

9. L'avis devient un point

Avant la signature, l'objet payload passe par une fonction de hachage. FALCON emploie pour cela Hash-to-Point : du message on ne tire pas une valeur numérique, mais directement un point de l'anneau.

Le service de signature tire en outre un sel aléatoire $r$ (320 bits) et le hache avec le reste :

Le sel n'est pas un accessoire. Sans lui, un même avis donnerait toujours la même signature, et de nombreuses signatures permettraient de reconstruire la base secrète. Il voyage donc avec la signature.

---

10. Ce qu'est une signature valide

On cherche un couple

possédant deux propriétés :

La première condition seule est triviale à satisfaire — il suffit de poser $s_2=0$ et $s_1=c$. C'est la seconde condition qui rend la tâche difficile.

---

11. Un mini-exemple entièrement calculé

Nous réduisons tout à une taille de jouet : des polynômes à un seul coefficient, donc des nombres ordinaires, et

La clé secrète. Deux petits nombres :

La clé publique. On a $3^{-1}\equiv65 \pmod{97}$, car $3\cdot65=195=2\cdot97+1$. Donc :

Le réseau. $L=\{(s_1,s_2): s_1+34\,s_2\equiv0 \pmod{97}\}$.

La base publique découle directement de $h$ :

Les deux appartiennent à $L$ — et les deux sont longs.

La base secrète n'est connue que du service de signature :

car $-5+34\cdot3=97\equiv0$ et $-9+34\cdot(-14)=-485=-5\cdot97\equiv0$. Le déterminant vaut

l'équation NTRU est donc satisfaite. Les deux vecteurs sont courts.

---

Étape 1 : hacher l'avis

Supposons que l'objet payload de l'avis donne

Étape 2 : une première solution, mauvaise

vérifie $71+34\cdot0=71\equiv c$. Mais la longueur vaut $71$ — bien trop long.

Étape 3 : raccourcir grâce à la base secrète

Le service de signature exprime le point cible dans sa base courte :

Cela conduit à $a\approx-10{,}25$ et $b\approx-2{,}20$. Arrondis à $a=-10$ et $b=-2$, on obtient le point du réseau

Contrôle : $68+34\cdot(-2)=68-68=0$, il appartient donc bien à $L$. On soustrait :

Longueur :

Voilà la signature.

Étape 4 : le même procédé avec la base publique

Qui ne connaît que $h=34$ dispose de la base $\{(97,0),(-34,1)\}$. Le même calcul d'arrondi y donne le point de réseau $(97,0)$, et donc

C'est également une solution valide de l'équation — mais sept fois plus longue. Si la borne d'acceptation est fixée en dessous de 26, elle ne vaut rien.

C'est la trappe de FALCON en une ligne.

Étape 5 : le navigateur vérifie

Le navigateur reçoit l'avis, le sel et $s_2=2$. Il recalcule le condensé, obtient $c=71$, reconstruit

et vérifie la longueur :

Étape 6 : quelqu'un modifie le texte de l'avis

Si le texte est modifié après coup, le condensé du contenu change, et avec lui le point — disons

L'ancienne signature reste $(3,2)$, mais

Nous pouvons supprimer un avis. Nous ne pouvons pas le modifier sans que cela se voie.

Précision de transparence sur l'exemple

En dimension deux, un attaquant peut simplement essayer les solutions courtes une à une — pour $c'=40$, par exemple $(6,1)$. Cet exemple n'est pas sûr ; il ne montre que le mécanisme. Avec FALCON-1024, le vecteur compte 2048 coefficients, et là, les essais successifs ne mènent nulle part.

---

12. Pourquoi ne pas simplement arrondir ?

Le procédé de l'étape 3 s'appelle l'arrondi de Babai. Pour un exemple pédagogique, il suffit — pour un véritable procédé de signature, non.

La raison : les signatures arrondies ne sont pas réparties uniformément. Leur forme dépend de la géométrie de la base secrète. À partir d'un nombre suffisant de signatures, cette géométrie se laisserait reconstruire — et avec elle la clé privée. C'est exactement là-dessus que des procédés de signature antérieurs fondés sur les réseaux ont échoué.

FALCON tire donc les vecteurs courts selon une loi gaussienne discrète sur le réseau :

Les valeurs proches du point cible sont plus probables, mais laquelle est retenue exactement reste aléatoire. Le résultat est une distribution qui ne révèle rien de la base utilisée — mathématiquement : elle est indistinguable d'une distribution ne dépendant que du réseau lui-même.

Cet échantillonneur est la partie la plus exigeante de FALCON. Il procède récursivement sur une structure arborescente et travaille avec des nombres à virgule flottante — ce qui rend l'implémentation délicate et explique avant tout que FALCON soit plus difficile à mettre en œuvre correctement que ML-DSA.

---

13. Ce qui est réellement transmis

La signature est constituée de

Seulement $s_2$ — pas le couple. Le vérificateur calcule $s_1$ lui-même :

Comme les coefficients de $s_2$ sont petits et dispersés autour de zéro, ils se compressent fortement. C'est la raison des signatures remarquablement compactes de FALCON :

À titre de comparaison : ML-DSA-87 demande 4 627 octets. Chez McGesund, aucune de ces signatures ne se trouve toutefois dans le QR code lui-même — l'autocollant ne porte que l'enveloppe Ed25519 ; les sceaux post-quantiques sont stockés auprès du jeu de données et chargés au moment de la vérification. Ici, la taille ne décide donc pas de l'imprimabilité, mais du stockage et de la transmission : un sceau FALCON occupe environ un quart d'un sceau ML-DSA.

---

14. Pourquoi FALCON vérifie vite

La multiplication de polynômes coûte, en version naïve,

Avec la transformation de Fourier rapide, cela descend à environ

Pour $n=1024$, c'est la différence entre un million et environ dix mille opérations. C'est pourquoi la vérification s'exécute en quelques millisecondes dans le navigateur d'un visiteur — et c'est aussi pourquoi le F figure dans le nom :

FAst Fourier Lattice-based COmpact signatures over NTRU.

---

15. Le déroulement en image

---

16. Pourquoi un attaquant échoue

Il connaît $h$ et donc l'ensemble du réseau. Il connaît aussi le point cible $c$ dès que l'avis est public. Ce qui lui manque, c'est la base courte.

Pour falsifier un avis, il devrait trouver, pour un $c$ choisi par lui-même, un vecteur court — à partir de la seule description publique. C'est la tâche qu'a illustrée l'étape 4 de l'exemple : sans les bons vecteurs, le même calcul aboutit à une solution beaucoup trop longue.

En dimension 1024, les meilleures méthodes connues — classiques comme quantiques — en sont très loin.

---

17. Ce que McGesund en fait concrètement

L'enveloppe. Chaque avis signé porte une signature Ed25519. C'est la variante obligatoire — classique, très petite, vérifiable nativement dans tous les navigateurs.

Les sceaux post-quantiques. À côté viennent une ou deux signatures résistantes au quantique. Lesquelles, cela dépend de la formule tarifaire :

La variante parallèle est délibérément redondante. FALCON repose sur les réseaux NTRU, ML-DSA sur les réseaux modulaires. Si l'une des deux familles s'avérait plus faible qu'on ne le suppose aujourd'hui, l'autre continuerait de porter.

L'ancrage temporel. L'empreinte de la clé de signature est ancrée dans un bloc Bitcoin via OpenTimestamps. Il est ainsi démontré non seulement que la signature est authentique, mais aussi qu'elle existait déjà à un instant donné — sans que quiconque ait à croire notre horodatage.

Tout cela est calculé dans le navigateur du lecteur, via un module WASM. Nous fournissons les données ; la vérification s'exécute sur l'appareil du visiteur. Si nous quittions le réseau demain, un avis une fois chargé resterait vérifiable.

Pour situer les noms : FALCON est actuellement en cours de normalisation sous le nom FN-DSA ; le projet est prévu comme FIPS 206, mais n'est pas encore finalisé. C'est pourquoi les niveaux s'appellent FN-DSA-512 et FN-DSA-1024 dans le code de McGesund, même si l'usage courant continue de parler de FALCON.

---

18. L'intuition essentielle

La clé publique est la description complète d'un labyrinthe. Chacun peut la consulter.

La signature est la preuve : « J'ai trouvé un chemin très court pour exactement cet avis. »

La clé privée est la connaissance des raccourcis.

Le lecteur n'a pas besoin de connaître les raccourcis. Il se contente de mesurer si le chemin présenté est effectivement court et s'il correspond effectivement à cet avis. Il peut faire les deux sans nous.

Qui modifie le texte déplace le point — et l'ancien chemin ne mène plus nulle part.