Introduction
Our contribution
Paper organization
Preliminaries
\({\mathbb {F}}_q\)
| A finite field of q elements |
| | The concatenation operator of vectors or matrices |
\(x\xleftarrow {\$}S\)
| The operation of selecting an element x from set A uniformly at random |
\(||{\mathbf {a}}||\)
| The rank of a vector \({\mathbf {a}}\) |
\(Len({\mathbf {x}})\)
| A function that takes as input a vector \({\mathbf {x}}\), and outputs the length of \({\mathbf {x}}\) |
\(Rd_k({\mathbf {x}})\)
| A function that takes as input a seed \({\mathbf {x}}\), and outputs a random vector from \({\mathbb {F}}_{q^m}^k\) |
\(Conv_t({\mathbf {x}})\)
| A function that takes as input a vector \({\mathbf {x}}\) of length \(\lfloor \log _{q^m}\left( {\begin{array}{c}n\\ t\end{array}}\right) \rfloor\) over \({\mathbb {F}}_{q^m}\), and outputs an error vector of length n and weight t. The inverse of function \(Conv_{t}(\cdot )\) is denoted by \(Conv^{-1}_{t}(\cdot )\) |
\(Lt_{k}({\mathbf {x}})\)
| A function that takes as input a vector \({\mathbf {x}}\), and outputs the left k components |
\(Rt_{k}({\mathbf {x}})\)
| A function that takes as input a vector \({\mathbf {x}}\), and outputs the right k components |
Revisiting the LT scheme [18]
-
Setup(\(1^{\lambda }\)): Given a security parameter \(\lambda\), the algorithm chooses a prime power q, a group of integers \((n, m, k, k_0, k_1, t)\) s.t. \(n>k, ~k_0 = \lfloor \frac{k}{2}\rfloor , ~k_1 = k- k_0, t \le \lfloor \frac{n-k}{2}\rfloor\) according to \(\lambda\). The algorithm then outputs the public parameter \(params = (q, n, m, k, k_0, k_1, t)\).
-
KGen(params): Give the public parameter params, the algorithmThe public/private key pair is (\(pk = (\hat{G}, {\mathbf {x}}),sk = (Q, G, P, \mathcal {DEC}(\cdot ))\)).
-
Chooses a generator matrix \(G \in {\mathbb {F}}_{q^m}^{k \times n}\) of a \([n, k]_{q^m}\) linear code \({\mathcal {C}}\) with error correcting ability t and an efficient decoding algorithm \(\mathcal {DEC}(\cdot )\);
-
Chooses a vector \({\mathbf {x}} \xleftarrow {\$}{\mathbb {F}}_{q^m}^n\) s.t. \(\Vert {\mathbf {x}}\Vert = n\);
-
Chooses two invertible matrices \(Q \in {\mathbb {F}}_{q^m}^{k \times k}\) and \(P \in {\mathbb {F}}_q^{n \times n}\) uniformly at random;
-
Computes \(\hat{G} = QG + Rot_k({\mathbf {x}})P\).
-
Our IND-CCA2 secure PKE scheme
-
Setup(\(1^{\lambda }\)): Given a security parameter \(\lambda\), the algorithm
-
Chooses a prime number power q, a group of integers \((n, m, k, k_0, k_1, t, t_0, t_1)\) s.t. \(n>k, ~k_0 = \lfloor \frac{k}{2}\rfloor , ~k_1 = k- k_0,\ t \le \lfloor \frac{n-k}{2}\rfloor\), \(~t_0 = \lfloor \frac{t}{2}\rfloor , ~t_1 = t- t_0\);
-
Chooses a random vector \(\mathbf {con}\) over \({\mathbb {F}}_{q^m}\) with \(Len(\mathbf {con}) \le \frac{1}{2}\ell\), where \(\ell _0=\lfloor \log _{q^m}\left( {\begin{array}{c}n\\ t_0\end{array}}\right) \rfloor\), \(\ell _1=\lfloor \log _{q^m}\left( {\begin{array}{c}n\\ t_1\end{array}}\right) \rfloor\), and \(\ell =\ell _0+\ell _1\);
-
Outputs the public parameter \(params = (q, n, m, k, k_0, k_1, t, t_0, t_1, \mathbf {con})\).
-
-
KGen(params): Give the public parameter \(params= (q, n, m, k, k_0, k_1, t, t_0, t_1, \mathbf {con})\), the algorithmThe public key is \(pk = (\hat{G}, {\mathbf {x}})\) and the private key is \(sk = (Q, G, P, \mathcal {DEC}(\cdot ))\).
-
Chooses a generator matrix \(G \in {\mathbb {F}}_{q^m}^{k \times n}\) of an \([n, k]_{q^m}\) linear code \({\mathcal {C}}\) with error correcting ability t and an efficient decoding algorithm \(\mathcal {DEC}(\cdot )\);
-
Chooses a vector \({\mathbf {x}} \xleftarrow {\$}{\mathbb {F}}_{q^m}^n\) s.t. \(\Vert {\mathbf {x}}\Vert = n\);
-
Chooses two invertible matrices \(Q \in {\mathbb {F}}_{q^m}^{k \times k}\) and \(P \in {\mathbb {F}}_q^{n \times n}\) uniformly at random;
-
computes \(\hat{G} = QG + Rot_k({\mathbf {x}})P\).
-
Security proof
Correctness
IND-CCA2 security
-
\(\mathbf{Exp }_{{\mathcal {A}}, \textsf {PKE}}^{\textsf {IND-CCA2}}(\lambda )\):
-
\(params \leftarrow \textsf {Setup}(\lambda )\)
-
\((pk, sk) \leftarrow \textsf {KGen}(params)\)
-
\(({\mathbf {m}}_0, {\mathbf {m}}_1, \text{ state })\leftarrow {\mathcal {A}}_1^{\textsf {Dec}(sk,\cdot )}(pk)\), where \({\mathbf {m}}_0\) and \({\mathbf {m}}_1\) have the same length
-
\(b \xleftarrow {\$}\{0,1\}\)
-
\({\mathbf {c}}' \leftarrow \textsf {Enc}(pk,{\mathbf {m}}_b)\)
-
\(b' \leftarrow {\mathcal {A}}_2^{\textsf {Dec}(sk,\cdot )}({\mathbf {c}}',\text{ state })\). Note that \({\mathcal {A}}_2\) is not allowed to make decryption query on \({\mathbf {c}}'\).
-
Outputs 1 if \(b' = b\), otherwise outputs 0.
-
\(\textsf {Evt}_1\): the event that \({\mathbf {v}}\) is queried to Rd in \(q_{Rd}\) queries before \({\mathbf {u}}_1\) is queried to \({\mathcal {H}}\).
-
\(\textsf {Evt}_2\): the event that \({\mathbf {u}}_1\) is queried to \({\mathcal {H}}\) in \(q_{{\mathcal {H}}}\) times before \({\mathbf {v}}\) is queried to Rd.
-
The plaintext-extractor takes as input a ciphertext \({\mathbf {c}}\).
-
For \(q_{Rd}\) times queries to Rd, the input and the output pairs of Rd are denoted by \(({\mathbf {v}}_i, V_i)\), \(1\le i \le q_{Rd}\). Similarly, the input and the output pairs of \({\mathcal {H}}\) are denoted by \(({\mathbf {u}}_{1j}, U_{1j})\), \(1\le j \le q_{{\mathcal {H}}}\).
-
The plaintext-extractor finds the pair \(({\mathbf {v}}_i, V_i) = ({\mathbf {u}}_2 - U_{1j}, {\mathbf {u}}_{1j} - ({\mathbf {m}}|\mathbf {con}))\) s.t.$$\begin{aligned} {\mathbf {e}}_0=\, & {} Conv_{t_0}(Lt_{\ell _0}(Lt_{\ell _0+\ell _1}({\mathbf {u}}_{1j}|{\mathbf {u}}_2))), \end{aligned}$$(8)are two error vectors of \({\mathbf {c}}\) and \(Rt_{k}({\mathbf {u}}_{1j}|{\mathbf {u}}_2)\) is the plaintext of \({\mathbf {c}}\) in the LT scheme.$$\begin{aligned} {\mathbf {e}}_1=\, & {} Conv_{t_1}(Rt_{\ell _1}(Lt_{\ell _0+\ell _1}({\mathbf {u}}_{1j}|{\mathbf {u}}_2)) \end{aligned}$$(9)
-
If the plaintext-extractor cannot find the pair \(({\mathbf {v}}_i, V_i)\) or \(({\mathbf {u}}_{1j}, U_{1j})\), it rejects the ciphertext \({\mathbf {c}}\).
-
\(\textsf {Evt}_3\): the event that \({\mathcal {A}}\) queries the appropriate ciphertext \({\mathbf {c}}\) to \({\mathcal {D}}\) before \({\mathcal {A}}\) queries \({\mathbf {u}}_{1j}\) to \({\mathcal {H}}\) and \({\mathbf {v}}_i\) to Rd.
Efficiency
\(q^m\)
|
n
|
k
|
t
| Ciphertext size (KB) | Public key size (KB) | Security level | Semantic security | |
---|---|---|---|---|---|---|---|---|
Loidreau’s scheme |
\(2^{128}\)
| 90 | 24 | 11 | 1.44 | 21.50 | 140 | IND-CCA2 |
\(2^{128}\)
| 120 | 80 | 4 | 1.92 | 51.00 | 141 | ||
Wang’s scheme |
\(2^9\)
| 1020 | 660 | 180 | 1.15 | 980 | 128 | Not Given |
\(2^{10}\)
| 1560 | 954 | 203 | 1.95 | 2460 | 192 | ||
Our PKE scheme |
\(2^{75}\)
| 73 | 21 | 13 | 1.37 | 15.06 | 141 | IND-CCA2 |
\(2^{85}\)
| 83 | 18 | 16 | 1.76 | 16.76 | 154 | ||
\(2^{71}\)
| 69 | 19 | 13 | 1.22 | 12.25 | 133 | ||
\(2^{101}\)
| 99 | 22 | 17 | 2.5 | 28.75 | 196 |