FALCON · FN-DSA

La familia SHA-3 (FIPS 202) se basa en la permutación Keccak y su construcción esponja: el estado interno de 1600 bits absorbe bloques del mensaje y luego se exprime para producir la salida. Las variantes SHAKE128/256 son funciones de salida extensible (XOF): producen tantos bytes como se pidan. En FALCON el mensaje no se firma directamente: HashToPoint lo convierte en un polinomio del anillo de trabajo:

1. Absorción de la sal y el mensaje. Se absorben en SHAKE-256 la sal r (40 bytes) y el mensaje m. La sal hace que dos ejecuciones sobre el mismo mensaje produzcan polinomios distintos.
   Sal r utilizada (40 bytes, hex)
2. Exprimido por bloques. Se extraen bloques de 2 bytes del estado, interpretados como enteros de 16 bits (0 … 65535).
   Salida de SHAKE-256 como enteros de 16 bits ( valores, 0 … 65 535) ⧉ Copiar
3. Muestreo por rechazo. Se descartan los valores ≥ k·q (k = 5, k·q = 61 445) para que, tras reducir mod q, la distribución sea uniforme en ℤq y el polinomio no tenga sesgos explotables.
   Valores no descartados ( valores < k·q = 61 445, antes de reducir mod q) ⧉ Copiar
4. Construcción del polinomio. Cada valor aceptado se reduce mod q y ocupa un coeficiente, hasta completar los n coeficientes de c. Este polinomio es lo que realmente se firma en FALCON.
   Coeficientes de c (n = , enteros en [0, q−1], q = 12 289) ⧉ Copiar

La clave privada de FALCON es una base corta de un retículo NTRU; la clave pública es una base «mala» (larga) del mismo retículo. Conocer la base corta permite resolver problemas que con la base pública son intratables: esa asimetría es la trampilla (trapdoor) del esquema. Recuperar (f, g) a partir de h es el problema de recuperación de clave NTRU, considerado difícil incluso para algoritmos cuánticos.

1. Polinomios cortos f y g. Se muestrean con coeficientes gaussianos discretos pequeños (y se reintenta si f no es invertible o la calidad de la base resultante es mala). Observa que sus coeficientes son diminutos comparados con q.
   f

   g
2. Ecuación NTRU. Se calculan F, G que completan la base del retículo: f·G − g·F = q  (mod xⁿ+1) Es la operación más costosa de todo el esquema (se resuelve recursivamente por mitades).
   F

   G
3. Cálculo de la FFT de f, g, F, G. Los cuatro polinomios se llevan al dominio FFT (evaluación en las raíces complejas de xⁿ+1), donde las multiplicaciones de polinomios se convierten en productos coeficiente a coeficiente. Con esta representación se forma la base secreta B₀ = [[g, −f], [G, −F]] usada en el paso siguiente.
   FFT(f)

   FFT(g)

   FFT(F)

   FFT(G)
4. Cálculo del árbol LDL. Sobre la base B₀ se calcula la matriz de Gram G₀ = B₀·B₀* y se factoriza recursivamente (descomposición LDL* en el dominio FFT). El árbol resultante se normaliza con σ y acelerará el muestreo gaussiano al firmar.
   Árbol T normalizado (descomposición LDL*) — explora sus nodos y valores G₀ = B₀·B₀* = L·D·L*

   El árbol se construye factorizando la matriz de Gram de la base secreta en el dominio FFT y dividiendo recursivamente cada polinomio en dos mitades (de ahí su forma binaria). Cada nodo interno guarda el polinomio ℓ de la factorización L·D·L* de su nivel (coeficientes complejos, mostrados como a±bi); tras la normalización, cada hoja guarda el valor σ/‖b̃ᵢ‖: la desviación típica con la que ffSampling muestreará sobre el vector de Gram-Schmidt b̃ᵢ al firmar. El árbol forma parte de la clave privada extendida y nunca se publica.

5. Clave privada. La clave privada serializa los cuatro polinomios (f, g, F, G) a 14 bits por coeficiente; junto con el árbol T forma la clave privada extendida que se usa al firmar.
   Clave privada sk = (f, g, F, G) ·

   Hex Binario Base64

   ⧉ Copiar

   En un sistema real la clave privada jamás se muestra ni sale del dispositivo; aquí se expone con fines didácticos.

6. Cálculo de la clave pública. Es el cociente de los polinomios cortos: h = g · f⁻¹ (mod xⁿ+1, q) serializado a 14 bits por coeficiente. A diferencia de f y g, h parece aleatorio en [0, q−1]: es la base «mala» que no revela la trampilla.
   h = g·f⁻¹ mod q (coeficientes)

   Clave pública vk (h serializado) ·

   Hex Binario Base64

   ⧉ Copiar

FALCON sigue el paradigma GPV: firmar es encontrar una preimagen corta del hash del mensaje usando la base secreta del retículo. Firma dos veces el mismo mensaje y observa que la sal, s₀ y s₁ cambian: la firma es probabilística.

1. Sal y reto. Se genera una sal aleatoria r de 40 bytes y se calcula el polinomio reto c = HashToPoint(r ‖ m) (etapa 1).
   Sal r (40 B, hex)

   c = HashToPoint(r ‖ m)
2. Cálculo de la preimagen. El reto se expresa en coordenadas de la base secreta: en el dominio FFT se calcula la solución exacta (no entera) t = (t₀, t₁) = (FFT(c), FFT(0))·B̂₀⁻¹ con t₀ = FFT(c)⊙FFT(−F)/q y t₁ = FFT(c)⊙FFT(f)/q. Cualquier redondeo entero de t dará un punto del retículo cercano al reto.
   t₀ (dominio FFT, complejos)

   t₁ (dominio FFT, complejos)
3. Muestreo de la preimagen con el árbol T. Con el árbol T normalizado se ejecuta ffSampling (muestreo gaussiano rápido tipo Fourier): recorre el árbol y redondea cada coordenada de t con gaussianas discretas, produciendo un vector entero z = (z₀, z₁) cercano a t. La distribución gaussiana garantiza que la firma no filtra información de la base secreta.
   z₀ = ffSampling(t₀, T) (dominio FFT)

   z₁ = ffSampling(t₁, T) (dominio FFT)
4. Cálculo de s (dominio FFT). La diferencia entre la preimagen exacta y el punto entero muestreado se lleva de vuelta a coordenadas del anillo: ŝ = (t̂ − ẑ)·B̂₀ s es corto precisamente porque z está cerca de t.
   ŝ₀ (dominio FFT, complejos)

   ŝ₁ (dominio FFT, complejos)
5. Comprobación de la norma. La firma solo es válida si es suficientemente corta: ‖s₀‖² + ‖s₁‖² ≤ β² Si la cota no se cumple, se vuelve a muestrear (puede ocurrir varias veces).
   Norma ‖(s₀,s₁)‖²

   Cota β²
6. Cálculo de la FFT inversa de s. Al volver al dominio de coeficientes se obtienen los polinomios enteros (s₀, s₁) = invFFT(ŝ), que cumplen: s₀ + s₁·h ≡ c (mod q) Sus coeficientes son pequeños comparados con q = 12 289: por eso la firma es «corta».
   s₁ (se enviará comprimido en la firma)

   s₀ (no se envía; el verificador lo reconstruye)
7. Compresión y ensamblado. Se comprime s₁ (codificación de tipo Golomb–Rice) y se emite la firma final; s₀ no se envía porque el verificador puede recalcularlo: firma = header ‖ r ‖ comp(s₁)

   Header:

   Firma completa

   Hex Binario Base64

   ⧉ Copiar

La verificación solo usa información pública (mensaje, firma y clave pública h) y es mucho más rápida que la firma. Sin la base secreta, encontrar un (s₀, s₁) corto que cumpla la ecuación equivale a resolver el problema SIS sobre el retículo NTRU.

1. Desensamblado de la firma. Se separa la firma recibida en sus tres campos: firma = header ‖ r ‖ comp(s₁) El header codifica el grado n; la sal r ocupa 40 bytes y el resto es s₁ comprimido.

   Header:

   Sal r extraída de la firma (hex)

   comp(s₁) extraído de la firma (hex)
2. Sal y reto. Con la sal r extraída y el mensaje recibido m se recalcula el reto c = HashToPoint(r ‖ m). Si el mensaje fue alterado en un solo bit, c cambia por completo.
   c recalculado
3. Descompresión de s₁. Se decodifica comp(s₁) (codificación de tipo Golomb–Rice) para recuperar los coeficientes enteros de s₁. Si la codificación es inválida, la firma se rechaza ya en este paso.
   s₁ descomprimido
4. Reconstrucción de s₀. Usando solo la clave pública: s₀ = c − s₁·h (mod q) con coeficientes centrados en (−q/2, q/2]. Con una firma legítima, s₀ es pequeño; con un mensaje alterado, sus coeficientes se disparan.
   s₀ reconstruido
5. Decisión por la norma. Se acepta la firma si y solo si el vector es corto: ‖s₀‖² + ‖s₁‖² ≤ β²
   Norma calculada ‖(s₀,s₁)‖²

   Cota máxima β²