1 Introduction
-
we generalize LIGA’s Key Generation algorithm, i.e., the choice of the \(\mathbf {z}_i\)’s (the interleaved errors in the public key) is more flexible now (in [50], \(\mathbf {z}_1 = \mathbf {z}_2 = \dots = \mathbf {z}_u\)),
-
we present a KEM/DEM version of LIGA,
-
we identify formal problems in the rank metric on which the security of LIGA relies and prove the IND-CPA/CCA2 security of the KEM/DEM version under the assumption that some of these problems are hard,
-
we analyze new exponential-time attacks on these problems.
2 Preliminaries
2.1 Notations
2.2 Rank-metric codes and Gabidulin codes
2.3 Interleaved rank-metric codes
3 Key generation in the original Faure–Loidreau system
3.1 The original algorithm
Name | Use | Restriction |
---|---|---|
q | Small field size | Prime power |
m | Extension degree | \(1 \le m\) |
n | Code length | \(n \le m\) |
k | Code dimension | \(k < n\) |
u | Extension degree | \(2 \le u < k\) |
w | Error weight in public key | \(\max \left\{ n-k-\frac{k-u}{u-1}, \left\lfloor \frac{n-k}{2} \right\rfloor +1 \right\} \le w < \frac{u}{u+2} (n-k)\) |
\(t_{\mathsf {pub}}\) | Error weight in ciphertext | \(t_{\mathsf {pub}}= \left\lfloor \frac{n-k-w}{2} \right\rfloor \) |
\(\zeta \) | \(\mathbb {F}_{q^m}\)-dimension of error vector in the public key | \(\zeta < \frac{w}{n-k-w}\ \) and \(\ \zeta q^{\zeta w-m} \le \tfrac{1}{2}\) |
3.2 Coding-theoretic interpretation of the original public key
3.3 Efficient key recovery of the original FL key
3.3.1 GOT attack
3.3.2 Interleaved decoding attack
3.3.3 Equivalence of GOT attack and interleaved decoding attack
4 The new system LIGA
4.1 The new key generation algorithm
4.2 The public key encryption version
4.3 KEM/DEM version \({{\Pi }}^{\mathrm{PKE}}\) and \({\Pi }^{\mathrm{KEM}}\)
4.4 Complexity
4.4.1 Timing attacks
4.4.2 Asymptotically fastest methods
-
\(O^\sim (n^{\min \{\frac{\omega +1}{2},1.635\}})\) operations in \(\mathbb {F}_{q^m}\) or \(O^\sim (n^{\omega -2}m^2)\) operations in \(\mathbb {F}_q\) in general4 and
-
\(O^\sim (n)\) operations in \(\mathbb {F}_{q^m}\) if the entries of \(\mathbf {g}\) are a normal basis of \(\mathbb {F}_{q^m}/\mathbb {F}_q\),
5 Difficult problems & semantic security of LIGA
5.1 Difficult problems in the rank metric
-
\(\mathbf {G}\xleftarrow {\$}\mathcal {G}\), where \(\mathcal {G}\) is the set of all generator matrices of [n, k] Gabidulin codes over \(\mathbb {F}_{q^m}\)
-
\(\mathbf {M}\xleftarrow {\$}\{\mathbf {X}\in \mathbb {F}_{q^m}^{u\times k} : {{\,\mathrm{rk}\,}}_{q^m}(\mathbf {X}_{[k-u+1,k]}) = u\} \).
-
\(\mathcal {A} \xleftarrow {\$}\{ \text {subspace } \mathcal {U} \subseteq \mathbb {F}_{q^m}^w \, : \, \dim \mathcal {U} = \zeta , \, \mathcal {U} \text { has a basis of full}-\) \(\mathbb {F}_q\) \(-\text { rank elements} \}\)
-
\(\mathbf {E}' \xleftarrow {\$}\left\{ \begin{pmatrix} \mathbf {s}_1' \\ \vdots \\ \mathbf {s}_u' \end{pmatrix} \in \mathbb {F}_{q^m}^{u \times w}\, : \, \langle \mathbf {s}_1',\dots ,\mathbf {s}_u'\rangle _{\mathbb {F}_{q^m}} = \mathcal {A}, \, {{\,\mathrm{rk}\,}}_{q}(\mathbf {s}_i') = w \, \forall \, i \right\} \)
-
\(\mathbf {Q} \xleftarrow {\$}\{ \mathbf {A}\in \mathbb {F}_q^{w \times n} : {{\,\mathrm{rk}\,}}_{q}(\mathbf {A}) = w \}\)
-
\(\mathbf {E}\leftarrow \mathbf {E}' \mathbf {Q}\)
-
\(\mathbf {e}\xleftarrow {\$}\{ \mathbf {x}\in \mathbb {F}_{q^m}^{n}\, : \, {{\,\mathrm{rk}\,}}_q(\mathbf {x}) = t_{\mathsf {pub}}\} \)
-
\(\alpha \xleftarrow {\$}\mathbb {F}_{q^{mu}}\)
-
\(\mathbf {k}\leftarrow {{\,\mathrm{ext}\,}}_{\mathbf {\gamma }}^{-1}(\mathbf {K})\)
-
\(\mathbf {y}\leftarrow {{\,\mathrm{Tr}\,}}(\alpha \mathbf {k}) +\mathbf {e} = {{\,\mathrm{Tr}\,}}(\alpha \mathbf {m}) \mathbf {G}+ {{\,\mathrm{Tr}\,}}(\alpha \mathbf {z}) + \mathbf {e}\)
5.2 Semantic security
5.2.1 IND-CPA security of \({{\Pi }}^{\mathrm{PKE}}\)
-
Partible: \(\mathsf {Encrypt}_1\) takes as input a public key \(\mathsf {pk}\) and \(r \in \mathcal {R}\), and outputs a \(p(\lambda )\) bit-string, where \(\lambda \) is the security parameter. \(\mathsf {Encrypt}2\) takes as input a key \(\mathsf {pk}\), and \(\mathbf {m}\in \mathcal {M}\) and outputs a \(p(\lambda )\) bit-string. Here p is some polynomial in the security parameter \(\lambda \). Then for any \(\mathsf {pk}\) given by \(\mathsf {KeyGen}\), \(r \in \mathcal {R}\), and \(\mathbf {m}\in \mathcal {M}\), \(\mathsf {Encrypt}_1( \mathsf {pk}, r ) \oplus \mathsf {Encrypt}_2 ( \mathsf {pk}, \mathbf {m}) = \mathsf {Encrypt}( \mathsf {pk}, \mathbf {m}; r ) \).
-
Pseudorandomness: Let D be a probabilistic algorithm and letWe define the advantage function of the problem as follows. For any t,$$\begin{aligned} \mathsf {Adv}_{D,\mathsf {Encrypt}_1}^{ind}(\lambda ) =&\Pr \Big [ D(\mathsf {pk},\mathsf {Encrypt}_1(\mathsf {pk},r)) = 1 |r \xleftarrow {\$}\mathcal {R}, (\mathsf {sk}, \mathsf {pk}) \leftarrow \mathsf {KeyGen}\big (1^{\lambda }\big ) \Big ] \\&- \Pr \big [ D(\mathsf {pk},s) = 1 |s \xleftarrow {\$}\mathcal {U}_{p(\lambda )}, (\mathsf {sk}, \mathsf {pk}) \leftarrow \mathsf {KeyGen}\big (1^{\lambda } \big ) \big ]. \end{aligned}$$where the maximum is taken over all D with time-complexity t. Then, the function \(\mathsf {Adv}_{\mathsf {Encrypt}_1}^{ind}(\lambda ,t)\) is negligible for every polynomial bounded t and every sufficiently large \(\lambda \).$$\begin{aligned} \mathsf {Adv}_{\mathsf {Encrypt}_1}^{ind}(\lambda ,t) = \max _{D} \big \{\mathsf {Adv}_{D,\mathsf {Encrypt}_1}^{ind}(\lambda ) \big \}, \end{aligned}$$
5.2.2 IND-CCA2 security of \({\Pi }^{\mathrm{KEM}}\)
6 Security analysis of LIGA
6.1 Exponential-time attacks on ResIG-Search
6.1.1 Brute-force the vector \(\mathbf {z}\) attack
6.1.2 Interleaved decoding attack
6.1.3 List decoding of the public key attack
6.1.4 Randomized Gabidulin decoding attack on the public key
6.1.5 Moving to another close error attack
6.2 Exponential-time attacks on ResG-Search
6.2.1 Randomized Gabidulin decoding attack on the ciphertext
6.2.2 List decoding of the ciphertext attack
6.2.3 Combinatorial rank syndrome decoding (RSD) attack
6.2.4 Algebraic RSD attack
6.2.5 Linearization attack
6.2.6 Algebraic attacks
6.2.7 Overbeck-like attack
6.2.8 Brute-force attack on the element \(\alpha \)
6.3 Exponential-time attacks on ResIG-Dec
6.4 Avoiding Weak Keys
6.5 Summary of the work factors
-
The work factor of the second algebraic attack in [16] (cf. Sect. 6.2.6) is unknown. Hence, we choose the code parameters such that the resulting non-linear system of equations occurring in the attack consists of more than \(n_\mathrm {p} \approx 2^{32}\) many polynomials of degree at least \(d_\mathrm {p} = 127\). This is the same choice as in [16].
-
Since there is no efficient list decoder for Gabidulin codes, the work factor of the list decoding the public key or the ciphertext in Sect. 6.2.2 is not known. However, we do have a lower bound on the worst-case work factor for some codes, given by the maximal list size \(\mathcal {L}_\mathbf {c},\text {worst}\) in (12). In all examples for which the bound holds, we chose the parameters such that \(\log _2(\mathcal {L}_\mathbf {c},\text {worst})\) is much larger than the claimed security level.
-
The probability of generating a weak key should be negligible. Thus, we choose the parameters such that \(\zeta q^{\zeta w-m} \le \tfrac{1}{2}\) andwhere \(\lambda \) is the security parameter and$$\begin{aligned} \Pr (\text {weak key})&\le \frac{q^{m\zeta }-1}{(q^m-1)(q^{mw}-1)}\left( \sum _{i=0}^{t-1} \genfrac[]{0.0pt}{}{w}{i}_{q} \prod _{j=0}^{i-1} \left( q^m-q^j\right) -1 \right) \\&\le 2^{-\lambda }, \end{aligned}$$$$\begin{aligned} t := \min \left\{ t \, : \, q^{-m\zeta }+ {256} \min \{t,t_{\mathsf {pub}}\}^2 q^{-(t+t_{\mathsf {pub}}-w+1)\left( n+\frac{t-3w-t_{\mathsf {pub}}}{2}\right) } \le 2^{-\lambda } \right\} . \end{aligned}$$
Name of the attack | Work factor |
---|---|
Brute-force \(\mathbf {z}\) (Sect. 6.1.1) | \(\text {WF}_{{\mathbf {z}}}=\frac{q^{w(n-w)}}{\mathcal {N}}\) |
Interleaved Decoding (Sect. 6.1.2) | \(\text {WF}_{\text {ILD}}= \frac{q^{m(w-\zeta (n-k-w))}}{\mathcal {N}}\) |
Randomized Decoding (Sect. 6.1.4) | \(\text {WF}_{\text {RGD}} = \frac{n}{64} q^{m(n-k)-w(n+m)+w^2+\min \{2\xi (\frac{n+k}{2}-\xi ),wk\} }\) |
Moving to Close Error (Sect. 6.1.5) | \(\text {WF}_{\text {MCE}} = q^{(n-w)(w(\zeta +1)-\zeta (n-k))}\) |
Combinatorial RSD (Sect. 6.2.3) | \( \text {WF}_{\text {CRSD}}=(n-k)^3m^3q^{t_{\mathsf {pub}}\big \lceil \frac{(k+1)m}{n} \big \rceil -m}\) |
Algebraic RSD (Sect. 6.2.4) | \( \text {WF}_{\text {ARSD}}\) |
Linearization (Sect. 6.2.5) | \(\text {WF}_{\text {Lin}} = q^{m \cdot \max \{u t_{\mathsf {pub}}+ u + 1 - \varphi ,(u+2)t_{\mathsf {pub}}+ k +1 -n\}}\) |
GCD based attack (Sect. 6.2.6) | \(\text {WF}_{\text {GCD}} = q^{m(u-1)}\frac{q^{t_{\mathsf {pub}}+1}-1}{q-1}\) |
Brute-force \(\alpha \) (Sect. 6.2.8) | \(\text {WF}_{\alpha }= q^{mu}\) |
Distinguisher for \(\mathbf {k}_{\mathsf {pub}}\) (Sect. 6.3) | \(\text {WF}_{\mathbf {k}_{\mathsf {pub}},\mathrm {distinguisher}} = q^{m\zeta }\) |
Parameter set | q | u | k | n | m | \(\zeta \) | w | \(t_{\mathsf {pub}}\) | R |
---|---|---|---|---|---|---|---|---|---|
LIGA-128 | 2 | 5 | 53 | 92 | 97 | 2 | 27 | 6 | 0.52 |
LIGA-192 | 2 | 5 | 69 | 120 | 127 | 2 | 35 | 8 | 0.53 |
LIGA-256 | 2 | 5 | 85 | 148 | 149 | 2 | 43 | 10 | 0.54 |
7 Parameters and key sizes
System name | \(\mathsf {sk}\) | \(\mathsf {pk}\) | \(\mathsf {ct}\) | Security | DFR |
---|---|---|---|---|---|
LIGA-128 | 40 | 5618 | 1116 | 128 bit | No |
RQC-I | 40 | 1834 | 3652 | 128 bit | No |
ROLLO-I-128 | 40 | 696 | 696 | 128 bit | Yes |
Loidreau-128 | – | 6720 | 464 | 128 bit | No |
BIKE-2 Level 1 | 249 | 1271 | 1271 | 128 bit | Yes |
McEliece348864 | 6452 | 26,1120 | 128 | 128 bit | No |
LIGA-192 | 40 | 9565 | 1905 | 192 bit | No |
RQC-II | 40 | 2853 | 5690 | 192 bit | No |
ROLLO-I-192 | 40 | 958 | 958 | 192 bit | Yes |
Loidreau-192 | – | 11,520 | 744 | 192 bit | No |
BIKE-2 Level 2 | 387 | 2482 | 2482 | 192 bit | Yes |
McEliece460896 | 13,568 | 524,160 | 188 | 192 bit | No |
LIGA-256 | 40 | 13,823 | 2757 | 256 bit | No |
RQC-III | 40 | 4090 | 8164 | 256 bit | No |
ROLLO-I-256 | 40 | 1371 | 1371 | 256 bit | Yes |
Loidreau-256 | – | 16,128 | 1024 | 256 bit | No |
BIKE-2 Level 3 | 513 | 4094 | 4094 | 256 bit | Yes |
McEliece6688128 | 13,892 | 1,044,992 | 240 | 256 bit | No |