HQC: incapsulamento chiave basato sui codici

17 Nov 2025

Introduzione

La conclusione del terzo round del processo di standardizzazione del NIST per la crittografia post-quantum avvenuta nel 2022, oltre alla selezione di uno schema di incapsulamento chiave (CRYSTALS-Kyber/ML-KEM) e di tre firme digitali (CRYSTALS-Dilithium/ML-DSA, Falcon/FN-DSA e SPHINCS+/SLH-DSA), ha avviato una quarta fase per la valutazione di un ulteriore metodo di incapsulamento chiave come alternativa a ML-KEM. Infatti, sebbene la comunità crittografica nutra fiducia nelle garanzie di sicurezza fornite da ML-KEM, le sue fondamenta sono relativamente giovani e non è escluso che le future ricerche in ambito crittanalitico ne riducano l’efficacia. Pertanto, pur identificando ML-KEM come scelta primaria, il NIST si è preoccupato di individuare un’alternativa che non sia basata sulle medesime assunzioni di sicurezza, legate alla teoria dei reticoli, e che possa agevolmente subentrargli in caso di necessità. In quest’ottica di diversificazione, il quarto round ha analizzato tre schemi basati sulla teoria dei codici (Classic McEliece, HQC e Bike) e uno schema basato sulle isogenie di curve ellittiche (SIKE). Essendo SIKE rivelatosi insicuro, il processo si è ristretto ai primi tre candidati e l’analisi si è conclusa il 5 marzo 2025 con la scelta del NIST dello schema Hamming Quasi-Cyclic (HQC).

Hamming Quasi-Cyclic

In questo articolo è affrontata una descrizione dello schema HQC, includendo gli elementi matematici e le assunzioni di sicurezza che lo caratterizzano [1]. L’ambiente matematico in cui vivono gli elementi coinvolti nello schema è $\mathcal{R}=\mathbb{F}_2[X]/(X^n-1)$ , ovvero l’insieme di tutti i polinomi in $X$ a coefficienti binari in cui vige la relazione $X^n=1$ . Dati due polinomi $\mathbf{p},\mathbf{q}\in\mathcal{R}$ , è importante notare che il loro prodotto $\mathbf{p}\cdot \mathbf{q}$ può essere rappresentato come il prodotto di una matrice circolante, indicata con $\mathbf{rot}(\mathbf{p})$ , per un vettore binari:

$\mathbf{p} \cdot \mathbf{q} \Leftrightarrow \mathbf{rot}(\mathbf{p})\begin{pmatrix} q_0 \\ q_1 \\ \vdots \\ q_{n-1} \end{pmatrix}= \begin{pmatrix} p_0 & p_{n-1} & \cdots & p_1 \\ p_1 & p_0 & \cdots & p_2 \\ \vdots & \vdots & \ddots & \vdots \\ p_{n-1} & p_{n-2} & \cdots & p_0 \end{pmatrix} \begin{pmatrix} q_0 \\ q_1 \\ \vdots \\ q_{n-1} \end{pmatrix},$

ove $p_i$ (risp. $q_i$ ) è il coefficiente binario del monomio $X^i$ in $\mathbf{p}$ (risp. $\mathbf{q}$ ).

Assunzione di sicurezza

La sicurezza dello schema HQC è basata sulla difficoltà di risolvere il problema Decisional Quasi-Cyclic Syndrome Deconding (DQCSD). Sia $\omega(\cdot)$ la funzione peso di Hamming [2] e sia $\mathcal{R}_{\omega}$ il sottoinsieme di $\mathcal{R}$ costituito da elementi con peso di Hamming [3] $\omega$ , DQCSD chiede di riuscire a distinguere due distribuzioni di probabilità così costruite:

Distribuzione QSCD: campiona in modo uniforme $\mathbf{h}\in\mathcal{R}$ e $\mathbf{x}=(\mathbf{x_0},\mathbf{x_1})\in\mathcal{R}_{\omega}^2$ (in notazione compatta $\mathbf{h}\leftarrow\mathcal{R}$ , $\mathbf{x}\leftarrow \mathcal{R}_{\omega}^2$ ) e restituisce la coppia $\left(\mathbf{h},(\mathbf{1}_n\,\,\mathbf{rot}(\mathbf{h}))\begin{pmatrix}\mathbf{x_0}\\\mathbf{x_1} \end{pmatrix}=\mathbf{x_0}+\mathbf{h}\cdot\mathbf{x_1}\right)\in \mathcal{R}\times\mathbb{F}_2^n$ ;
Distribuzione Uniforme: campiona in modo uniforme e restituisce la coppia $(\mathbf{h},\mathbf{y})\in\mathcal{R}\times\mathbb{F}_2^n$ .

Tale formulazione è di fatto un caso particolare [4] del più generale problema Syndrome Decoding (SD), ove il ruolo della matrice di parità è giocato da $H=(\mathbf{1}_n\,\,\mathbf{rot}(\mathbf{h}))$ . L’adozione di questa struttura permette di avere una dimensione della chiave pubblica più contenuta senza impattare significativamente sulla resistenza rispetto agli attacchi noti in letteratura.

HQC Public Key Encryption (PKE)

Analogamente a quanto accade per ML-KEM, il design dell’incapsulamento chiave in HQC parte da uno schema di cifratura a chiave pubblica a cui viene applicata una trasformata di Fujisaki-Okamoto [5]. Come accade per un generico schema di cifratura a chiave pubblica, HQC PKE si compone di tre algoritmi: generazione delle chiavi, cifratura e decifratura.

Generazione chiavi: la chiave privata $sk$ è costituita da $\mathbf{x}$ , $\mathbf{y}$ campionati in modo uniforme fra tutti i polinomi in $\mathcal{R}$ con peso di hamming $\omega$ . La chiave pubblica è data invece dalla coppia $(\mathbf{h}, \mathbf{s}=\mathbf{x}+\mathbf{h}\cdot \mathbf{y})$ , ove $\mathbf{h}$ è campionato uniformemente in $\mathcal{R}$ . L’impraticabilità di risalire dalla chiave pubblica a quella privata è garantita dalla difficoltà del problema DQCSD.
Cifratura di $m$ : per questioni di correttezza dello schema, il messaggio $m$ da cifrare viene prima codificato [6]. È bene evidenziare che il codice relativo a questa operazione non ha nulla a che vedere con il codice sottostante all’assunzione di sicurezza [7]. Dopo aver campionato uniformemente in $\mathcal{R}_{\omega}$ tre elementi $\mathbf{r_1}$ , $\mathbf{r_2}$ , $\mathbf{e}$ , il cifrato di $m$ è dato dalla coppia $(\mathbf{u}=\mathbf{r_1}+\mathbf{h}\cdot \mathbf{r_2},\mathbf{v}=\text{Encode}(m) + \mathbf{s}\cdot\mathbf{r_2}+\mathbf{e})$ .
Decifratura di $c$ : grazie alla conoscenza della chiave privata, il messaggio $m$ di partenza è ottenuto dalla decodifica (rispetto allo stesso codice usato in cifratura) di $\mathbf{v}-\mathbf{u}\cdot\mathbf{y}$ .

La correttezza della decifratura è garantita dalla seguente equazione.

$\begin{align*} \mathbf{v}-\mathbf{u}\cdot\mathbf{y} & = \text{Encode}(m)+\mathbf{s}\cdot \mathbf{r_2}+\mathbf{e}-\mathbf{u}\cdot\mathbf{y} \\ & = \text{Encode}(m)+\mathbf{s}\cdot \mathbf{r_2}+\mathbf{e}-\mathbf{r_1}\cdot\mathbf{y}-\mathbf{h}\cdot\mathbf{r_2}\cdot\mathbf{e} \\ & = \text{Encode}(m)+\underbrace{\mathbf{x}\cdot \mathbf{r_2}+\mathbf{e}-\mathbf{r_1}\cdot\mathbf{y}}_{\text{termine ``piccolo''}} \end{align*}$

Il termine aggiuntivo, dato da una somma di elementi di piccola dimensione, viene assorbito dal processo di decodifica. Elemento interessante da osservare è come la costruzione della chiave pubblica e del cifrato segua una struttura molto simile a quella degli schemi basati su LWE come ML-KEM. Infatti, entrambi coinvolgono la moltiplicazione di una matrice pubblica per un segreto e l’aggiunta di un rumore. Nonostante ciò, l’ambiente matematico di partenza è differente fra HQC e ML-KEM e questo è sufficiente ad avere per i due schemi assunzioni di sicurezza appartenenti a teorie matematiche distinte: quella dei codici e quella dei reticoli.

HQC Key Encapsulation Mechanism (KEM)

Gli algoritmi di generazione chiavi, incaspulamento e decapsulamento di HQC KEM poggiano su generazione chiavi, cifratura e decifratura di HQC PKE.

Generazione chiavi: l’algoritmo richiama la generazione chiavi di HQC PKE ed aggiunge il campionamento di un segreto $\sigma$ che entra in gioco in caso di fallimento in fase di decapsulamento.
Incapsulamento: un plaintext $m$ è campionato uniformemente. La chiave condivisa $K$ è ottenuta a partire da $m$ e dalla chiave pubblica tramite l’utilizzo di una funzione di hash $\textsf{H}$ . Successivamente, il messaggio $m$ è cifrato con HQC PKE e trasmesso.
Decapsulamento di $c$ : le fasi di decifratura, ricifratura e comparazione della trasformazione Fujisaki-Okamoto sono evidenziate in rosso. Si osserva che nel caso in cui il decapsulamento non dia esito positivo non viene restituito un messaggio d’errore ma una chiave random a partire dal segreto $\sigma$ . In questa eventualità, le due parti sono in possesso di due chiavi crittografiche distinte e la discrepanza viene rilevata solo in una fase di comunicazione successiva, si parla infatti di implicit rejection.

Performance

In questa sezione si conclude con il confronto dal punto di vista delle performance [8] di HQC con ML-KEM e la costruzione pre-quantum Elliptic Curve Diffie-Hellman (ECDH), relativamente a parametrizzazioni con medesimo target di sicurezza.

Rispetto a ECDH, a fronte di un costo computazionale paragonabile (fattore $\times2$ ), si osserva una maggiorazione consistente in termini di dimensione valori (fattore $\times 200$ ), in linea con le considerazioni che spesso emergono in merito alle sfide della transizione al post-quantum. Rispetto a ML-KEM, la dimensione dei valori da trasmettere ed il costo computazionale delle varie componenti risultano maggiorati rispettivamente di un fattore $\times4$ e $\times9$ . In effetti, uno dei maggiori punti di forza che ha permesso a ML-KEM di essere selezionato nel corso del terzo round è stato proprio quello delle ottime performance. Anche alla luce di questo aspetto, HQC viene considerato solo come alternativa di backup da implementare preventivamente nel caso che risultati crittanalitici catastrofici minino la sicurezza di ML-KEM.

[1] Come accaduto per altri articoli della presente rubrica, la trattazione è semplificata rispetto alla documentazione ufficiale per ragioni divulgative pur senza tralasciarne i concetti chiave.

[2] La funzione peso di Hamming applicata ad un vettore in $\mathbb{F}_2^n$ restituisce il numero delle sue entrate uguali a $1$ .

[3] La funzione peso di Hamming in questo caso è calcolata considerando il vettore costituito dai coefficienti del polinomio.

[4] Per completezza si evidenzia che il problema qui presentato è detto 2-DSQC, in HQC è necessario assumere anche la difficoltà di una sua estensione ovvero il 3-DSQC.

[5] Il razionale alla base di questa costruzione è il medesimo di ML-KEM e può essere approfondito nel relativo articolo.

[6] La codifica avviene in una concatenazione di un codice Reed-Muller con un codice Reed-Solomon che è nota pubblicamente.

[7] In sintesi in HQC intervengono due codici distinti, uno a garantirne la sicurezza ed un altro la correttezza.

[8] Performance di un’implementazione ottimizzata (AVX2) su processore Intel Xeon E-2124.

Questo articolo appartiene ad una serie di contributi, a cura del Gruppo di Ricerca in Crittografia di Telsy, dedicata al calcolo quantistico e alle sue implicazioni sulla Crittografia. Per la consultazione di altri articoli si rimanda all’indice della rubrica.

Per altri articoli relativi ai temi Quantum e Crittografia si rimanda alle relative categorie nel blog.

Gli autori

Francesco Stocco, laureato magistrale in Matematica presso l’Università degli Studi di Padova e l’Université de Bordeaux frequentando il percorso di studi “Algebra Geometry And Number Theory” (ALGANT), entrato a far parte del Gruppo di Ricerca in Crittografia di Telsy alla fine del 2020.