LEDAkem: a post-quantum key encapsulation mechanism based on QC-LDPC codes
Marco Baldi Alessandro Barenghi Franco Chiaraluce Gerardo Pelosi Paolo Santini
cs.CR cs.IT math.IT


















M. Baldi A. Barenghi F. Chiaraluce G. Pelosi P. Santini





Università Politecnica delle Marche, Ancona, Italy



Politecnico di Milano, Milano, Italy











: a post-quantum key encapsulation mechanism based on QC-LDPC codes
    Marco Baldi1 Alessandro Barenghi2 Franco Chiaraluce1, 

Gerardo Pelosi2 Paolo Santini1

    December 30, 2023
===========================================================================================





This work presents a new code-based key encapsulation mechanism (KEM) called .
It is built on the Niederreiter cryptosystem and relies on quasi-cyclic low-density parity-check codes as 
secret codes, providing high decoding speeds and compact keypairs. 
 uses ephemeral keys to foil known statistical attacks, 
and takes advantage of a new decoding algorithm that provides faster decoding 
than the classical bit-flipping decoder commonly adopted in this kind of systems.
The main attacks against  are investigated, taking into account quantum speedups.
Some instances of  are designed to achieve different security levels against classical and quantum computers.
Some performance figures obtained through an efficient C99 implementation of  are provided.







§ INTRODUCTION


Devising efficient and robust post-quantum key encapsulation mechanisms (KEMs)KEM is an important and urgent research target, as also witnessed by the recent NIST call for post-quantum cryptographic systems <cit.>.
Code-basedcryptosystems are among the most promising candidates to replace quantum-vulnerable primitives which are still relying on the hardness of the integer factorization or discrete logarithm problems, such as the Diffie-Hellman key exchange and the RSA and ElGamal cryptosystems.
Indeed, Shor's algorithm <cit.> can be used to solve both the integer 
factorization and the discrete logarithm problems in polynomial time with a quantum computer.
One of the problems for which no known polynomial time algorithm on a quantum computer exists is the decoding of a general linear code.
Indeed, such a problem belongs to the non deterministic-polynomial (NP)-complete computational equivalence class <cit.>, which is widely believed to contain problems which have no polynomial time solution on a quantum computer.

The first code-based public-key cryptosystem relying on the general linear code decoding problem was proposed by McEliece in 1978 <cit.>, and used Goppa codes <cit.> to form the secret key.
Such a choice yields large public keys, which is the main limitation of Goppa code-based systems.
The Niederreiter cryptosystem <cit.> is a code-based cryptosystem exploiting the same trapdoor, but using syndromes and parity-check matrices instead of codewords 
and generator matrices as in McEliece.
When the same family of codes is used, Niederreiter and McEliece 
are equivalent <cit.> and therefore they achieve the same security levels.

Replacing Goppa codes with other families of more structured codes may reduce the public key size.
However, this may also compromise the system security, as it occurred with some first McEliece variants based on QC codes <cit.>, LDPC codes <cit.> and QC-LDPC codes <cit.>, QD codes <cit.>, convolutional codes <cit.> and some instances based on GRS codes <cit.>.
Nevertheless, some variants exploiting QC-LDPC and QC-MDPC codes <cit.> have been shown to be able to achieve very compact keys without endangering security.

Recently, some new statistical attacks have been developed that exploit the information coming from decryption failures in QC-LDPC and QC-MDPC code-based systems to perform key recovery attacks, thus forcing to renew keys frequently in these systems <cit.>.

In this paper, we start from the QC-LDPC code-based system proposed in <cit.> and we develop a new KEM based on the the Niederreiter cryptosystem.
We also introduce an improved decoding algorithm which exploits correlation among intentional errors seen by the private code. This way, the correction capability of the private code is exploited to the utmost, thus allowing to achieve significant reductions in the public key size.
We call the new system  and study its properties and security.
We take into account the fact that Grover's algorithm running on a quantum computer may be exploited to speedup attacks based on ISD <cit.>, and we propose some sets of parameters for  achieving different security levels against attacks exploiting both classical and quantum computers.
We also describe an optimized software implementation of the proposed system and provide and discuss some performance figures.
 currently is one of the first round candidate algorithms of the NIST 
post-quantum cryptography standardization project <cit.>, along with other 
code-based KEM. In this work we will highlight the differences between our proposal
and the closest one among the others, i.e. BIKE <cit.>, which relies on QC-MDPC
codes for its construction.

The organization of the paper is as follows. In Section <ref> we 
describe . In Section <ref> we present its security 
analysis and in Section <ref> its peculiar features. In 
Section <ref> we discuss some implementation issues and we show some 
numerical results. Finally, some conclusions are drawn in Section <ref>.



§ THE  CRYPTOSYSTEM



The  cryptosystem is derived from the Niederreiter cryptosystem with the following main differences:


  * Non-algebraic codes known as QC-LDPC codes are used as secret codes.

  * The public code is neither coincident with nor equivalent to the private code.

  * Suitably designed iterative non-bounded-distance decoding algorithms are used.


The motivation for using QC-LDPC codes as private codes is in the fact that 
these such codes are known to achieve important reductions in the public key size when 
used in this context <cit.>.
Moreover, when LDPC codes are used as private codes, the public code cannot 
be either coincident with or equivalent to the private code.
Indeed, in such a case, an attacker could search for low weight codewords in the 
dual of the public code and find a sparse parity-check matrix of the private 
code which allows efficient decoding.

For this reason, following <cit.>,  uses a transformation 
matrix Q that hides the sparse parity-check matrix H of the private code 
into a denser parity-check matrix L = HQ of the public code.
This also affects the error vector that must be corrected during decryption, 
which is obtained from the error vector used during encryption through 
multiplication by Q.
In this work, we show how it is possible to exploit the knowledge of Q 
to design an ad-hoc decoding algorithm achieving very good performance in terms 
of both decoding speed and DFR.

In fact, a well-known feature of LDPC coding is that the decoding radius of iterative decoders is not sharp and cannot be estimated in a deterministic way.
It follows that some residual DFR must be tolerated, and it must be estimated heuristically through Montecarlo simulations.
This is done for all the proposed instances of  in order to guarantee that they achieve a sufficiently low DFR.
Providing quantitative estimates of the DFR for the proposed instances
of  allows us to prevent attacks such as the ones described in <cit.>
changing the key either at each round of the KEM, or before a sufficient amount of decoding failures are observed by the attacker.



 §.§ Coding background


A QC code is defined as a linear block code with dimension k=p k_0 
and length n=p n_0, in which each cyclic shift of a codeword by n_0 
symbols results in another valid codeword.
It follows from their definition that QC codes have generator and 
parity-check matrices in “blocks circulant” form or, equivalently, in “circulants block” form.
The latter is used in . 
A v× v circulant matrix A has the following form

    A = [[   a_0   a_1   a_2     ⋯ a_v-1; a_v-1   a_0   a_1     ⋯ a_v-2; a_v-2 a_v-1   a_0     ⋯ a_v-3;     ⋮     ⋮     ⋮     ⋱     ⋮;   a_1   a_2   a_3     ⋯   a_0 ]].

According to its definition, any circulant matrix is regular, since all its rows
and columns are cyclic shifts of the first row and column, respectively.

The set of v× v binary circulant matrices forms an algebraic ring under
the standard operations of modulo-2 matrix addition and multiplication.
The zero element is the all-zero matrix, and the identity element is the v× v identity matrix.
The algebra of the polynomial ring 𝔽_2[x]/⟨ x^v +1 ⟩ is isomorphic to the ring of v× v circulant matrices over 𝔽_2 with the following map

    A ↔ a(x)=∑_i=0^v-1a_i x^i.

According to (<ref>), any binary circulant matrix is associated to 
a polynomial in the variable x having coefficients over 𝔽_2 which coincide with the entries of the first row of the matrix

    a(x)=a_0+a_1x+a_2x^2+a_3x^3+⋯+a_v-1x^v-1.

According to (<ref>), the
all-zero circulant matrix corresponds to the null polynomial and the identity 
matrix to the unitary polynomial.
The ring of polynomials 𝔽_2[x]/⟨ x^v +1 ⟩ includes 
elements that are zero divisors which are mapped to singular circulant matrices 
over 𝔽_2.
Avoiding such matrices is important in some parts of , and smart ways 
exist to design non-singular circulant matrices.
As it will be described next, the main part of the secret key of  is 
formed by a binary QC-LDPC code described through its parity-check matrix 
H.
Let n denote the code length in bits and k denote the code dimension in 
bits, then H has size (n-k) × n = r × n, where r is the code redundancy.



 §.§ Description of the primitives


The main functions of  are described next.



  §.§.§ Key generation. 


Both private and public keys consist of binary matrices.
These matrices, in their turn, are formed by p × p circulant blocks, being p an integer properly chosen.



  
Secret key.

The key generation input is formed by:


  * The circulant block size p (usually in the order of some thousands bits).

  * The integer n_0 (usually between 2 and 4), representing the number of circulant blocks forming the matrix H.

  * The integer d_v, representing the row/column weight (usually between 15 and 25) of the circulant blocks forming the matrix H.

  * The vector of integers m̅ = [m_0, m_1, …, m_n_0-1], representing the row/column weights (each entry usually smaller than 10) of the circulant blocks forming the matrix Q (the structure of Q is clarified below).

Given these inputs, the secret key is obtained as follows.

First, n_0 sparse circulant matrices with size p × p are generated at random.
Each of them has row/column weight d_v.
We denote such matrices as H_0, H_1, …, H_n_0-1.
The secret low-density parity-check matrix H is then obtained as

    H = [H_0 | H_1 | H_2 | … | H_n_0-1].


The size of H is p × n_0 p.
Other n_0^2 sparse circulant blocks Q_i,j are then randomly generated to form the secret sparse matrix

    Q = [
    [         Q_0,0         Q_0,1             …     Q_0,n_0-1;         Q_1,0         Q_1,1             …     Q_1,n_0-1;             ⋮             ⋮             ⋱             ⋮;     Q_n_0-1,0     Q_n_0-1,1             … Q_n_0-1,n_0-1;               ]].

The row/column weight of each block Q_i,j is fixed according to the following matrix:

    w(Q) = [
    [     m_0     m_1       … m_n_0-1; m_n_0-1     m_0       … m_n_0-2;       ⋮       ⋮       ⋱       ⋮;     m_1 m_n_0-1       …     m_0;         ]],

such that each row and each column of Q has weight m = ∑_i=0^n_0-1m_i.

The choice of the weights m̅=[m_0,m_1,⋯, m_n_0-1] and the size p 
of the circulant blocks composing it is very important since it allows to 
discern if Q is invertible or not. 
In particular, denoting with Π{·} the permanent of 
a matrix, the following theorem holds.

Let p>2 be a prime such that 
ord_p(2) = p-1 and Q be an n_0× n_0 matrix of elements in 
𝔽_2[x]/⟨ x^p+1⟩; 
if Π{w(Q)} is odd and Π{w(Q)}<p, 
then Q is non singular. 


Omitted for the sake of brevity.

With this result, we can guarantee that, when the sequence m̅ is properly 
chosen, the matrix Q is always non singular, which is a necessary condition for 
the key generation process to be successful.


The SK of  is formed by {H, Q}.


Since both H and Q are formed by sparse circulant blocks, it is convenient to 
represent each of these blocks through the indexes of the symbols 1 in their 
first row, i.e. adopt a sparse representation for them.
Each index of this type requires ⌈log_2(p) ⌉ bits to 
be stored.
If we consider that the circulant blocks in any block row of Q have overall 
weight m = ∑_i=0^n_0-1m_i, the size of SK in bits is

    S_sk = n_0 (d_v + m )  ⌈log_2(p) ⌉.


In practice, the secret matrices are generated through a DRBG, seeded with 
a bit string extracted from a TRNG. 
In this case, to obtain H and Q it is sufficient to know the TRNG 
extracted seed of the DRBG that has been used to generate the positions of 
their non-null coefficients, since this process is rather fast.
This approach allows reducing the size of the secret key to the minimum required,
as it is assumed that the TRNG output cannot be compressed.
The entity of the reduction depends on the values of the parameters involved in 
(<ref>).


  
Public key.

Starting from H and Q, the following binary matrices are computed.
First of all, the matrix L is obtained as

    L = HQ = [L_0 | L_1 | L_2 | … | L_n_0-1].


If both d_v and m are odd, then L_n_0-1 has full-rank.
In fact, L_n_0-1=∑_i=0^n_0-1H_iQ_i,n_0-1 and has weight equal 
to md_v-2c (where c is the number of cancellations occurred in the product).
It is possible to demonstrate that if md_v is odd and md_v<p then 
L_n_0-1 is non-singular.


After inverting L_n_0, the following matrix is computed:

    M = L_n_0-1^-1 L = [M_0 | M_1 | M_2 | … | M_n_0-2 | I ] = [M_l | I ].



The PK of  is formed by M_l = [M_0 | M_1 . .| M_2 | … | M_n_0-2].


Since the circulant blocks forming M_l are dense, it is convenient to store 
them through the binary representation of their first row (the other rows are 
then obtained as cyclic shifts of the first row).
The bit-size of the PK hence is

    S_pk = (n_0-1) p.




  §.§.§ Encryption. 


The plaintext of  is an ephemeral random secret generated by Bob
who is willing to share it with Alice.
The encryption inputs are:


  * The values of n_0 and p, from which n = n_0 p is computed.

  * The number of intentional errors t ≪ n.


Bob generates a secret in the form of a random binary vector e with length of 
n = n_0p bits and Hamming weight t.
Given a KDF, the shared secret key k_s is generated from e as 
k_s =  KDF(e). 
In order to encapsulate the shared secret e, Bob fetches Alice's PK 
M_l and computes s = [M_l | I ] e^T
where ^T denotes matrix transposition. The p × 1 syndrome vector s 
representing the encapsulated secret is then sent to Alice.



  §.§.§ Decryption. 


In order to perform decryption, Alice must recover e from s.
The latter can be written as s = M e^T = L_n_0-1^-1 L e^T = L_n_0-1^-1 H Q e^T.
The first decryption step for Alice is computing s' = L_n_0-1 s = H Q e^T.
For this purpose, Alice needs to know L_n_0-1 that, 
according to (<ref>), is the last circulant block of the matrix HQ. 
Hence, it can be easily computed from the SK which contains both H and Q.
If we define the expanded error vector as

    e' = e Q^T,

then we have s' = H e'^T.
Hence, QC-LDPC decoding through H can be exploited for recovering e' 
from s'. QC-LDPC decoders are not bounded distance decoders, and some 
DFR must be tolerated.
However, the system parameters can be chosen such that the DFR is 
acceptably small.
For this purpose, the average decoding radius of the private code must be 
sufficiently larger than the Hamming weight of e', which is approximately 
equal to mt (due to the sparsity of Q and e).
Then, multiplication by (Q^T)^-1 would be needed to obtain e 
from e', that is,

    e = e' (Q^T)^-1.


However, by exploiting the efficient decoding algorithm described in Section <ref>, this last step can be avoided, which also allows avoiding the computation and storage of (Q^T)^-1 as part of the 
secret key.
In fact, the decoding algorithm described in Section <ref> allows recovering e directly by performing decoding of s' = L_n_0-1 s = H Q e^T 
through H, while taking into account the effect of the multiplication of e by Q.
Then, the secret key is recovered as k_s =  KDF(e).

In case a decoding error occurs, the decryption procedure derives the shared secret combining with a KDF the syndrome with a secret constant, which may be derived via a PRNG from the secret key material <cit.>. Alternatively, using a secret permutation of the syndrome as input to the KDF was noted to be effective in <cit.>. Such an approach which is beneficial from the security standpoint in case of an accidental keypair reuse. More details concerning this aspect, which is related to formal security of , will be given in Section <ref>.
According to this approach, Bob will become aware of the decoding failure upon reception of the message sent by Alice encrypted with the incorrectly derived shared secret.



 §.§ Efficient decoding 


Classical BF decoding works as follows.
At each iteration, for each codeword bit position, the number of unsatisfied 
parity-check equations is computed, and if this number equals or exceeds a given 
threshold, then that bit is flipped.
The decision threshold can be chosen in many ways, affecting the decoder 
performance, and it can be fixed or it can vary during iterations.
A choice that often turns out to be optimal is to fix the threshold, at each 
iteration, as the maximum number of unsatisfied parity-check equations in which 
any codeword bit is involved.
In fact, a codeword bit participating in a higher number of unsatisfied 
parity-check equations can be considered less reliable than a codeword bit 
participating in a smaller number of unsatisfied parity-check equations.
So, if the threshold is chosen in this way, the bits that are flipped are those 
that are most likely affected by errors.

Starting from classical BF, we have developed an improved decoder that is 
specifically designed for , where the position of the ones in the 
expanded error vector e' to be corrected is influenced by the value of Q^T, 
as e' is equivalent to a random error vector e with weight t multiplied by 
Q^T.
Since this improved decoder takes into account such a multiplication by the 
transpose of matrix Q to estimate with greater efficiency
the locations of the bits of the expanded error vector, we denote it as 
Q-decoder.

Inputs of the decoder are the syndrome s' and 
the matrices H and Q according to (<ref>) and (<ref>), 
respectively. 
The output of the decoder is a 1 × n vector ê or a decoding 
failure, where ê represents the decoder estimate of the error vector 
e appearing in the equality s'= H Q e^T.
The decoding process performs a maximum of l_max iterations, where the l-th iteration processes s^(l-1) and ê^(l-1) (that is the values at the previous iteration) and outputs s^(l) and 
ê^(l).
A threshold criterion is adopted to compute the positions in ê^(l) that must be changed.
The threshold values b^(l) can be chosen in different ways and affect the decoder performance. In the next section we describe a simple and effective procedure to design such values.
The decoder initialization is performed by setting s^(0)= s'^T and 
ê^(0)=0_n, where 0_n is the length-n vector with all-zero entries.
It is important to note that s^(0) (and, by extension, s^(l)) is a row vector. Moreover, let us consider that all multiplications are binary, expect those denoted with `*', which are performed in the integer domain ℤ. The l-th iteration of the Q-decoder performs the following operations:


  * Compute Σ^(l)=[σ_1^(l),σ_2^(l),⋯,σ_n^(l)]=s^(l-1)* H, resulting in a vector of integers having entries between 0 and d_v.

  * Compute R^(l)=[ρ_1^(l),ρ_2^(l),⋯,ρ_n^(l)]=Σ^(l) * Q.

  * Define ^(l)={v ∈ [1,n]| ρ^(l)_v≥ b^(l)}.

  * Update ê^(l-1) as


ê^(l)=ê^(l-1)+1_^(l)


where 1_^(l) is a length-n binary vector with all-zero entries, except those indexed by ^(l).

  * Update the syndrome as


s^(l)=s^(l-1)+∑_v∈^(l)q_v H^T


where q_v is the v-th row of Q^T.

  * If the weight of s^(l) is zero then stop decoding and return ê^(l).

  * If l < l_max then increment l and go back to step i), 
otherwise stop decoding and return a decoding failure. 


As in classical BF, the first step of this algorithm computes the vector Σ^(l). 
Each entry of this vector counts the number of unsatisfied parity-check 
equations corresponding to that bit position, and takes values in 
{0,…, d_v}.
This evaluates the likelihood that the binary element of e' at the same position is equal to one.
Differently from classical BF, in step ii) the correlation R^(l) 
between these likelihoods and the rows of Q^T is computed.
In fact, the expanded error vector e'=eQ^T can be written as the sum of the 
rows of Q^T indexed by the support of e, that is 
e'=∑_j∈Ψ{e}q_j
where Ψ{e} denotes the support of e. 

Since both Q and e are sparse (that is, m,t ≪ n), cancellations between 
ones in the sum are very unlikely.
When the correlation between Σ^(l) and a generic row q_v of Q^T 
is computed, two cases may occur:


  * If v∉Ψ{e}, then it is very likely that q_v has 
a very small number of common ones with all the rows of Q^T forming e',
hence the correlation is small.

  * If v∈Ψ{e}, then q_v is one of the rows of Q^T 
forming e', hence the correlation is large.


The main difference with classical BF is that, while in the latter all 
error positions are considered as independent, the Q-decoder exploits the 
correlation among expanded errors which is present in , since their positions are influenced by Q^T.
This allows achieving important reductions in the number of decoding iterations.
As a further advantage, this decoder allows recovering e, besides e', 
without the need of computing and storing the inverse of the matrix Q^T.
For this purpose, it is sufficient that, at each iteration, the Q-decoder flips the bits of the estimated error vector e that correspond to the correlations values overcoming the threshold.



 §.§ Choice of the Q-decoder decision thresholds



One important aspect affecting performance of the Q-decoder is the choice of the 
threshold values against which the correlation is compared at each iteration.
A natural choice is to set the threshold used at iteration l equal to the maximum value of the correlation R^(l) , that is b^(l)=max_j=1,2,⋯,n{ρ_j^(l)}.
This strategy ensures that only those few bits that have maximum likelihood of 
being affected by errors are flipped during each iteration, thus achieving the 
lowest DFR.
However, such an approach has some drawbacks in terms of complexity, since the computation of 
the maximum correlation requires additional computations with respect to a 
fixed threshold.

Therefore, as in <cit.>, we consider a different strategy, which allows computing the 
threshold values on the basis of the syndrome weight at each iteration.
According to this approach, during an iteration it is sufficient to compute the 
syndrome weight and read the corresponding threshold value from a look-up table.
This strategy still allows to achieve a sufficiently low DFR, while employing
a significantly smaller number of decoding iterations.

Let us consider the l-th iteration of the Q-decoder, and denote by t_l the 
weight of the error vector e^(l) and with t'_l the weight of the 
corresponding expanded error vector e'^(l) = e^(l)Q^T.
Let us introduce the following probabilities <cit.>:

    p_ci(t'_l)    = ∑_j=0, j odd^min[n_0d_v-1,t'_l]n_0d_v-1jn-n_0d_vt'_l-j/n-1t'_l
    
    p_ic(t'_l)    = ∑_j=0, j even^min[n_0d_v-1,t'_l-1]n_0d_v-1jn-n_0d_vt'_l-j-1/n-1t'_l-1

where p_ci(t'_l) is the probability that a codeword bit is error-free and a 
parity-check equation evaluates it to be incorrect, and p_ic(t'_l) is the probability that a codeword bit is error-affected and a 
parity-check equation evaluates it to be correct.
In both these cases, the syndrome bit is equal to 1.
The probability that each syndrome bit is equal to 1 can be therefore computed 
as p_ic(t'_l)+p_ci(t'_l), so the average syndrome weight at iteration l results in

    w_s^(l)=E[wt{s^(l)}]=[p_ic(t'_l)+p_ci(t'_l)]p
  
where wt{·} denotes the Hamming weight.
Since both the parity-check matrix and the error vector are sparse, the 
probability of wt{s^(l)} being significantly different from 
w_s^(l) is negligible.

So, (<ref>) allows predicting the average syndrome weight starting 
from t'_l.
In order to predict how t'_l varies during iterations, let us consider the 
i-th codeword bit and the corresponding correlation value ρ_i^(l) at the l-th
iteration.
The probability that such a codeword bit is affected by an error can be written as

    P{e_i=1|ρ_i^(l)}=P{e_i=1,ρ_i^(l)}/P{ρ_i^(l)}=(1+P{e_i=0,ρ_i^(l)}/P{e_i=1,ρ_i^(l)})^-1

where e_i is the i-th bit of the error vector used during encryption.
After some calculations, we obtain

    P{e_i=1|ρ_i^(l)}=1/1+n-t_l/t_l(p_ci(t_l)/p_ic(t_l))^ρ_i^(l)(1-p_ci(t_l)/1-p_ic(t_l))^md_v-ρ_i^(l)

where p_ci(t_l) and p_ic(t_l) are given in (<ref>), 
with t_l as argument instead of t'_l.

Adding the i-th row of Q^T to the expanded error vector e' is the same as 
flipping the i-th bit of the error vector e.
Hence, we can focus on e and on how its weight t_l changes during decoding 
iterations.
The values of t'_l can be estimated using (<ref>), while, due to sparsity, those of t_l can be estimated as t'_l/m.

The decision to flip the i-th codeword bit is taken when the following 
condition is fulfilled

    P{e_i=1|ρ_i^(l)}>(1+Δ)P{e_i=0|ρ_i^(l)}

where Δ≥ 0 represents a margin that must be chosen taking into account 
the DFR and complexity: increasing Δ decreases the DFR but 
increases the number of decoding iterations.
So, a trade-off value of Δ can be found that allows achieving a 
low DFR while avoiding unnecessary large numbers of iterations.

Since P{e_i=0|ρ_i^(l)}=1-P{e_i=1|ρ_i^(l)}, (<ref>) can be rewritten as

    P{e_i=1|ρ_i^(l)}>1+Δ/2+Δ.

P{e_i=1|ρ_i^(l)} is an increasing function of 
ρ_i^(l), hence the minimum value of ρ_i^(l) such that 
(<ref>) is satisfied can be computed as

    b^(l)=min{ρ_i^(l)∈ [0, md_v],    s.t.   P{e_i=1|ρ_i^(l)}>1+Δ/2+Δ}

and used as the decision threshold at iteration l.

Based on the above considerations, the procedure to compute the decision threshold 
value per each iteration as a function of the syndrome weight can be summarized 
as follows:


  * The syndrome weights corresponding to t'_l=0,m,2m,⋯,mt (which are 
all the possible values of t'_l neglecting cancellations) are computed 
according to (<ref>). These values are denoted as 
{w_s(0), w_s(m), ⋯, w_s(mt)}.

  * At iteration l, given the syndrome weight w̅_̅s̅^(l), the integer 
j∈ [0,t] such that w_s(jm) is as close as possible to w̅_̅s̅^(l) is computed.

  * Consider t_l = j and compute b^(l) according to (<ref>) and 
(<ref>). The value of b^(l), so obtained, is used as the decoding 
threshold for iteration l.


The above procedure can be implemented efficiently by populating a look-up table 
with the pairs { w_j, b_j }, sequentially ordered.
During an iteration, it is enough to compute w̅_̅s̅^(l), search the largest
w_j in the look-up table such that w_j<w̅_̅s̅^(l) and set b^(l)=b_j.

We have observed that, moving from large to smalle values of w_j, the thresholds computed this way firstly exhibit a decreasing trend,
then start to increase.
According to numerical simulations, neglecting the final increase is beneficial 
from the performance standpoint. Therefore, in the look-up table we replace the 
threshold values after the minimum with a constant value equal to the minimum 
itself.


 §.§ Relations with QC-MDPC code-based systems


In , the public code is a QC-MDPC code that admits L=HQ as a valid parity-check matrix. 
However, differently from QC-MDPC code-based schemes, the private code is a QC-LDPC code, which facilitates decoding.
In fact, decoding directly the public QC-MDPC code through classical BF decoders would be a possibility, but the approach we follow is different.
By using the decoding algorithm described in Section <ref>, we decode the private QC-LDPC code, taking into account the correlation introduced in the private error vector due to multiplication by Q^T.
Since the private QC-LDPC matrix is sparser than the QC-MDPC matrix of the public code, this yields lower decoding complexity.

Besides working over different matrices, the main difference between these two decoding algorithms is in the use of integer multiplications in our decoder, while all multiplications are performed over 𝔽_2 in classical BF decoders.
In fact, in our decoder we perform the following operation to compute R^(l)

    R^(l)=s^(l-1) * H * Q= e Q^T H^T * H * Q ≈ e L^T * L

where the last approximation comes from the fact that, for two sparse matrices A and B, we have A · B ≈ A * B.
Thus, we can say that H Q ≈ H * Q.
So, if we consider classical BF decoding working over the matrix L = H Q, the counter vector is computed as

    Σ^(l) = s^(l-1) * L = e L^T * L.




In the Q-decoder, the error vector is updated by summing rows of Q^T, which is equivalent to flipping bits of the public error vector.
Hence, there is a clear analogy between decoding of the private QC-LDPC code through the Q-decoder and decoding of the public QC-MDPC code through a classical BF decoder.
Through numerical simulations we have verified that the two approaches yield comparable performance in the waterfall region.
Performance in the error floor region is instead dominated by the minimum distance of the code over which decoding is performed.
Since QC-LDPC codes have smaller minimum distance than QC-MDPC codes, this reflects into a higher error floor when decoding is performed over the private QC-LDPC code.
However, no error floor has been observed during simulations of  with QC-LDPC decoding, down to a DFR between 10^-9 and 10^-8.
Since this is the working point of the codes we use, in terms of DFR, we can say that the error floor effect, if present, is negligible from our scheme performance standpoint.






§ SECURITY ANALYSIS



 is constructed starting from the computational problem of syndrome decoding, i.e., 
obtaining a bounded weight error vector from a given syndrome and a general 
linear code, which was shown to be NP-complete in <cit.>.
The main difference from the statement of the general hard problem on which
our proposal is built is the nature of the code employed, which is quasi-cyclic
and admits a representation with a low-density parity-check matrix.
To best of our knowledge, there is no superpolynomial advantage in performing syndrome
decoding on QC-LDPC, given our public code representation, either due to the 
quasi-cyclic form of the code or to the low density of its parity matrix.
We point out that the same assumption on the lack of advantage due to the quasi-cyclic structure of a code has also been done in
both the BIKE <cit.> and the BIG QUAKE <cit.> proposals.

With these statements standing, the security analysis of  examines and 
quantifies the effectiveness of the best known attacks detailing the efficiency 
of algorithms running on both classical and quantum computers providing 
non-exponential speedups over an enumerative search for the correct error vector.
We remark that currently no algorithm running on either a classical Turing 
Machine (TM) or a quantum TM provides an exponential speedup in solving the 
computational problem underlying   compared to an exhaustive search 
approach.



 §.§ Analysis of the algorithm with respect to known attacks

As mentioned in the previous sections,  derives from QC-LDPC 
code-based cryptosystems already established in the 
literature <cit.>. 
As proved in <cit.>, in case of using long-term keys, these 
cryptosystems may be subject to reaction attacks that are able to recover the 
secret key by exploiting the inherent non-zero DFR they exhibit and Bob's 
reactions upon decryption failures. 
However, using ephemeral keys prevents the possibility to mount an attack of 
this kind, which requires long statistical evaluations.
Nevertheless, the risks in case of an accidental keypair reuse must be considered, and this will be done in Section <ref>.

A first type of attacks that can be mounted against  are DA 
aimed at performing decoding through the public code representation, without 
knowing the private code representation.
The most powerful algorithms that can be used for this purpose are ISD 
algorithms. These algorithms aim at performing decoding of any linear block 
code by exploiting a general representation of it. ISD algorithms have 
been introduced by Prange <cit.> and subsequently improved by 
Lee-Brickell <cit.>, Leon <cit.> and Stern <cit.>. 
More recently, they have known great advances through modern approaches, also 
exploiting the generalized birthday paradox 
<cit.>. It is possible 
to show that the general decoding problem is equivalent to the problem of finding 
low-weight codewords in a general (random-like) code. 
Therefore, algorithms for searching low-weight codewords can be used as ISD 
algorithms.

The availability of an efficient algorithm to search for low-weight codewords is 
also at the basis of KRA. In  the matrix L=HQ is a valid 
parity-check matrix for the public code. Since L is sparse, by knowing it 
an attacker could separate H from Q and recover the secret key. In order to 
discover L, an attacker must search for its rows in the dual of the public 
code. Due to the sparsity of H and Q, any of these rows has weight in the 
order of n_0 d_v m. The attack can be implemented by exploiting again an efficient 
algorithm for the search of low-weight codewords in linear block codes.

Another potential attack to systems based on QC-LDPC codes is that 
presented in <cit.>. This attack uses a special squaring 
technique and, by extracting the low-weight error vectors, finds low-weight 
codewords more efficiently than with a general ISD algorithm. 
This attack, however, is applicable if and only if p is even.
Therefore, in order to increase the system security it is advisable to choose 
odd values of p.
Choosing p as a prime is an even more conservative choice against 
cryptanalysis exploiting factorization of p.
The value of p in  is chosen in such a way to prevent these attacks.

To estimate complexity of DA and KRA exploiting ISD 
and low-weight codeword searching algorithms, let us define the WF of an 
algorithm as the base-2 logarithm of the average number of binary operations it 
requires to complete its execution successfully.
Let WF(n,k,w) denote the WF of the most efficient algorithm searching 
for codewords of weight w in a code having length n and dimension k.
Such an algorithm can be used to perform ISD with the aim of decrypting a 
 ciphertext without knowing the private key.
In this case, we have n=n_0p, k=(n_0-1)p and w=t. Moreover, due to the 
QC nature of the codes, a speedup in the order of √(p) must be taken 
into account <cit.>.
Hence, the security level against decoding attacks of this type can be computed as

    SL_DA = WF(n_0p,(n_0-1)p,t)/√(p).


Concerning the KRA attack, based on the above considerations we have a 
similar formula, but with different parameters, that is,

    SL_KRA = WF(n_0p,p,n_0 d_v m)/p,

where the speedup factor p is due to the fact that recovering only one out of p sparse rows of L, 
 is enough for the attacker (due to the QC 
structure of L).

According to <cit.>, the most efficient ISD algorithm taking into 
account Grover's algorithm <cit.> running on a quantum computer is 
Stern's algorithm.
Therefore, the post-quantum security levels have been estimated by considering 
the work factor of Stern's algorithm with quantum speedup according to <cit.>.
Instead, with classical computers the most efficient ISD algorithm turns 
out to be the BJMM algorithm in <cit.>. Therefore, the security levels 
against attackers provided with classical computers have been estimated by 
considering the work factor of BJMM in (<ref>) and 
(<ref>). 
We chose to employ the results provided in <cit.> to evaluate
the computational efforts of Stern's variant of the ISD as they provide
exact formulas instead of asymptotic bounds.
However, we note that a recent work <cit.> provides improved asymptotic 
bounds on the computational complexity of quantum ISD for increasing
values of the codeword length n. Deriving from this approach exact values for given parameters set is worth investigating.



 §.§ System parameters

The NIST call for Post-Quantum Cryptography Standardization <cit.> 
defines 5 security categories, numbered from 1 to 5 and characterized by 
increasing strength (see <cit.> for details).
According to this classification, nine instances of  are proposed, grouped in three classes corresponding to different security levels.
The three instances in each class correspond to three values of n_0 (2, 3, 4), 
each one yielding a different balance between performance and public key size.
The parameters of the nine instances of  are reported in 
Table <ref> for the security categories 1, 3 and 5, 
respectively.
In the table, the superscript (pq) denotes that the attack work factor has been 
computed taking into account quantum speedups due to Grover's algorithm, while 
the superscript (cl) denotes that only classical computers have been considered.

For each security category and considered value of n_0, we have fixed a value 
of the parity-check matrix row/column weight d_v in the order of 25 or 
less (that is advisable to have good error correcting capability of the private 
QC-LDPC codes), and we have found the values of p and m that allow satisfying (<ref>) for the target security level.
In fact, the value of m must be chosen such that the dual of the public code, having minimum distance equal to n_0md_v, is robust against KRA based on ISD.
Once n_0 is fixed, we can find many pairs of values m and d_v which satisfy this bound; among these, we have chosen the one having the lowest product md_v, which is a metric affecting the error correcting capability of the private code.

Then, we have found the value of t that allows satisfying (<ref>) 
and checked whether t' = tm errors can be corrected by the private code 
through Q-decoding with a sufficiently low DFR.
Otherwise, we have increased the value of p keeping all the other parameters 
fixed.
Concerning the estimation of the DFR, we have first exploited BF 
asymptotic thresholds <cit.>, and then we have performed Montecarlo 
simulations for each system instance in order to evaluate its DFR.
In all Montecarlo simulations, except the one for the Category 1, n_0=2 parameter
set, we have encountered no errors, so the DFR can 
be approximately bounded by the reciprocal of the number of simulated decryptions.
Concerning the parameter set for Category 1, n_0 = 2, we obtained 20 
failures on 2.394· 10^9 decoding computations, pointing to a DFR ≈ 8.3· 10^-9.
In order to make a conservative design of the system, we have considered some 
margin in the complexity estimates of the attacks, such that the actual security 
level for these instances is larger than the target one.
This also accounts for possible (though rare) cancellations occurring in L, 
which may yield a row weight slightly smaller than m d_v n_0.
The values of d_v have been chosen greater than 15 in order to avoid codes having too small minimum distances.
In addition, they are odd to ensure that the circulant blocks forming H and L 
(and L_n_0-1, in particular) have full rank.
Also the values of m are always odd, and the sets [m_0,m_1,⋯,m_n_0-1] 
have been chosen in such a way to guarantee that Q has full rank.
In fact, L=HQ is a valid parity-check matrix for the public code: if Q is 
singular, it might happen that the rank of L is lower than p, leading to a 
code with a co-dimension lower than p.
With the choice of an invertible Q, we guarantee that this does not occur.






§ PROPERTIES OF THE PROPOSED CRYPTOSYSTEM 



The QC-LDPC code-based Niederreiter cryptosystem alone achieves only IND-CPA, that however is sufficient in case of using ephemeral keys.
It is possible to convert a Niederreiter cryptosystem achieving only IND-CPA into one achieving IND-CCA, under the assumption that the DFR of the underlying code is zero.
Such a conversion involves substituting the outcome of a decoding failure (due to an ill-formed ciphertext) with the outcome of a KDF taking as input either the public syndrome and a fixed secret bit sequence <cit.>, or a secret permutation of the syndrome itself <cit.>.
We apply the conversion specified in <cit.> to our scheme, despite its DFR is not null, as it still proves beneficial in case of an accidental keypair reuse, against an attacker matching the IND-CCA model whenever no decoding failures due to the QC-LDPC code structure takes place.

Furthermore, we note that  ciphertexts are not malleable in a chosen plaintext scenario.
Indeed, even if an attacker alters arbitrarily a ciphertext so that it decrypts to a valid 
error vector e  (e.g., discarding the ciphertext  and 
forging a new one), the shared secret is derived via a hash based KDF, 
which prevents him from controlling the output of the decryption.


  §.§.§ Relations with the security of QC-MDPC code-based systems.

Differently from QC-MDPC code-based systems, the public code in  has a QC-MDPC matrix L that can be factorized into H and Q, and this might appear to yielding lower security than a general QC-MDPC matrix.
However, in order to attempt factorization of L, the attacker should first recover it by searching 
for low-weight codewords in the dual of the public code.
Once L has been recovered, trying to factorize it into H and Q indeed becomes pointless, since 
the attacker could exploit L to perform direct decoding of the public QC-MDPC code.
Alternatively, an attacker could try to perform decoding of the public code, which requires solving the syndrome decoding problem for the same code.
The best known techniques for solving these two problems are based on ISD, and no method is known to facilitate their solution by exploiting the fact that L can be factorized into H and Q.



  §.§.§ Risks in case of keypair reuse.

While  uses ephemeral keys that are meant for single use, 
it is possible that implementation accidents lead to a reuse of the 
same keypair more than once.
The main threat in case of keypair reuse is the reaction attack described 
in <cit.>, where a correlation between the DFR and the private key is derived.
However, for the attack to succeed, the attacker needs to reliably estimate 
the decoding failure rate for a set of carefully crafted or selected error vectors.
Given the DFR for which  was designed (<10^-8), obtaining a 
reliable estimate requires a number of decryptions with the same key in the 
order of billions. Since the said evaluation should be obtained for all the 
possible distances between two set bits in the secret key, a conservative 
estimate of the number of decryption actions required is (p-1) 1/DFR, which, 
considering the weakest case, corresponding to Category 1 with n_0=2,
yields ≳ 2.7 × 10^12 decryptions.
Therefore, the attack presented in <cit.> is not a practical threat 
 on  with the proposed parameters, unless a significant amount of 
 decryptions are performed with the same key.
Moreover, even the CCA described in <cit.>, where a ciphertext
is crafted with a number of errors greater than t to artificially increase the DFR of the system,
can be thwarted through checking the weight of the decoded error vector and reporting 
a decoding failure if it exceeds t.



  §.§.§ Protection against side-channel attacks.

The two most common side channels exploited to breach practical implementations 
of cryptosystems are the execution time of the primitive and the instantaneous 
power consumption during its computation.
In particular, in <cit.>, it was shown how a QC-LDPC code-based 
system can be broken by means of simple power analysis, exploiting the 
control-flow dependent differences of the decoding algorithm.
We note that employing ephemeral keys provides a natural resistance 
against non-profiled power consumption side channel attacks, as a significant 
amount of measurements with the same key (>30) must be collected before the 
key is revealed. 

Concerning execution time side channel information leakage, the main portion of
the  decryption algorithm which is not characterized by a constant execution time is decoding.
Indeed, the number of iterations made by the decoder depends on the values 
being processed.
However, for the proposed parameters, we note that the number of iterations is 
between 3 and 5, with a significant bias towards 4.
Hence, it is simple to achieve a constant time decoding by modifying the 
algorithm so that it always runs for the maximum needed amount of iterations to 
achieve the desired DFR. Such a choice completely eliminates the timing leakage,
albeit trading it off for a performance penalty.




§ IMPLEMENTATION AND NUMERICAL RESULTS



An effort has been made to realize a fast and efficient C99 implementation of  without platform-dependent optimizations, which is publicly available in <cit.>.
To this end, we represented each circulant block as a polynomial in 
𝔽_2[x]/⟨ x^p +1 ⟩ thanks to the isomorphism described in 
Section <ref>.
Consequently, all the involved block circulant matrices are represented as
matrices of polynomials in 𝔽_2[x]/⟨ x^p +1 ⟩.
The polynomials are materialized employing a bit-packed form of their binary
coefficients in all the cases where the number of non null coefficients is high.
In case a polynomial has a low number of non null coefficients with respect to the 
maximum possible, i.e., the circulant matrix is sparse, 
we materialize only the positions of its one coefficients
as integers.

We provide below the results of a set of execution time benchmarks.
The results were obtained measuring the required time for key generation, 
encryption (key encapsulation) and decryption (key decapsulation) as a function 
of the chosen security category and the number of circulant blocks n_0. 
The measurements reported are obtained as the average of 100 executions of the 
reference implementation.
The generated binaries were run on an AMD Ryzen 5 1600 CPU at 3.2 GHz, locking the 
frequency scaling to the top frequency.

Table <ref> reports the running times in terms of
CPU time taken by the process. As it can be noticed, the most computationally
demanding primitive is the key generation, which has more than 80% of its
computation time taken by the execution of a single modular inverse in 
𝔽_2[x]/⟨ x^p+1 ⟩ required to obtain the value of 
L_n_0-1^-1.
The encryption primitive is the fastest among all, and its computation time is
substantially entirely devoted (> 99%) to the n_0-1 polynomial multiplications
performing the encryption.
The decryption primitive computation is dominated by the Q-decoder computation 
(>95% of the time), with a minimal portion taken by the n_0 modular 
multiplications which reconstruct L_n_0-1 and the one to compute
the private syndrome fed into the Q-decoder.

Considering the computational cost of performing a KEM with ephemeral keys, 
the most advantageous choice is to pick n_0=4 for any security level, although
the computational savings are more significant when considering high-security 
parameter choices (Category 3 and 5).



Table <ref> reports the sizes of both the keypairs and the 
encapsulated secrets for .
In particular, regarding the size of the private keys we report
both the size of the stored private key
and the required amount of main memory to store the expanded
key during the decryption phase. 
We note that, for a given security category, increasing the value of n_0
enlarges the public key, as it is constituted of (n_0-1)p bits.
This increase in the size of the public key represents a tradeoff with the
decrease of the size of the ciphertext to be transmitted since it is only 
p bits long, and p decreases if a larger number of blocks is selected, for
a fixed security category.
The size of the derived encapsulated secret is at least 256 bits, in order to
meet the requirement reported in <cit.>.
The shared secret is derived employing the SHA-3 hash function with 
a 256, 384 or 512 bits digest, in order to match the requirements of Categories 1, 3, and 5, respectively.



§ CONCLUSION



We have introduced a post-quantum KEM based on QC-LDPC codes with the following advantages: it is built on an NP-complete problem under reasonable assumptions; it exploits improved BF decoders which are faster than classical BF decoders; it requires compact keypairs (below 23 kiB at most), with minimum size private keys; it needs only addition and multiplication over 𝔽_2[x], and modular inverse over 𝔽_2[x]/⟨ x^p+1 ⟩ besides single-precision integer operations; it is particularly efficient in applying countermeasures against non-profiled power consumption side channel attacks.
As regards implementation, no platform specific optimizations have been exploited, thus we expect these results to be quite consistent across different platforms. On the other hand, starting from this platform-agnostic reference implementation, a number of optimizations can be applied to make  faster.



§ ACKNOWLEDGMENTS

Paolo Santini was partly funded by Namirial SpA.

splncs03

