Design criteria of a new code-based KEM

Abstract

The advances in quantum technologies became a threat to cryptosystems based on number-theoretic approach. Therefore, the development of post-quantum algorithms is currently underway. One of the areas of research is key encapsulation mechanisms (KEMs), which are supposed to replace the Diffie–Hellman key exchange protocol. When constructing such mechanisms, a modular approach based on a public key cryptosystem is often used. We provide an overview of such approaches for schemes based on error-correcting codes. We present arguments for and against the choice of each component of the modular approach. Moreover, we propose the combinations allowing to build KEMs with most favorable characteristics and present a proof of security for one of them.

1 Introduction

Post-quantum cryptography is a relatively young field, which appeared as a “counter-measure” to Shor’s algorithms [1] solving factorization and discrete logarithm problems with polynomial complexity on a quantum computer whereas they are the basis of security of all modern cryptographic protocols. In order for these protocols to remain secure in the era of powerful quantum computers, it is necessary to modify them so that their security relies on the complexity of problems that are not covered by Shor’s algorithms. Such problems include, for example, problems related to error-correcting codes, lattices, multivariate polynomials and hash functions. A large number of new schemes were spawned by the NIST competition for the best post-quantum algorithms for further standardization.

NIST has claimed two main areas of research: key encapsulation mechanisms $(\textsf{KEM})$ and digital signature schemes. This choice is explained by the necessity of replacement of the main public-key cryptosystems which are subject to quantum attacks. These include digital signatures and encryption schemes, as well as key exchange protocols like Diffie–Hellman one. If post-quantum signatures are obviously designed to replace classical ones, then the other two points are closed by $\textsf{KEM}$s. Public key encryption schemes are included in the $\textsf{KEM}$ proposal as an integral part, and the $\textsf{KEM}$s themselves are analogues of key exchange protocols, where, however, the key is generated by one party and is transferred to the second party and not created by them jointly.

Known approaches to constructing $\textsf{KEM}$s on error-correcting codes do not depend on the structure of codes as such, but the codes affect cryptosystems’ properties and security. A $\textsf{KEM}$ is usually built on a cryptosystem in general form but requires it to satisfy a number of properties. And it is the refinement of this cryptosystem that sets the security level and the performance characteristics of the final scheme. To build such a modular $\textsf{KEM}$ scheme, one needs to fix a family of codes with its specialized decoding algorithm, a cryptosystem based on it and a transformation from this cryptosystem to $\textsf{KEM}$.

There exist schemes based on various codes, cryptosystems and transformations, but often the proposals lack design rationale and do not explain why one approach rather than another is chosen. At the same time, these considerations would be very helpful when synthesizing new schemes or for choosing one of the already proposed options. In the present work we aim to consolidate all the disparate discussions on the advantages and disadvantages of various approaches, as well as to analyze the outcomes of applying the most promising among them.

2 Results

In Sects. 4–6 we provide a detailed description of the steps required for synthesis of an error-correcting code-based $\textsf{KEM}$. By selecting the best approach from a set of options at each step, a scheme with optimal characteristics can be constructed. Such schemes are enumerated in Sect. 7 along with related remarks. Finally, in Sect. 8 we give a complete proof for one of them.

3 Preliminaries

In this section we provide definitions and facts used later in the text.

3.1 Coding theory and problems

Definition 1

(Linear code) Let q, m, n be positive integers such that q is prime and $k < n$. And let $\textrm{GF}(q^m)$ be a Galois field of order $q^m$ and $V_{n}$ be a linear space over the field $\textrm{GF}(q^m)$ of dimension n. Then linear block code is a linear k-dimensional subspace $\mathcal {C}$ of the space $V_{n}$.

Here k is called the dimension of the code, and n is its length. One of the most important characteristics of a code is parameter t that corresponds to the number of errors the code can fix. It is determined by the minimum distance of the code.

Definition 2

(Hamming weight) Hamming weight $\textrm{wt}(x)$ of vector x is the number of its nonzero elements.

Definition 3

(Hamming distance) Hamming distance $\rho (x,y)$ between vectors x and y is the number of positions at which the corresponding bits in this vectors are different.

Definition 4

(Minimum distance) The minimum distance d of the code $\mathcal {C}$ is defined as the minimum Hamming distance between the distinct codewords of $\mathcal {C}$:

$$\begin{aligned} d = \min _{\begin{array}{c} x \in \mathcal {C},\,y \in \mathcal {C}, \\ x \ne y \end{array}} \rho (x,y). \end{aligned}$$

A linear code $\mathcal {C}$ with parameters n, k and t can be defined either by its generator or parity-check matrix.

Definition 5

(Generator matrix) Matrix G of size $k \times n$ with elements from $\textrm{GF}(q^m)$ is called the generator matrix of code $\mathcal {C}$ if its rows form a basis of $\mathcal {C}$.

Definition 6

(Parity-check matrix) Full-rank matrix H of size $(n-k) \times n$ with elements from $\textrm{GF}(q^m)$ is called a parity-check matrix of code $\mathcal {C}$ if the equality $Hc^T = 0$ holds if and only if $c \in \mathcal {C}$.

Definition 7

(Syndrome decoding) The problem of finding a vector $e\in \textrm{GF}(q^m)^n$ such that ${\textrm{wt}(e)=t}$ and $He^T=s^T$ given as inputs a parity-check $(n-k) \times n$-matrix H of a code over $\textrm{GF}(q^m)$, a nonzero vector $s \in \textrm{GF}(q^m)^{n-k}$ and an integer t is called the syndrome decoding problem.

Definition 8

(Decoding) The problem of finding a pair of vectors $(x,e)\in \textrm{GF}(q^m)^k \times \textrm{GF}(q^m)^n$ such that $\textrm{wt}(e)=t$ and $y=xG+e$ given as inputs a generator $(k \times n)$-matrix G of a code over $\textrm{GF}(q^m)$, a nonzero vector $y \in \textrm{GF}(q^m)^{n}$ and an integer t is called the decoding problem.

The decision syndrome decoding problem is NP-complete[2, 3]. The decoding problem is equivalent to the syndrome decoding problem in terms of complexity and therefore is also NP-hard. The best known algorithm named Information Set Decoding (ISD) solves this problem requiring $O(2^{0.0465n})$ bit operations [4] for $t=d/2$.

3.2 Cryptosystems

Henceforth we denote the message space by $\mathcal {M}$, the key space by $\mathcal {K}$ and the randomness space by $\mathcal {R}$. We use $\lambda$ for the security parameter.

Definition 9

($\textsf{PKE}$) A public-key cryptosystem $(\textsf{PKE})$ is a triplet of algorithms $(\textsf{KGen}, \textsf{Enc}, \textsf{Dec})$ such that

• 1. $\textsf{KGen}$ is a polynomial probabilistic key generation algorithm such that $\textsf{KGen}(1^n)=(\textsf{pk}, \textsf{sk})$, where $\textsf{pk}$ is the public key and $\textsf{sk}$ is the secret key;

• 2. $\textsf{Enc}$ is a polynomial (probabilistic) encryption algorithm that for an arbitrary $m\in \mathcal {M}$ returns $\textsf{Enc}(\textsf{pk}, m)=c$, where c is called the ciphertext;

• 3. $\textsf{Dec}$ is a polynomial decryption algorithm such that $\textsf{Dec}(\textsf{sk}, c) =$

  $$\begin{aligned} ={\left\{ \begin{array}{ll} m \in \mathcal {M}, &{} \text {if ~{ c}~ is a valid ciphertext for { m};} \\ \bot \notin \mathcal {M}, &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$

  Moreover, for any message $m \in \mathcal {M}$ and any key $\textsf{sk}\leftarrow \textsf{KGen}(1^n)$ it holds that $m = \textsf{Dec}(\textsf{sk}, \textsf{Enc}(\textsf{pk}, m)).$

A cryptosystem having deterministic algorithm $\textsf{Enc}$ is also called deterministic. Otherwise we can explicitly indicate the use of randomness $r \in \mathcal {R}$ by writing $\textsf{Enc}(\textsf{pk}, m, r)$. Further in the text, by default we assume that the cryptosystem is non-deterministic.

In [5] several more important properties of public-key cryptosystems were defined.

Definition 10

(Rigidity) A deterministic $\textsf{PKE}$ is called rigid if for all key pairs $(\textsf{pk}, \textsf{sk}) \leftarrow \textsf{KGen}$ and all ciphertexts c, it holds that either $\textsf{Dec}(\textsf{sk}, c) = \bot$ or $\textsf{Enc}(\textsf{pk}, \textsf{Dec}(\textsf{sk}, c)) = c.$

Definition 11

($\gamma$-spreadness) $\textsf{PKE}$ is said to be $\gamma$-spread if, for every key pair $(\textsf{pk}, \textsf{sk}) \leftarrow \textsf{KGen}$, every message $m \in \mathcal {M}$ and every possible ciphertext $c \in \mathcal {C}$ holds

$$\begin{aligned} \mathbb {P}_{r\rightarrow \$\mathcal {R}} [c = \textsf{Enc}(\textsf{pk},m, r)] \leqslant 2^{-\gamma }. \end{aligned}$$

Definition 12

($\delta$-correctness) $\textsf{PKE}$ is called $\delta$-correct if

$$\begin{aligned} \mathbb {E}\left[ \max _{m \in \mathcal {M}} \mathbb {P}[\textsf{Dec}(\textsf{sk}, \textsf{Enc}(\textsf{pk},m)) \ne m ]\right] \leqslant \delta , \end{aligned}$$

where the expectation is taken over ${(\textsf{pk}, \textsf{sk}) \leftarrow \textsf{KGen}}$ and the probability is taken over internal probabilities of $\textsf{Enc}$ and $\textsf{Dec}$ algorithms.

Definition 13

($\mathsf {OW\text {-}CPA}~\textsf{PKE}$) For any adversary $\mathcal {A}$ in the $\mathsf {OW\text {-}CPA}$ model the advantage against $\textsf{PKE}$ is defined as follows:

where the experiment $\mathsf {OW\text {-}CPA}$ is described below:

Definition 14

($\mathsf {IND\text {-}CPA}~ \& ~\textsf{IND}\text {-}\textsf{CCA}~\textsf{PKE}$) For any adversary $\mathcal {A}$ in model $\textsf{Model}\in \{\mathsf {IND\text {-}CPA},\textsf{IND}\text {-}\textsf{CCA}\}$ the advantage against $\textsf{PKE}$ is defined as follows:

where the experiment $\textsf{Model}$ is described below:

3.3 Key encapsulation mechanisms

Definition 15

($\textsf{KEM}$) For a given key space $\mathcal {K}$ a key encapsulation mechanism $(\textsf{KEM})$ is a triplet of algorithms ($\textsf{KGen}, \textsf{Encaps}, \textsf{Decaps}$) such that

• 1. $\textsf{KGen}$ is a polynomial probabilistic key generation algorithm such that $\textsf{KGen}(1^n)=(\textsf{pk}, \textsf{sk})$, where $\textsf{pk}$ is the public key and $\textsf{sk}$ is the secret key;

• 2. $\textsf{Encaps}$ is a polynomial probabilistic encapsulation algorithm such that $\textsf{Encaps}(\textsf{pk})=(K,c)$, where c is called the encapsulation of the key $K\in \mathcal {K}$;

• 3. $\textsf{Decaps}$ is a polynomial decapsulation algorithm such that $\textsf{Decaps}(\textsf{sk}, c) =$

  $$\begin{aligned} ={\left\{ \begin{array}{ll} K \in \mathcal {K}, &{} \text {if { c} is a valid encapsulation of { K};} \\ \bot \notin \mathcal {K}, &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$

Moreover, for any key pair $(\textsf{pk}, \textsf{sk}) \leftarrow \textsf{KGen}(1^n)$ and any pair $(K, c) \leftarrow \textsf{Encaps}(\textsf{pk})$ it holds that ${K = \textsf{Decaps}(\textsf{sk}, c)}$.

Definition 16

($\mathsf {IND\text {-}CPA}~ \& ~\textsf{IND}\text {-}\textsf{CCA}~\textsf{KEM}$) For any adversary $\mathcal {A}$ in model $\textsf{Model}\in \{\mathsf {IND\text {-}CPA},\textsf{IND}\text {-}\textsf{CCA}\}$ the advantage against $\textsf{KEM}$ is defined as follows:

where the experiment $\textsf{Model}$ is described below:

3.4 Pseudo-random functions

Definition 17

(Advantage in $\textsf{PRF}$ model) Let $\textsf{F}: \mathcal {K}_{\textsf{F}} \times \mathcal {M}\rightarrow \mathcal {C}$ be a family of keyed functions and $\textsf{Func}(\mathcal {M},\mathcal {C})$ be a set of all functions of the form $\mathcal {M}\rightarrow \mathcal {C}$. The advantage in the $\textsf{PRF}$ model of an adversary $\mathcal {A}$ is defined as follows:

where

Here $\textsf{Func}(\mathcal {M},\mathcal {C})$ is the set of all functions mapping $\mathcal {M}$ to $\mathcal {C}$.

Definition 18

($\textsf{PRF}$) A function $\textsf{F}: \mathcal {K}\times \mathcal {M}\rightarrow \mathcal {C}$ is called pseudorandom if:

• 1. given a key $K \in \mathcal {K}$ and an input $m \in \mathcal {M}$ there is an “efficient” algorithm to compute F(K, m);

• 2. for any polynomial adversary $\mathcal {A}$ and a small predetermined value $\varepsilon$ holds that .

4 Code selection

In this section, we describe the two most promising classes of codes to use in $\textsf{KEM}$.

4.1 Goppa codes

Goppa codes were used in the original versions of the oldest code-based cryptosystems, namely McEliece and Niederreiter ones (more details about them can be found in Sect. 5). Three schemes based on these codes have been presented at the first round of NIST competition: Classic McEliece [6], NTS-KEM [7] and Edon-K [8]. BIG QUAKE [9] uses the subclass of these codes called quasi-cyclic Goppa codes.

The complex structure of Goppa codes keeps these schemes secure whereas changing the code often results in a vulnerability. The codes are considered indistinguishable from random despite the existence of a distinguisher [10] for a particular subclass of these codes. Both decoding and syndrome decoding problems on Goppa codes traditionally are treated as NP-hard similar to random linear codes (despite of the fact it was never proven).

However, the structure of these codes is also one of their shortcomings. The public key of the cryptosystem cannot be represented compactly, therefore it has a huge size. This property critically restricts the applicability of such schemes. In addition, $\textsf{PKE}$s on Goppa codes did not avoid side-channel attacks. Still, all these attacks are based on strong assumptions about the adversary capabilities.

A large class of timing attacks exploited the fact Patterson algorithm works non-constant time [11,12,13,14,15]. Later a power attack of this kind also appeared [16]. As countermeasures, modifications were proposed that introduced additional operations to compensate for optimizations and ensure consistent time complexity in all cases. Another countermeasure is masking [17]. But although it straightforward to prevent the attacks of this class, the modifications slowed down the decoding algorithm. Furthermore, as soon as one vulnerability was fixed, another was found almost immediately. Ultimately, the Patterson algorithm was completely abandoned in favor of the constant-time Berlekamp-Massey algorithm.

A more serious threat is a fault-injection attack from [18] that makes it possible to attack the scheme with the NIST highest security level in several seconds. Although no specific countermeasures are known for the attack, one should keep in mind that it uses laser fault injection, that is, the adversary needs to have access to the device. Another attack [19] becoming possible for the FPGA implementations when the attacker is in possession of the device, uses the leakage of electromagnetic radiation. The attack allows to reveal the secret key even when using the Berlekamp-Massey algorithm.

A generalization of Goppa codes is Srivastava codes (used in DAGS [20] from NIST competition) which, in turn, belong to the class of alternant codes which are a special case of algebraic geometry codes. Another subclass of algebraic geometry codes is generalized Reed-Solomon codes. Since the extension of the code class makes its instances more random-looking it is possible to consider transitioning from schemes based on Goppa codes to schemes based on their generalization or another subclass of algebraic geometry codes. Moreover, both alternate and Reed-Solomon codes have efficient decoding algorithms.

There is a variant of $\textsf{KEM}$ based on generalized Srivastava codes [21]. There have also been two unsuccessful attempts. One is based on generalized Reed-Solomon codes (the RLCE scheme was proposed in the NIST competition [22] and attacked in [23]). The other one is presented in [24] together with an attack on itself. This scheme is based on another specific subclass of algebraic geometry code. Attacks on $\textsf{PKE}$ schemes based on generalized Reed-Solomon codes are also known, see [25, 26].

Thus, the alternatives to Goppa codes mentioned above are promising but poorly studied in terms of their application in cryptography. More research should precede their usage in schemes that are subject to further standardization.

4.2 Quasi-cyclic codes

Cyclic codes are generated by cyclic matrices, i.e. wherein each row is a cyclic shift of the previous row by one position. This particular property enables a cyclic matrix to be described using only n bits, rather than $n^2$ bits, rendering it highly efficient for storage purposes. A generalization of this concept is seen in quasi-cyclic matrices, which are block matrices consisting of cyclic matrix blocks. Although quasi-cyclic matrices are also storage-optimized, they lack the explicit structure exhibited by cyclic matrices.

In the realm of coding theory literature, codes based on specific subclasses of cyclic matrices, such as QC-LDPC (Quasi-Cyclic Low-Density Parity-Check) and QC-MDPC (Quasi-Cyclic Moderate-Density Parity-Check) codes, are frequently employed. Rows of the cyclic submatrices that comprise the generating matrices of these codes have constant weight ($\mathcal {O}(1)$) in the former case and weight bounded by $\mathcal {O}(\sqrt{n\log _2 n})$ in the latter. Each of these types of codes is represented in the NIST competition. HQC [27] and RQC [28] are based, among others, on a quasi-cyclic code (in Hamming and rank metric respectively). BIKE [29] and QC-MDPC [30] use QC-MDPC codes, LEDAkem [31] uses QC-LDPC codes and Lepton [32] uses repetition BCH code that is also quasi-cyclic due to the cyclicality of BCH codes.

Similar to Goppa codes, non-constant decoding time exposes vulnerabilities to timing attacks, such as those observed in schemes on QC-MDPC codes [33, 34], notably the HQC scheme from the first round of the NIST competition [35, 36] and the final versions of HQC and BIKE [37]. Fending off these attacks necessitates the adoption of fully constant-time implementations. Additionally, it is imperative to keep the generation time of a random vector in the encryption algorithm constant.

However, when using quasi-cyclic codes, ensuring constant execution time of the decapsulation algorithm is not enough to ensure security. Another critical concern arises in the form of power analysis and differential power analysis (DPA) attacks, which exploit the analysis of power traces. The proposed cryptanalysis method effectively recovers the complete secret key through a limited number of decryption observations. These attacks consist of a combination of a differential leakage analysis during the syndrome computation followed by an algebraic step that exploits the relation between the public and private key. The applicability of these attacks extends to schemes based on QC-MDPC codes [38,39,40], as well as second-round NIST competition schemes, specifically QC-MDPC $\textsf{KEM}$ (utilizing QC-MDPC codes) and LEDA (using QC-LDPC codes) [41]. However, employing countermeasures such as noise introduction and useless operation incorporation, along with decoding randomization and masking techniques, effectively mitigates all attacks of this this class.

A vulnerability was discovered in the NIST competition Round 2 variant of HQC $\textsf{KEM}$, wherein an attacker could exploit the power consumption patterns of the decoder to expose the secret key [42]. The principle of the attack was to observe and differentiate the power consumption of the decoder depending on whether it corrected an error for a chosen ciphertext. For rare cases when the described approach did not succeed, the authors proposed an adjusted decoding algorithm that incorporated an ISD variant based on side-channel information. It is important to note that the effectiveness of this attack relied on the specific characteristics of BCH codes, which were subsequently replaced within the proposal. However, even for the Round 3 version of HQC a vulnerability of this nature was still present [43]. By leveraging power analysis, an attacker could recover the secret key with an acceptable number of measurements even for the parameter set supposed to provide 256 bits of security.

Subsequently, an efficient reaction attack was built on the QC-MDPC $\textsf{KEM}$ [44] and later a similar attack was devised for the LEDA [45]. In recent theoretical work [46], it was demonstrated that unlike bounded-distance decoders used for algebraic codes such as Goppa ones, iterative decoders used for sparse codes do not have a deterministic decoding radius, and thus the decoding may fail with some probability that is called the decoding failure rate (DFR). Consequently, this parameter is now considered crucial for the code selection and is required not to exceed $2^{-\lambda }$.

Additionally, a notable characteristic of schemes based on quasi-cyclic codes is the reduced complexity of the ISD algorithm. Extensive studies [47] have demonstrated that the work factor of a quasi-cyclic code is equal to the work factor of a random code with equivalent parameters, multiplied by a factor of 1/$\sqrt{N}$. Here, N corresponds to the number of rows in the internal quasi-cyclic submatrix, which denotes the number of repetitions of the same row.

5 Cryptosystems

To of the oldest error-correcting code-based cryptosystems are McEliece [48] and Niederreiter [49] ones. They can be considered fundamental in a sense, as all subsequent variants can be viewed as modifications of either one of these cryptosystems or a combination thereof. That is, Classic McEliece [6] and LEDAkem [31] are built on the original Niederreiter cryptosystem, BIKE [29] and LOCKER [50] use randomized version of this scheme while HQC [27] and RQC [28] use it as one of two basic cryptosystems. At the same time QC-MDPC [30] and Edon-K [8] are built on the McEliece cryptosystem whereas NTS-KEM [7] and DAGS [20] are constructed based on its modification.

The most common alteration is changing the key generation algorithm. It is usually chosen to ensure that the corresponding trapdoor one-way function is difficult for the selected class of codes. Therefore, below we provide only the encryption algorithms of the aforementioned McEliece and Niederreiter cryptosystems, which are more versatile. And we omit the decryption algorithms since they also significantly depend on the chosen code and key generation algorithm.

Both cryptosystems utilize an error vector, which is a vector of length n with a fixed Hamming weight t, where parameter t is small. However, while in the McEliece cryptosystem this vector is chosen uniformly at random from the set of all such vectors $\mathcal {H}_{n,t}$, the Niederreiter cryptosystem employs a specific transformation $\phi$ that maps the message to the error vector. Consequently, the latter cryptosystem is deterministic.

From the above the encryption algorithm of the McEliece cryptosystem transforms a message of length k into a ciphertext of length n (that is $|\mathcal {M}|=2^k$), while the Niederreiter encryption allows obtaining a ciphertext of length $n-k$ from a modified message of length n (and $|\mathcal {M}|=\left( {\begin{array}{c}n\\ t\end{array}}\right)$).

The mapping $\phi$ can be defined in any way, which is usually chosen for best performance characteristics. One way is the following. We divide the original message M into t parts of length $|M_i|$. Then consider each part as the binary representation of the position of “1” in the corresponding block of m. So it is necessary that $|M| \leqslant t\log _2(n/t).$

Moving on to additional properties of $\textsf{PKE}$ we should note that both cryptosystems are $\delta$-correct and $\delta$ is defined by underlying code. For quasi-cyclic codes parameter choices can make this value less than $2^{-\lambda }$. Bounded-distance decoders of Goppa codes provide $\delta =0$. Such schemes are also called perfectly correct.

Rigidity also depends on the code and, moreover, on the specific decoding algorithm. For example, the Niederreiter cryptosystem based on Goppa codes, in which the Berlekamp-Massey algorithm is used for decoding [51], is rigid. This is due to the ability of the decoding algorithm to detect incorrect inputs, i.e. ciphertexts that were not obtained as a result of the encoding algorithm. Such inputs can be decoded into $\bot$, and on the rest the decoding algorithm $\textsf{Dec}(\textsf{sk},c)$ can have the only output. And then from the determinism of the encryption algorithm for this output m holds that $\textsf{Enc}(\textsf{pk},m)=c$.

However, it is impossible to claim rigidity for the Niederreiter cryptosystem in the general case, even when Goppa codes are used. The same is true for the cryptosystem based on quasi-cyclic codes.

For the McEliece cryptosystem, the property is not fulfilled naturally due to the non-determinism of the encryption algorithm.

However, for its deterministic variant (achieved by using the transformation $\textsf{T}$ described further in Sect. 6.2) is proven to be rigid.

Finally the McEliece cryptosystem is $1/\left( {\begin{array}{c}n\\ t\end{array}}\right)$-spread and for the Niederreiter cryptosystem the definition is undefined.

6 Construction of $\textsf{KEM}$

$\textsf{KEM}$ schemes are typically built upon $\textsf{PKE}$ schemes. In these constructions, $\textsf{KGen}$ algorithms usually coincide, except for possibly generating an additional value. Algorithm $\textsf{Encaps}$ incorporates algorithm $\textsf{Enc}$ and algorithm $\textsf{Decaps}$ relies on $\textsf{Dec}$ (see Fig. 1).

Fig. 1

Transformation from $\textsf{PKE}$ to $\textsf{KEM}$

All PKE-to-KEM transformations can be divided into two main classes: security-preserving transformations and security-amplifying transformations. We consider both of them further.

6.1 Security-preserving transformations

Let us introduce here an intuitive way of building $\textsf{KEM}= (\textsf{KGen}, \textsf{Encaps}, \textsf{Decaps})$ scheme based on $\textsf{PKE}= (\textsf{KGen}, \textsf{Enc}, \textsf{Dec})$. Note that key generation algorithms are identical.

Below is the proof of the result, which can be considered folklore.

Theorem 1

For any $\mathsf {IND\text {-}CPA}~(\textsf{IND}\text {-}\textsf{CCA})$ adversary $\mathcal {A}$ against the resulting $\textsf{KEM}$ there exists an $\mathsf {IND\text {-}CPA}~ (\textsf{IND}\text {-}\textsf{CCA})$ adversary $\mathcal {B}$ against the original $\textsf{PKE}$, running in about the same time, such that

Moreover, if $\textsf{IND}\text {-}\textsf{CCA}$ adversary $\mathcal {A}$ was issuing $q_D$ queries to the decapsulation oracle $\textsc {Decaps}$ then $\textsf{IND}\text {-}\textsf{CCA}$ adversary $\mathcal {B}$ issues $q_D$ queries to the decryption oracle $\textsc {Dec}$.

Proof

For the adversary $\mathcal {A}$ that attacks $\textsf{KEM}$ in $\textsf{Model}$ $(\mathsf {IND\text {-}CPA}~\text {or}~\textsf{IND}\text {-}\textsf{CCA})$ the experiment $\textbf{Exp}^0$ coincides with the classical experiment in this model, i.e.

$$\begin{aligned} \mathcal {O}_1 := {\left\{ \begin{array}{ll} - &{} \text {for ~} \mathsf {IND\text {-}CPA}\\ \textsc {Decaps} &{} \text {for ~} \textsf{IND}\text {-}\textsf{CCA}\end{array}\right. } \end{aligned}$$

In the experiment $\textbf{Exp}^1$ the adversary $\mathcal {B}=(\mathcal {B}_1, \mathcal {B}_2)$ attacks $\textsf{PKE}$ encryption schemes in $\textsf{Model}$ $(\mathsf {IND\text {-}CPA}~\text {or}\textsf{IND}\text {-}\textsf{CCA})$. $\mathcal {B}_1$ chooses a pair of messages at random, sends it to $\mathcal {B}_2$ and $\mathcal {B}_2$ calls the adversary $\mathcal {A}$ against $\textsf{KEM}$ in the corresponding model. Then

$$\begin{aligned} \mathcal {O}_2 := {\left\{ \begin{array}{ll} - &{} \text {for ~} \mathsf {IND\text {-}CPA}\\ \textsf{Dec}&{} \text {for ~} \textsf{IND}\text {-}\textsf{CCA}\end{array}\right. } \end{aligned}$$

If $b=1$ then in $\textbf{Exp}^0$ the adversary $\mathcal {A}$ receives the pair $(c_0, K_1^*),$ where $c_0=\textsf{Enc}(\textsf{pk},K_0^*)$, and in $\textbf{Exp}^1$ the adversary $\mathcal {A}$ is given the pair $(c_1, m_0),$ where $c_1=\textsf{Enc}(\textsf{pk},m_1)$. These pairs are identical up to renaming, that is, the probability of correctly guessing $b'=b$ in these cases are equal.

Alternatively, if $b=0$ in $\textbf{Exp}^0$, the adversary $\mathcal {A}$ is provided with the pair $(c_0, K_0^*)$, where $c_0=\textsf{Enc}(\textsf{pk},K_0^*)$. And in $\textbf{Exp}^1$ when $b=0$, the adversary $\mathcal {A}$ receives the pair $(c_0, m_0)$, with $c_0=\textsf{Enc}(\textsf{pk},m_0)$. Again probabilities coincide.

Hence

$$\begin{aligned} \mathbb {P}[\textbf{Exp}^0(\mathcal {A})\Rightarrow 1]=\mathbb {P}[\textbf{Exp}^1(\mathcal {B})\Rightarrow 1], \end{aligned}$$

which implies the condition of the theorem. $\square$

It can be easily shown that both McEliece and Niederreiter cryptosystems provide security only in $\mathsf {OW\text {-}CPA}$ model, but not in $\mathsf {IND\text {-}CPA}$ or $\textsf{IND}\text {-}\textsf{CCA}$ ones. Let us show their insecurity in $\mathsf {IND\text {-}CPA}$ model and then insecurity in $\textsf{IND}\text {-}\textsf{CCA}$ model will follow automatically.

So the fact under consideration is obvious for the Niederreiter cryptosystem as it is deterministic and the test can be easily done by recounting both ciphertexts.

In case of McEliece cryptosystem the adversary aims at distinguishing between messages $m_b, b\in \{0,1\}$ after getting the ciphertext $c'$. Then for each $b' \in \{0,1\}$ it can compute the value $e' = m_{b'}G+c' = m_{b'}G+ m_bG + e_b$, where $e_b$ for $b \in \{0,1\}$ denotes error vectors added in the encryption algorithm of the McEliece cryptosystem. The last step is to check whether $\textrm{wt}(e')=t$. The condition will be obviously fulfilled in case $b=b'$ and with high probability fails otherwise.

That is, in order to obtain an $\textsf{IND}\text {-}\textsf{CCA}$ secure $\textsf{KEM}$ by applying a security-preserving transformation it is necessary to apply another preliminary transformation that firstly increases the $\textsf{PKE}$ security to $\textsf{IND}\text {-}\textsf{CCA}$.

Not many transformations of this type are known, and even fewer of them can be applied to cryptosystems of interest to us. Some can only be applied to cryptosystems whose $\textsf{Enc}$ function is a permutation [52] and some others are applicable to $\mathsf {IND\text {-}CPA}$ secure $\textsf{PKE}$s [53]. But the most suitable ones are based just on an $\mathsf {OW\text {-}CPA}$ secure cryptosystem [54, 55]. One more transformation additionally requires underlying $\textsf{PKE}$ to be not only $\mathsf {OW\text {-}CPA}$ secure, but also $\gamma$-spread [56].

Transformation from $\mathsf {IND\text {-}CPA}$ to $\textsf{IND}\text {-}\textsf{CCA}$ secure $\textsf{PKE}$ consists mainly in binding the error vector to the message via hashing. All cryptosystems after transformation from an $\mathsf {OW\text {-}CPA}$ secure one have extended ciphertexts: some additional information depending on message and randomness is added. The first variant [56] is to encrypt random r and concatenate the result with $c' =\textsf{G}(r)+ m$ where $\textsf{G}$ is a generator of a cryptographically secure pseudo random sequences. One more random value can be used additionally [54], in this case $c'=\textsf{G}(r)+ (m\Vert r_1)$, where $\Vert$ denotes concatenation. To decrease the ciphertext size only some part of $c'$ may be added [55].

Unfortunately, all aforementioned transformations have only asymptotic estimates which makes it impossible to select parameters for real applications. There are also no examples of such transformations usage among NIST proposals.

6.2 Security-amplifying transformations

Security-amplifying transformations can be represented by a family of so-called Fujisaki-Okamoto $(\textsf{FO})$ ones. Though original transformations [53, 57] aimed at conversion from weak $\textsf{PKE}$ to ones secure in $\textsf{IND}\text {-}\textsf{CCA}$ model, this idea was lately developed at conversions from $\textsf{PKE}$ to $\textsf{KEM}$.

The first transformation $\textsf{T}$ determines the scheme and raises security either from $\mathsf {OW\text {-}CPA}$ or from $\mathsf {IND\text {-}CPA}$ to $\mathsf {OW\text {-}PCVA}$ (a stronger version of the $\mathsf {OW\text {-}CPA}$ model [5]). In the first case a rigid cryptosystem is obtained, but in the second one the reduction is tight. The idea is to bind the randomness to the message m by replacing it with its hash value. So, e.g. in McEliece cryptosystem we can use $e = \textsf{G}(m)$ for some special hash-function $\textsf{G}$ with output of certain weight. Note that for Niederreiter cryptosystem, that is deterministic and not $\gamma$-spread, the reduction is trivial.

Next step can be performed by one of the transformations from Fig. 2. They can be grouped according to different properties. First, subscript m indicates that the output key depends only on the message $(K=\textsf{H}(m))$, while its absence means that the key is obtained with additional use of the ciphertext $(K=\textsf{H}(m,c))$ for some hash $\textsf{H}$ with output length $\ell$. Next, schemes marked as $\perp$ are ones with explicit rejection: in case of appearance of symbol $\perp$ inside the $\textsf{Dec}$ algorithm, these algorithms transfer it to the output of $\textsf{Decaps}$ algorithm. Schemes with implicit rejection (marked as $\not \perp$) preventively generate additional randomness in $\textsf{KGen}$ algorithm and use it have a key-like output in $\textsf{Decaps}$. However, in case of the event $\perp$ keys on the two sides will not match. Finally, prefix $\textsf{Q}$ means that additional hash-value $\textsf{H}'(m)$ is counted in $\textsf{Encaps}$ and checked in $\textsf{Decaps}$. Note that the superposition of transformation $\textsf{T}$ and one of transformations from Fig. 2 is usually denoted by $\textsf{FO}$ with the appropriate subscripts.

Fig. 2

Overview of $\textsf{FO}$ transformations

Some of these transformations (namely, $\textsf{U}^{\bot }, \textsf{QU}_m^{\bot }$ and $\textsf{FO}_m^{\bot }$) were proposed by A. Dent in [58]. Afterwords Hofheinz et al. [5] systematized and generalized this approach and provided description of transformations $\textsf{T},\textsf{U}^{\bot }, \textsf{U}^{\not \bot }, \textsf{U}_m^{\bot }$ and $\textsf{U}_m^{\not \bot }$. Both articles present the corresponding security proofs in $\textsf{ROM}$ model (except for transformation $\textsf{U}_m^{\not \bot }$, for which only the concept of proof is given). Further research on the security of transformations $\textsf{U}^{\not \bot }$ and $\textsf{U}_m^{\not \bot }$ in $\textsf{ROM}$ model was presented by D. J. Bernstein and E. Persichetti in [59]. Security of transformation $\textsf{QU}_m^{\not \bot }$ in $\textsf{ROM}$ model has never been studied.

We don’t know anything about the security of transformations $\textsf{QU}^{\bot }$ and $\textsf{QU}^{\not \bot }$ in $\textsf{QROM}$ model. However post-quantum security of other transformations was studied in several articles [5, 60,61,62,63]. Additionally, article [63] establishes the equivalence between transformations $\textsf{U}^{\bot }$ and $\textsf{U}_m^{\bot }$, as well as between transformations $\textsf{U}^{\not \bot }$ and $\textsf{U}_m^{\not \bot }$.

Below we present Tables 1 and 2, which compare the bounds of various $\textsf{FO}$ transformations for Niederreiter and McEliece $\textsf{PKE}$s basing on known results. These comparisons aim to illustrate the process of transforming an $\mathsf {OW\text {-}CPA}$ $\textsf{PKE}$ into an $\textsf{IND}\text {-}\textsf{CCA}$ $\textsf{KEM}$. The tables focus on cryptosystems based on Goppa codes and consider the specific characteristics of both the selected codes and cryptosystems. Consequently, usage of Goppa codes results in ${\delta = 0}$. In addition to that, when the Niederreiter $\textsf{PKE}$ is used, the determining transformation $\textsf{T}$ can often be excluded. It makes the estimates tighter. Nevertheless, the inclusion of this transformation is sometimes imperative to facilitate reduction to an $\mathsf {OW\text {-}CPA}$ $\textsf{PKE}$.

We wish to highlight that according to the remark before Theorem 3.1 in [5] transformation $\textsf{T}$ may result in $\mathsf {OW\text {-}PCA}$ $\textsf{PKE}$ instead of $\mathsf {OW\text {-}PCVA}$. In this case number of queries to Cvo oracle (introduced in the above article) is $q_V = 0$. This fact establishes the estimate for $\textsf{FO}^{\not \bot }$ transformation below: firstly an ${\mathsf {IND--CCA}}$ secure $\textsf{KEM}$ is reduced to an $\mathsf {OW\text {-}PCA}$ secure $\textsf{PKE}$ that is subsequently reduced to an $\mathsf {OW\text {-}CPA}$ secure $\textsf{PKE}$.

The theorem producing reduction for $\textsf{FO}_m^{\not \bot }$ transformation connects $\mathsf {IND--CCA}$ secure $\textsf{KEM}$ and deterministic rigid $\mathsf {OW\text {-}CPA}$ secure $\textsf{PKE}$. But since the adversary’s advantage in $\mathsf {OW\text {-}CPA}$ model doesn’t exceed it’s advantage in $\mathsf {OW\text {-}PCA}$ model, further a known result can be applied that connects an $\mathsf {OW\text {-}PCA}$ secure deterministic rigid $\textsf{PKE}$ and a general-type $\mathsf {OW\text {-}CPA}$ secure $\textsf{PKE}$.

We will upper-bound the security of $\textsf{QFO}_m^{\bot }$ transformation applied to McEliece cryptosystem and $\textsf{QFO}_m^{\not \bot }$ transformation applied to both McEliece and Niederreiter cryptosystems in $\textsf{ROM}$ model by the security of these transformations in $\textsf{QROM}$. Moreover, we will also upper-bound the security of transformation $\textsf{QU}_m^{\bot }$ in $\textsf{QROM}$ model by the security of transformation $\textsf{QFO}_m^{\bot }$ in the same model.

Note that transformations $\textsf{QU}^{\bot }$ and $\textsf{QU}^{\not \bot }$ are excluded from the tables as lacking security in $\textsf{QROM}$ model. Transformations $\textsf{U}^{\bot }$ and $\textsf{U}_m^{\bot }$ are also not presented as no reductions to $\mathsf {OW\text {-}CPA}$ $\textsf{PKE}$ were obtained for them in $\textsf{QROM}$.

Everywhere in the tables q means the total number of the adversary’s queries to various oracles and $\varepsilon$ is the success probability of another adversary against the $\mathsf {OW\text {-}CPA}$ security of the underlying $\textsf{PKE}$. Let us note additionally that some transformations require the underlying $\textsf{PKE}$ to be rigid. Also some proofs are made for modified transformations where the hash-function is replaced with $\textsf{PRF}$ at the implicit rejection step. The results are given up to constants.

Table 1 $\textsf{FO}$ transformations applied to Niederreiter $\textsf{PKE}$ on Goppa codes and resulting in an $\textsf{IND}\text {-}\textsf{CCA}$ secure $\textsf{KEM}$

Table 2 $\textsf{FO}$ transformations applied to McEliece $\textsf{PKE}$ on Goppa codes and resulting in an $\textsf{IND}\text {-}\textsf{CCA}$ secure $\textsf{KEM}$

Those transformations are widely presented at NIST competition. Thus, Classic McEliece [6] uses $\textsf{U}^{\not \bot }$, BIKE [29] uses $\textsf{FO}^{\not \bot }$, DAGS [64] uses $\textsf{QFO}_m^{\bot }$ and HQC, BIG QUAKE [9], RQC [28] and LOCKER [50] use $\textsf{QFO}^{\bot }$ transformation.

7 Notes on best approaches

It can be seen from Tables 1 and 2 that the best security estimates are obtained by the combination of Niederreiter cryptosystem and one of transformations $\textsf{U}^{\not \bot }$ and $\textsf{U}_m^{\not \bot }$. On the whole a rigid Niederreiter $\textsf{PKE}$ provides estimates better than a McEliece one as it doesn’t require additional transformations to be deterministic. That’s why it is possible to avoid accuracy loss associated with using the determining transformation $\textsf{T}$.

As a result, Niederreiter-based schemes require smaller code parameters to achieve the same security level, as the complexity of decoding problems is directly dependent on the code’s length, dimension, and distance. Moreover, Niederreiter $\textsf{PKE}$ has shorter ciphertexts.

Additionally, Sect. 6.1 discusses the advantage of security-amplifying transformations over security-preserving ones. Thus, the two schemes are the most promising among all known variants.

It worth noting that all proofs for transformations $\textsf{U}_m^{\not \bot }$ and $\textsf{FO}_m^{\not \bot }$ and some proofs for $\textsf{U}^{\not \bot }$ in $\textsf{QROM}$ model in articles [60, 62, 63] require the replacement of the function call $\textsf{H}(s,c)$ in the implicit rejection with the output of a pseudorandom function $\textsf{F}(s,c)$. At the same time all proofs that are known for transformation $\textsf{U}_m^{\not \bot }$ in $\textsf{ROM}$ model (see [5, 59]) are given for the basic version presented in Fig. 2.

In article [59] the authors bring up an important problem: theorems are often presented with incomplete or non-rigorous proofs, or sometimes without any at all. We agree that the security notions must be checked as carefully as possible. That’s why we decided to close the gap between proofs in classic and quantum models for the transformation $\textsf{U}_m^{\not \bot }$. The modified $\textsf{KEM}$ obtained by the application of transformation $\textsf{U}_m^{\not \bot }$ to Niederreiter $\textsf{PKE}$ along with its security proof can be found in the next section.

8 Security of $\textsf{U}_m^{\not \bot }$ applied to Niederreiter $\textsf{PKE}$

The goal of the section is to unify the specification of the transformation $\textsf{U}_m^{\not \bot }$ by using a pseudorandom function ${\textsf{F}: \mathcal {K}_{\textsf{F}}\times \mathcal {C}\rightarrow \mathcal {K}}$ for the implicit rejection. Here $\mathcal {C}$ is the set of all possible outputs of function $\textsf{Enc}$.

Note that from this approach it follows that the secret s is chosen from the set $\mathcal {K}_{\textsf{F}}$.

The listing of the obtained scheme, that is further referred as $\widetilde{\textsf{KEM}}$, can be found below. Here $\textsf{KGen}'$ is the key generation algorithm of the underlying Niederreiter cryptosystem.

We now present the security notions for our $\textsf{KEM}$ both in $\textsf{ROM}$ and $\textsf{QROM}$ models.

The first one follows the approach of the paper [5], which however lacks the proof of security of transformation $\textsf{U}_m^{\not \bot }$. Additional changes arise from the properties of the chosen cryptosystem as well as the introduction of a pseudorandom function $\textsf{F}$. So it is the first complete proof for the proposed scheme.

Theorem 2

Assume Niederreiter $\textsf{PKE}$ to be rigid. For any $\textsf{IND}\text {-}\textsf{CCA}$ adversary $\mathcal {B}$ against $\widetilde{\textsf{KEM}}$ issuing at most $q_D$ queries to the decapsulation oracle $\textsc {Decaps}$, and at most $q_H$ queries to the random oracle $\textsf{H}$, there exist an $\mathsf {OW\text {-}CPA}$ adversary $\mathcal {A}$ against Niederreiter $\textsf{PKE}$ and an adversary $\mathcal {A}'$ against the security of $\textsf{PRF}~\textsf{F}$ with at most $q_D$ quires such that

and adversaries $\mathcal {A}$ and $\mathcal {A}'$ are running in about the same time and resources as $\mathcal {B}$.

Proof

Let $\mathcal {B}$ be an adversary against the $\textsf{IND}\text {-}\textsf{CCA}$ security of $\widetilde{\textsf{KEM}}$, issuing at most $q_D$ queries to the oracle $\textsc {Decaps}$.

The experiment $\textbf{Exp}^0$ is the original $\textsf{IND}\text {-}\textsf{CCA}$ experiment with so-called lazy sampling technique. The idea is to explicitly reflect the nature of the random oracle $\textsf{H}$: on a new query it outputs a random value, but on a repeated one it outputs the same value as before. To achieve this, the set $\Pi ^H$ is introduced to store the requests and answers for all previous queries made to $\textsf{H}$ so far.

Thus for $\textbf{Exp}^0$ holds that

In $\textbf{Exp}^1$ pseudorandom function $\textsf{F}(s,c)$ is replaced by $\textsf{H}'(c)$, where $\textsf{H}'$ is an independent internal random oracle that cannot be accessed by $\mathcal {B}$. This changes the $\textsc {Decaps}$ oracle, but the rest of the experiment remains unchanged.

We construct a $\textsf{PRF}$-adversary $\mathcal {A}'$ which replaces its calls to $\textsf{F}$ by calls to its oracle, runs $\mathcal {B}$, and outputs 1 if $\mathcal {B}$ wins and 0 otherwise. Now the task of distinguishing experiments $\textbf{Exp}^0$ and $\textbf{Exp}^1$ precisely coincides with the experiment $\textsf{PRF}$ of the adversary $\mathcal {A}'$ with $q_D$ queries, that is,

In $\textbf{Exp}^2$ the set $\Pi ^D$ is introduced. It contains the requests and answers of the oracle $\textsc {Decaps}$. Also oracles $\textsf{H}$ and $\textsc {Decaps}$ are modified such that they make no use of the secret key any longer.

In $\textbf{Exp}^1$ for all correct ciphertexts c holds that $\textsc {Decaps}(c) = \textsf{H}(\textsf{Dec}(\textsf{sk},c)).$ Now we show that the changes did not spoil this rule. First, note that both experiments return some random value if $\textsf{Dec}(\textsf{sk}, c) = \bot$. Another note is that that there couldn’t be the pair (c, K) in the set $\Pi ^D$ before either the first query on c to the oracle $\textsc {Decaps}$ or the query on $m':=\textsf{Dec}(\textsf{sk},c)$ to the oracle $\textsf{H}$.

Now let us analyze two cases separately: in the first one the adversary $\mathcal {B}$ first queries $\textsf{H}$ on $m'$ and then queries $\textsc {Decaps}$ on c, in the second one it reverses the queries. If $\textsf{H}$ is queried on $m'$ first, at the very moment the pair $(m', K)$ for $K \rightarrow \$\mathcal {K}$ is added to $\Pi ^H$ and the pair $(c':=\textsf{Enc}(\textsf{pk},m'),K)$ is added to $\Pi ^D$. As $\textsf{PKE}$ is rigid it holds that $c'=c$ and hence $\textsc {Decaps}(c)=K=\textsf{H}(m').$ If $\textsc {Decaps}$ is queried on c first, the pair (c, K) for $K \rightarrow \$\mathcal {K}$ is added to $\Pi ^D$ and this sets $\textsc {Decaps}(c)=K$. Thus, when $\textsf{H}$ is queried on $m'$ afterwards, the condition on the line 5 of listing of $\textsf{H}$ will be satisfied and then the pair $(m',K)$ will be added to $\Pi ^H$ wherefore $K=\textsf{H}(m').$

Consequently we have

$$\begin{aligned} \mathbb {P}[\textbf{Exp}^2(\mathcal {B})\Rightarrow 1]=\mathbb {P}[\textbf{Exp}^1(\mathcal {B})\Rightarrow 1]. \end{aligned}$$

Finally, the experiment $\textbf{Exp}^3$ differs from experiment $\textbf{Exp}^2$ in that it immediately aborts (with uniformly random output) after $\mathcal {B}$’s query to $\textsf{H}$ on $m^*$.

We denote the event that the corresponding condition from the line 1 of listing of $\textsf{H}$ is fulfilled by $\textsf{CHAL}$. Then

$$\begin{aligned} \left| \mathbb {P}[\textbf{Exp}^3(\mathcal {B})\Rightarrow 1]-\mathbb {P}[\textbf{Exp}^2(\mathcal {B})\Rightarrow 1] \right| \leqslant \mathbb {P}[\textsf{CHAL}]. \end{aligned}$$

So in $\textbf{Exp}^3$ we avoid the adversary from asking the oracle $\textsf{H}$ queries on $m^*$. As queries to Decaps on $c^*$ are excluded by definition, $\mathcal {B}$ has no ability to get any information about $\textsf{H}(m^*)$ and we can claim bit b is independent from $\mathcal {B}$’s view. This gives us

$$\begin{aligned} \mathbb {P}[\textbf{Exp}^3(\mathcal {B}) \Rightarrow 1] = \frac{1}{2}. \end{aligned}$$

Let us construct the adversary $\mathcal {A}$ against Niederreiter cryptosystem in the $\mathsf {OW\text {-}CPA}$ model that simulates $\textbf{Exp}^3$ for the adversary $\mathcal {B}$.

This simulation is perfect if $\textsf{CHAL}$ doesn’t occur. If it does, then the message $m^*$, corresponding to the ciphertet $c^*$, is correctly processed and holds $(m^*,K')\in \Pi ^H$ for some $K'$. Note that, since $\textsf{PKE}$ is deterministic, $m^*$ always follows $\textsf{Enc}(\textsf{pk},m^*)=c^*$ that is condition on the line 4 of listing of $\mathcal {A}$ is fulfilled. Hence,

The statement of the theorem is obtained by collecting the probabilities. $\square$

Further we state the theorem on the security of $\widetilde{\textsf{KEM}}$ in $\textsf{QROM}$ without proof, since it follows right from Theorem 2 (the bound for $\textsf{U}^{\not \bot }$ transformation) and Theorem 5 (the equivalence of bounds for $\textsf{U}^{\not \bot }$ and $\textsf{U}_m^{\not \bot }$ transformations) from the article [63]. It is also useful to mention that the perfect correctness implies zero advantage in “finding failing ciphertexts” experiment set in [63, Definition 3]. And, finally, being deterministic the Niederreiter cryptosystem is 0-injective [63, Definition 6]. Putting together all the comments we claim Theorem 3.

Theorem 3

Assume Niederreiter $\textsf{PKE}$ to be perfectly correct. For any $\textsf{IND}\text {-}\textsf{CCA}$ adversary $\mathcal {B}$ against $\widetilde{\textsf{KEM}}$, issuing at most $q_D$ queries to the decapsulation oracle $\textsc {Decaps}$ and at most $q_H$ quantum queries to the random oracle $\textsf{H}$, there exist an $\mathsf {OW\text {-}CPA}$ adversary $\mathcal {A}$ against Niederreiter $\textsf{PKE}$ and an adversary $\mathcal {A}'$ against the security of $\textsf{PRF}~\textsf{F}$ with at most $q_D$ quires such that

and adversaries $\mathcal {A}$ and $\mathcal {A}'$ are running in about the same time and resources as $\mathcal {B}$.

9 Discussion

Further investigation is required to determine the most suitable code for the proposed scheme. Despite the fact that, based on a preliminary analysis, we have so far proposed using Goppa codes known to be the basis of secure and perfectly correct cryptosystems, this option may not be final. Alternative variants such as quasi-cyclic Goppa codes or subcodes of algebraic geometry codes should also be considered. However, a thorough assessment of the security of these codes is necessary. It is important to note that the selection of the code will have a direct impact on the scheme’s parameters and performance characteristics in future applications.

10 Conclusion

In this article, we gathered fundamental questions that need to be addressed by anyone considering synthesizing $\textsf{KEM}$ based on error-correcting codes. We described the most well-known code-based cryptosystems, along with their advantages and disadvantages, and discussed approaches that enable to transform these cryptosystems into secure $\textsf{KEM}$s. Furthermore, we explored the features of schemes depending on different classes of codes. Additionally, we specified two best options to construct a scheme with the best security estimates and for one of them provided a proof of security in $\textsf{ROM}$ model and a statement of security in $\textsf{QROM}$ model.

This work was driven by the observation that there is currently a significant number of proposals emerging worldwide due to the ongoing standardization process of $\textsf{KEM}$s. However, these proposals often lack the rationale of choosing one solution over another. We believe it is valuable to consolidate all the discussions on this topic into a single resource, allowing researchers to use this article as a reference for synthesizing such schemes. In addition, this work can serve as a foundation for a code-based $\textsf{KEM}$ standard in Russia.