CRYSTALS-Kyber: incapsulamento chiave basato su LWE

08 Mag

Nel contesto del processo di standardizzazione del NIST per l’individuazione e l’analisi di soluzioni di Post-Quantum Cryptography (PQC), il primo esito cruciale è rappresentato dalla selezione del meccanismo di incapsulamento chiave (KEM) CRYSTALS-Kyber.

Kyber è uno schema crittografico a chiave pubblica che consente a due parti di derivare un segreto comune con cui proteggere lo scambio di informazione.

Le principali caratteristiche, che hanno consentito a Kyber di essere selezionato come soluzione primaria nell’ambito dei KEM fra le 45 proposte NIST iniziali, vanno ricercate nell’efficienza e nella sicurezza garantita di fronte ai migliori attacchi classici e quantistici noti in letteratura.

All’interno degli attuali protocolli crittografici, Kyber andrà a sostituire le tecniche di scambio chiave crittografiche basate su problemi vulnerabili al quantum computing come il diffusissimo ECDH, scambio chiave Diffie Hellman costruito su curve ellittiche.

CRYSTALS-Kyber

Ai fini di comprendere il razionale dietro al design di Kyber, è opportuno procedere per passi.
Il punto di partenza è lo schema di cifratura basato su LWE , il secondo passo è un’estensione a Module-LWE mentre l’ultimo è una trasformazione da schema di cifratura a meccanismo di incapsulamento chiave.

Prima di affrontare la trattazione, è utile fissare alcune notazioni.

$q$ è un numero primo
$\mathbb{Z}_q$ indica l’insieme $\{0,\dots,q-1\}$
$R_q=\mathbb{Z}_q[X]/(X^n+1)$ indica l’insieme dei polinomi in $X$ a coefficienti in $\mathbb{Z}_q$ con relazione $X^n=-1$
Sia $S$ un insieme, $s\leftarrow S$ indica che $s$ è campionato uniformemente in $S$
$s\in S\gets B_{\eta}$ indica che $s$ è campionato dalla distribuzione binomiale centrata [1] di parametro $\eta$
$f\in R_q\gets B_\eta$ indica che ciascun coefficiente di $f$ è campionato da $B_\eta$
$\textsf{H}$ , $\textsf{G}$ sono funzioni di hash
$\textsf{KDF}$ è una funzione di key derivation

LWE Public Key Encryption (PKE)

Come accade per un generico schema di cifratura a chiave pubblica, LWE PKE si compone di tre algoritmi: generazione delle chiavi, cifratura e decifratura. Si osserva come LWE PKE sia di fatto uno schema “giocattolo” in quanto permette la cifratura di un singolo bit $x\in\{0,1\}$ .

Generazione chiavi : il vettore $\mathbf{s}$ e la matrice $\mathbf{A}$ sono campionati uniformemente in $\mathbb{Z}_q^k$ e $\mathbb{Z}_q^{m\times k}$ rispettivamente. L’errore $\mathbf{e}=(e_1,\dots,e_m)^{T}\in\mathbb{Z}_q^{m}$ è campionato secondo la distribuzione $B_\eta^m$ . $\mathbf{s}$ costituisce la chiave privata mentre la coppia $(\mathbf{A},\mathbf{b}=\mathbf{As}+\mathbf{e})$ la chiave pubblica. Si osservi che per questioni di sicurezza $m > k$ .
Cifratura di $x\in\{0,1\}$ : il cifrato è costituito da un vettore $\mathbf{u}\in\mathbb{Z}_q^k$ ottenuto dalla somma delle righe di $\mathbf{A}$ corrispondenti ad un certo sottoinsieme di indici $P$ e da un elemento $v\in\mathbb{Z}_q$ risultato della somma delle entrate di $\mathbf{b}$ corrispondenti a $P$ e del valore $\lfloor \frac{q}{2} \cdot x\rfloor$ [2]. Si osservi che se un attaccante intercetta $P$ può risalire direttamente al messaggio $x$ , pertanto il campionamento uniforme di $P$ risulta fondamentale.
Decifratura di $(\mathbf{u},v)$ : grazie alla conoscenza della chiave privata, $x$ è riottenuto valutando se il valore $v-\langle \mathbf{u}, \mathbf{s}\rangle$ è più vicino a $0$ o a $\lfloor \frac{q}{2}\rfloor$ .

Kyber Public Key Encryption (PKE)

Lo schema Kyber PKE mima il caso sopra discusso con una variazione nella struttura matematica in cui vivono gli elementi considerati, infatti si passa da $\mathbb{Z}_q$ a $R_q$ .
È bene osservare come Kyber PKE, nonostante non sia una costruzione giocattolo, non possa comunque essere utilizzato come soluzione di cifratura “standalone” in quanto non garantisce tutti i requisiti di sicurezza necessari in un contesto pratico. Infatti, questa costruzione realizza una sicurezza di tipo IND-CPA [3] ( indistiguishability under chosen plaintext attack ), un livello di sicurezza standard in crittografia ma insufficiente nella maggior parte dei casi d’uso.
Il ruolo fondamentale di Kyber PKE è piuttosto quello di fungere da building block per il meccanismo di incapsulamento chiave esposto da Kyber.

Ad alto livello, i passaggi sono i medesimi di LWE PKE.

Generazione chiavi : il vettore segreto $\mathbf{s}\in R_q^k$ e l’errore $\mathbf{e}\in R_q^k$ sono campionati secondo le distribuzioni $B_{\eta_1}^k$ e $B_{\eta_2}^k$ rispettivamente. La matrice pubblica $\mathbf{A}$ è campionata uniformemente in $R_q^{k\times k}$ .
Cifratura di $m\in R_q$ : il vettore $\mathbf{r}\in R_q^k$ , campionato da $B_{\eta_1}^k$ , ha lo stesso ruolo di $P$ nel caso LWE PKE. Il campionamento aggiuntivo degli errori $\mathbf{e}_1\in R_q^k$ ed $e_2\in R_q$ è necessario per questioni di sicurezza, in quanto, a differenza di LWE PKE, si lavora con la matrice $\mathbf{A}$ quadrata [4]. Il simbolo $\lceil\cdot\rfloor$ indica che si sta calcolando per ciascun coefficiente dell’elemento considerato l’approssimazione all’intero più vicino.
Decifratura di $(\mathbf{u},v)$ : la ratio che guida la decifratura è identica al caso LWE PKE.

La correttezza[5] dello schema è garantita dalla seguente relazione

v-\langle \mathbf{u},\mathbf{s} \rangle= \mathbf{s}^{T}\mathbf{A}^{T}\mathbf{r}+\mathbf{e}^{T}\mathbf{r}+e_2+\Big\lceil\frac{q}{2}\cdot m\Big\rfloor-\mathbf{s}^{T}\mathbf{A}^{T}\mathbf{r}-\mathbf{s}^{T}\mathbf{e_1}= \Big\lceil\frac{q}{2}\cdot m\Big\rfloor + \underbrace{\mathbf{e}^{T}\mathbf{r} -\mathbf{s}^{T}\mathbf{e_1}+e_2}_{\text{termini di errore}}.

Fujisaki-Okamoto Transform (FO)

L’ultimo passaggio per la costruzione del meccanismo di incapsulamento chiave proposto da Kyber è l’applicazione di una variante della trasformazione Fujisaki-Okamoto. Questa operazione, nota in letteratura, consente di realizzare uno schema KEM con sicurezza IND-CCA2 a partire da uno schema PKE con sicurezza IND-CPA.
Il livello IND-CCA2 [3] ( indistinguishability under adaptive chosen ciphertext attack ) è un tipo di sicurezza standard in crittografia che, a differenza del più debole IND-CPA, è adatto a contesti applicativi reali.

L’azione più rilevante della trasformazione FO si nota in fase di ricezione di un ciphertext.
Una volta decifrato un ciphertext, il plaintext corrispondente viene ricifrato e confrontato con quello ricevuto. Lo scopo è di aggiungere un livello di validazione dell’informazione.
Qualora la comparazione abbia esito positivo, una chiave crittografica viene derivata, altrimenti il ciphertext viene ritenuto invalido e rifiutato.

Kyber Key Encapsulation Mechanism (KEM)

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

Generazione chiavi : l’algoritmo è sostanzialmente il medesimo di Kyber PKE. La distinzione più rilevante risiede nel campionamento di un segreto aggiuntivo $z$ che entra in gioco in caso di rifiuto in fase di decapsulamento.
Incapsulamento : un plaintext $m$ è campionato uniformemente. La chiave condivisa $K$ è ottenuta a partire da $m$ e dal cifrato $c$ corrispondente.
Decapsulamento di $c$ : le fasi della trasformazione FO descritta in precedenza sono evidenziate in rosso . Si osserva una particolarità del meccanismo di rifiuto: 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 $z$ campionato in precendenza. 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 . La ratio dietro a questa strategia riguarda una maggior resistenza a cattivi utilizzi. Ad esempio, si vuole evitare che, in mancanza di verifica dell’esito del decapsulamento, alla richiesta di chiave crittografica venga comunque fornita una stringa di default a bassa entropia.

Performance in software

Analizzando le performance dello schema in software, si realizza che l’onere computazionale è suddiviso secondo il seguente grafico a torta [6].

La dicitura Keccak , che risulta la parte più intesiva, raggruppa tutte le primitive simmetriche [7] riportate di seguito.

$\textsf{H}$	SHA3-256
$\textsf{G}$	SHA3-512
$\textsf{KDF}$	SHAKE-256
$\textsf{XOF}$ [8]	SHAKE-128
$\textsf{PRF}$ [8]	SHAKE-256

La NTT[9], invece, indica una particolare trasformazione di elementi in $R_q$ ed è denotata come
$f = f_0 + f_1\cdot X + \cdots f_{n-1}\cdot +X^{n-1}\xmapsto[]{\textsf{NTT}} \hat{f} = \hat{f}_0 + \hat{f}_1\cdot X + \cdots +\hat{f}_{n-1}\cdot X^{n-1}.$
Grazie alla NTT il prodotto di due elementi $f$ e $g$ è dato da
$fg = \textsf{NTT}^{-1}(\hat{f}\circ\hat{g}),$
ove $\hat{f}\circ\hat{g}$ è calcolato componente per componente
$(\hat{f}\circ\hat{g})_i=\hat{f}_i\cdot \hat{g}_i,$
risultando molto efficiente dal punto di vista computazionale.

Nel contesto della standardizzazione post-quantum del NIST, l’efficienza computazionale ha giocato un ruolo fondamentale. In questa direzione, punto di forza di Kyber è rappresentato proprio dall’efficientamento delle moltiplicazioni fra elementi in $R_q$ garantito dall’applicazione della NTT.

[1] Campionamento da $B_{\eta}$ : $\begin{align*} &\{(a_i,b_i)\}^{\eta}_{i=1} \longleftarrow (\{0,1\}^2)^\eta\\\text{output } & \sum_{i=1}^{\eta}(a_i-b_i)\in\{-\eta\dots,-1,0,1\dots,\eta\}.\end{align*}$

[2] $\lfloor\cdot\rfloor$ indica la parte intera.

[3] pagina Wikipedia

[4] Qualora $\mathbf{e_1}$ , $e_2$ fossero nulli e $\mathbf{A}$ di rango massimo, da $\mathbf{u}$ si potrebbe ricavare $\mathbf{r}$ e successivamente da $v$ si potrebbe dedurre il messaggio $m$ .

[5] Lo schema è corretto se vale $\text{Kyber}.\textsf{CPAPKE}.\textsf{Dec}(sk,\text{Kyber}.\textsf{CPAPKE}.\textsf{Enc}(pk,m))=m$ .

[6] performance dell’implementazione di riferimento di Kyber in un processore Intel Core i7-8665U

[7] scelte secondo lo standard FIPS-202

[8] $\textsf{XOF}$ e $\textsf{PRF}$ non sono trattate in questo articolo, intervengono nei passaggi di campionamento.

[9] Si precisa come la NTT implementata in Kyber sia una lieve variazione di quella qui presentata a scopo divulgativo.

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

Veronica Cristiano, laureata triennale in Matematica presso l’Università di Pisa e laureata magistrale in Matematica con specializzazione in Crittografia presso l’Università di Trento, entrata a far parte del gruppo di ricerca in Crittografia di Telsy a metà del 2021.

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 occupandosi in particolare di temi inerenti alle tecnologie quantistiche.