{'fraction_non_alphanumeric': 0.039936440677966104, 'fraction_numerical': 0.012076271186440678, 'mean_word_length': 4.233967843282203, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Decoding Schemes for the MDPC-McEliece Cryptosystem

Recently, it has been shown how McEliece public-key cryptosystems based on moderate-density parity-check (MDPC) codes allow for very compact keys compared to variants based on other code families. In this paper, classical (iterative) decoding schemes for MPDC codes are considered. The algorithms are analyzed with respect to their error-correction capability as well as their resilience against a recently proposed reaction-based key-recovery attack on a variant of the MDPC-McEliece cryptosystem by Guo, Johansson and Stankovski (GJS). New message-passing decoding algorithms are presented and analyzed. Two proposed decoding algorithms have an improved error-correction performance compared to existing hard-decision decoding schemes and are resilient against the GJS reaction-based attack for an appropriate choice of the algorithm's parameters. Finally, a modified belief propagation decoding algorithm that is resilient against the GJS reaction-based attack is presented.


Introduction
In 1978, Rivest-Shamir-Adleman (RSA) proposed a pubilic-key cryptosystem whose security is based on the hard problem of factoring large integers. Since then, the RSA cryptosystem is used in most state-of-the art communication systems and is included in many communication standards. In 1999, Shor presented a factorization algorithm for quantum computers that is able to factor large integers in polynomial time [1]. Thus, assuming that quantum computer of sufficient scale can be built one day, the RSA cryptosystem can be broken in polynomial time rendering most of today's communication systems insecure. This result gives rise to developing cryptosystems that are post-quantum secure.
In the same year as RSA, McEliece proposed a cryptosystem based on errorcorrecting codes [2]. The security of the scheme relies on the hardness of decoding an unknown linear code and thus is resilient against efficient factorization attacks by quantum algorithms like Shor's algorithm. One drawback of the scheme is the large key size and the rate-loss compared to the RSA cryptosystem. Variants of the McEliece cryptosystem based on different code families were considered in the past (e.g. rank-metric codes [3], random codes [4]). In particular, McEliece cryptosystems based on low-density parity-check (LDPC) allow for very small keys but suffer from feasible attacks on the low-weight dual code due to the sparse parity-check matrix [4]. Variants based on quasi-cyclic (QC)-LDPC codes that use row and column scrambling matrices to increase the density of the public code parity-check matrix [5] allow for structural attacks [6]. The family of moderate-density parity-check (MDPC) codes admit a parity-check matrix of moderate density, 1 yielding codes with large minimum distance [7]. In [8] a McEliece cryptosystem based on QC-MDPC codes that defeats information set decoding attacks on the dual code due to the moderate density parity-check matrix is presented. For a given security level, the QC-MDPC cryptosystem allows for very small key sizes compared to other McEliece variants.
Recently, Guo, Johansson and Stankovski (GJS) presented a reaction-based key-recovery attack on the QC-MDPC system [9]. This attack reveals the paritycheck matrix by observing the decoding failure probability for chosen ciphertexts that are constructed with error patterns which have a specific structure. A modified version of the attack can break a system that uses CCA-2 secure conversions [10].
In this paper we analyze different decoding algorithms for (QC-) MDPC codes with respect to their error-correction capability and their resilience against the GJS attack [9]. In particular, we present novel hard-decision message-passing (MP) algorithms that are resilient against the GJS key-recovery attack from [9] and have an improved error-correction capability compared to existing harddecision decoding schemes. We derive the density evolution (DE) for the novel decoding schemes which allows to predict decoding thresholds as well as to optimize the parameters of the algorithm.
The paper is structured as follows. Section 2 gives basic definitions, describes classical decoding schemes for LDPC/MDPC codes and analyzes their resilience against the GJS attack by simulations. In Section 3 we propose new MP decoding schemes that are able to defeat the GJS attack. To estimate the decoding threshold we perform density evolution analysis of the novel schemes. Finally, Section 4 concludes the paper.

Preliminaries
Denote the binary field by F 2 and let the set of m × n matrices over F 2 be denoted by F m×n . The set of all vectors of length n over F 2 is denoted by F n 2 . Vectors and matrices are denoted by bold lower-case and upper-case letters such as a and A, respectively. A binary circulant matrix A of size Q is a Q × Q matrix with coefficients in F 2 obtained by cyclically shifting its first row a = (a 0 , a 1 , . . . , a Q−1 ) to right, yielding The set of Q × Q circulant matrices together with the matrix multiplication and addition forms a commutative ring and it is isomorphic to the polynomial ring F 2 [X]/ X Q − 1 , +, · . In particular, there is a bijective mapping between a circulant matrix A and a polynomial a(X) = a 0 + a 1 X + . . .
. We indicate the vector of coefficients of a polynomial a(X) as a = (a 0 , a 1 , . . . , a Q−1 ). The weight of a polynomial a(X) is the number of its non-zero coefficients, i.e., it is the Hamming weight of its coefficient vector a.
In the remainder of this paper we use the polynomial representation of circulant matrices to provide an efficient description of the structure of the codes.

QC MDPC-based Cryptosystems
A new variant of the McEliece public-key cryptosystem that is based on QC-MDPC codes was proposed in [8] The QC-MDPC McEliece cryptosystem allows for a very simple description without the need for row and column scrambling matrices. Due to the moderate density of the parity-check matrix, known decoding attacks on the dual code [4] are defeated. The parity-check matrix consists of blocks of Q × Q circulant matrices which allows for very small key sizes due to the compact description of the circulant blocks. A binary MDPC code of length n, dimension k and row weight d c is defined by a binary parity-check matrix H that contains a moderate number of d c ≈ O( n log(n)) ones per row. For n = N 0 Q, dimension k = K 0 Q, redundancy r = n − k = R 0 Q with R 0 = N 0 − K 0 for some integer Q, the parity-check matrix H(X) of a QC-MDPC 2 code in polynomial form is a R 0 × N 0 matrix.
Without loss of generality we consider in the following codes with r = Q (i.e. R 0 = 1). This family of codes covers a wide range of code rates and is of particular interest for cryptographic applications since the parity check matrices 2 As in most of the recent literature on codes constructed from arrays of circulants, we loosely define a code to be QC if there exists a permutation of its coordinates such that the resulting (equivalent) code has the following property: if x is a codeword, then any cyclic shift of x by positions is a codeword. For example, a code admitting a parity-check matrix as an array of R0 × N0 circulants does not fulfill the property above. However the code is QC in the loose sense, since it is possible to permute its coordinates to obtain a code for which every cyclic shift of a codeword by = N0 positions yields another codeword.
can be characterized in a very compact way. The parity-check matrix of QC-MDPC codes with r = Q has the form Let DEC H (·) be an efficient decoder for the code defined by the parity-check matrix H.
Key generation: -Randomly generate a parity-check matrix H ∈ F r×n c is the private key.
-The public key is the corresponding binary k × n generator matrix in systematic form, i.e., The generator matrix G can be described by K 0 Q bits (public key size). Encryption: -To encrypt a plaintext u ∈ F k 2 a user computes the ciphertext c ∈ F n 2 using the public key G as where e is an error vector uniformly chosen from all vectors from F n 2 of Hamming weight wht (e) = e.

Decryption:
-To decrypt a ciphertext c the authorized recipient uses the private key DEC H (·) to obtain uG = DEC H (mG + e).
-Since G is in systematic form the plaintext u corresponds to the first k bits of uG.

A Reaction-Based Attack on the QC-MDPC McEliece Cryptosystem
Beside the conventional key-recovery and decoding attacks based on information set decoding, GJS proposed a reaction-based key-recovery attack on the QC-MDPC McEliece cryptosystem [8] which is currently the most critical attack against the scheme [11]. Efficient iterative decoding of LDPC/MDPC codes comes at the cost of decoding failures. For example, the MDPC codes proposed in [8] are operated with a target decoding failure probability lower than 10 −7 . 3 The GJS attack exploits the observation that the decoding failure probability for some particularly chosen error patterns is correlated with the structure of the secret key, i.e., the parity-check matrix H. We now describe briefly how the attack proceeds.
The Lee distance d L between two entries at position i and j of a binary vector a = (a 0 a 1 . . . a n−1 ) is defined as [13] The Lee distance profile 4 of a binary vector a of length Q is defined as The multiplicity µ(d) is defined as the number of occurrences of distance d in the vector a. A binary vector a is fully specified by its distance profile D(a) and thus can be reconstructed with high probability from D(a) [9] (up to cyclic shifts).
Let Ψ d be a set containing all binary vectors of length n with exactly t ones that are placed as t 2 pairs with Lee distance d in the first Q positions of the vector. By limiting the errors to the first Q positions, only the first circulant block h 0 (X) of the matrix H(X) will determine the result of the decoding procedure. The GJS attack proceeds as follows: -For d = 1, . . . , U generate error sets Ψ d of size M each (with M being a parameter defining, together with U , the number of attempts used by the attacker). -Send M ciphertexts (2) with e ∈ Ψ d for all d = 1, . . . , U and measure the frame error rate (FER).
Since the decoding failure probability is lower for e ∈ Ψ d with d ∈ D(h 0 ), i.e. if µ(d) > 0, for sufficiently large M the measured FER can be used to determine the distance profile D(h 0 ). The vector h 0 can then be reconstructed from the distance profile D(h 0 ) using the methods from [9]. The remaining blocks of H(X) in (1) can then be reconstructed via the generator matrix G(X) using linear algebraic relations. The success on the attack depends on how the systems deals with decoding failures since the FER can only be measured if retransmissions are requested. Another important factor is which decoding scheme is used. In [9,14] it is shown that the GJS attack succeeds if bit-flipping (BF) or belief propagation (BP) decoding algorithms are used.
In key exchange protocols the attack can be defeated by using ephemeral keys (i.e. a new key pair for every key exchange) [15]. However, this protocol-based fix can only be applied in very special scenarios.

Classical Decoding Algorithms
In the following we describe classical decoding algorithms for LDPC codes and analyze their error-correction capability for MDPC codes as well as their resilience against the GJS attack. For decoding we map each ciphertext bit c i to +1 if c i = 0 and −1 if c i = 1 yielding (with some abuse of notation) a ciphertext c ∈ {+1, −1} n . We consider next iterative MP decoding on the Tanner graph [16] of the code. A Tanner graph is a bipartite graph consisting of n variable nodes (VNs) and r check nodes (CNs). A VN v j is connected to a CN c i if the corresponding entry h i,j in the parity-check matrix is equal to 1. We consider next only regular Tanner graphs, i.e, graphs for which the number of edges emanating from each VN equals d v and the number of edges emanating from each CN equals d c . We refer to d v and d c as variable and check node degree, respectively. The neighborhood of a variable node v is N (v), and similarly N (c) denotes the neighborhood of the check node c. We denote the messages from VN v j to CN c i by m vj →ci and the messages from c i to v j by m ci→vj . In the following we omit the indices of VNs and CNs whenever they are clear from the context.

Bit-Flipping
For decryption in the QC-MDPC cryptosystem [8] an efficient BF algorithm for LDPC codes (see e.g. [17,Alg. 5.4]) is considered. This algorithm is often referred to as "Gallager's bit-flipping" algorithm although it is different from the algorithm proposed by Gallager in [18].
Given a ciphertext c, a threshold b ≤ r and a maximum number if iterations I max , the BF algorithm proceeds as follows. Each VN v is initialized with the corresponding ciphertext bit c ∈ {+1, −1} and sends the message m v→c = c to all neighboring CNs c ∈ N (v). The CNs send the messages to all neighboring VNs v ∈ N (c). Note, that (3) is equivalent to the modulo two sum of all incoming messages considered over F 2 . Each variable nodes counts the number of unsatisfied check equations (i.e the number of messages m c→v = −1) and sends to its neighbors the "flipped" ciphertext bit if at least b parity-check equations are unsatisfied, i.e.
The algorithm terminates if either all checks are satisfied or the maximum number of iterations I max is reached. The error-correction capability of the BF algorithm depends on the choice of the threshold b. In [19] the threshold b is selected as the maximum number of unsatisfied parity-check equations at each iteration which is denoted by Max upc . Note, that with b = Max upc the BF algorithm is no longer purely a MP algorithm on the Tanner graph of the code since Max upc has to be obtained by a global entity.
In [8] it is suggested to compute b according to [18, p. 46, Eq. 4.16] which will lead to suboptimal results since the BF decoder is different from the decoder analyzed in [18,Sec. 4]. To reduce the average number of iterations the threshold in [8] is chosen as b = Max upc − δ, where δ is a small integer that is determined empirically (see [8,Sec. 4]).
Gallager B An efficient binary MP decoder for LDPC codes, often referred to as Gallager B, was presented an analyzed in [18]. Each VN v is initialized with the corresponding ciphertext bit c ∈ {+1, −1}. The VN send the messages This means that in the first iteration VN v sends the message m v→c = c to all neighboring CNs c ∈ N (v). The CNs send the messages to the neighboring VNs. After iterating (5), (6) at most I max times, the final decision is given byĉ Comparing the CN operations (3) and (6), and the VN operations (4) and (5), one can see the before mentioned difference between the BF algorithm an Gallager B. For fixed (d v , d c ) the average error correction capability over the binary symmetric channel (BSC) for the ensemble of (d v , d c ) LDPC codes can be analyzed, in the limit of large block lengths, using the DE analysis [12,18]. Following this approach, the optimal value (in the large block length limit) for the parameter b can be determined by [18,Eq. 4.16].
The VNs are initialized with the corresponding ciphertext bit c.  (6) and (7)). In general, the second variant improves upon the first variant in terms of the number of correctable errors [20]. By definition the probability p ( ) e has two degrees of freedom, namely p * and p dec , which are subject to optimization. In general there is no close form optimization of these two parameters except for using the DE analysis from [20] as a guideline.
Algorithm E A generalization of the Gallager B algorithm that exploits erasures, which we further refer to as Algorithm E, was introduced and analyzed in [12,21]. To incorporate erasures the decoder requires a ternary message alphabet {−1, 0, +1}, where 0 indicates an erasure. The VNs are initialized with the corresponding ciphertext bit c and send the messages Here, ω is a heuristic weighting factor that was proposed in [12] improve the performance of Algorithm E. In [12] ω was allowed to change over iterations (to account for the increase of reliability of the CN messages as the iteration number grows). We consider next the simple case where ω is kept constant through all iterations. The check nodes operate the same way as in Gallager B, i.e the CNs send the messages m c→v according to (6). After iterating (6) and (9) at most I max times, the final decision is made aŝ In [12] a DE analysis for Algorithm E was derived which allows to compute an estimate of the optimal weight ω. For odd d v Algorithm E is equivalent to Gallager B with threshold b = ω+dv−1 2 and thus is also vulnerable against the GJS attack.
Belief Propagation (BP) Decoding BP decoding is a soft-decision decoding algorithm that is optimum in the maximum a posteriori (MAP) sense over a cycle-free Tanner graph. Each VN v is initialized with the log-likelihood ratios where c is ciphertext bit corresponding to v. The VNs send the messages to the CNs. In turn, the CNs send the messages After iterating (10), (11) at most I max times, the final decision at each VN is made asĉ It was conjectured for QC-MDPC codes [8] and finally shown for QC-LDPC codes [14] that the GJS attack is also successful for QC-MDPC McEliece cryptosystems under BP decoding.

Simulation Results
We now present simulation results of the GJS attack on variants of the QC-MDPC cryptosystem using the above described schemes. We consider next an QC-MDPC code ensemble C with n = 9602 and k = 4801 and parity-check matrix in the form where h 0 (X) and h 1 (X) are two polynomials of degree less than 4801 and wht (h 0 ) = wht (h 1 ) = 45. The ensemble C was proposed in [8] for 80 bit security. To analyze the resilience against the GJS attack, we performed Monte Carlo simulations for codes randomly picked from C collecting up to 200 decoding failures (frame errors) with I max = 50 iterations. For each multiplicity in D(h 0 ), 11 different error sets Ψ d (simulation points) were simulated. As in [14] the weight of the error patterns was chosen such that the FER is high enough to be easily observable in the simulations. Figure 1 shows the simulation results for one code from C . The results show that except the MF decoding algorithm, all considered schemes are vulnerable against GJS attack. For the MF decoding scheme the probability p

Secret Key Concealment via Modified Iterative Decoding
In this section we propose new methods to modify MP decoding algorithms that admit erasures. The methods allow to modify MP decoding algorithms in a probabilistic manner to make them resilient against the GJS attack for an appropriate choice of the decoding parameters. The main idea is, that similar to the MF decoding scheme (see Sec. 2.3), we modify the VN to CN messages at each iteration with a given probability. In particular, we modify the MP decoder such that the messages m v→c are erased (i.e., set to 0) under certain conditions with a given probability p ( ) e . Remarkably, we will see how this results also in an improved error-correction capability. In the following we will refer to this approach as random erasure message-passing (REMP) decoding and we apply it to modify Algorithm E.

First Modification of Algorithm E (REMP-1)
We modify Algorithm E such that any nonzero message m v→c in iteration is erased with probability p and m v→c = 0 else. At the CNs we perform the same operation as in Algorithm E (see (6)). The final decision, after iterating (6) and (13) at most I max times, is given by (18). As for the MF algorithm, the probability p ( ) e may be decreased as grows following (8).
Density Evolution Analysis Based on the analysis of Algorithm E in [12], we derive the DE analysis of our modified algorithm from Sec. 3.1. Let p ( ) z denote the probability that a VN to CN message sent at iteration is equal to z ∈ {−1, 0, +1}. Similarly, let q ( ) z denote the probability that a CN to VN message sent at iteration is equal to z ∈ {−1, 0, +1}. The encryption step (2) can be considered as the transmission of a codeword mG over a binary symmetric channel with crossover probability e/n. For the analysis we assume w.l.o.g. that all ciphertext bits c i are equal to +1 (all-zero codeword). Hence, we initialize the probabilities p The CN operation of REMP-1 remains the same as in Algorithm E (see [12]) and thus we have The probability p ( ) +1 can be expressed as The probability p ( ) −1 is given by Finally, the probability p ( ) 0 is given by Note that since in our scenario we do not have erasures in the ciphertext we have p (0) 0 = 0 which allows to simplify the expressions above.

Second Modification of Algorithm E (REMP-2)
In the second modification of Algorithm E from Sec.
and m v→c =m c→v otherwise. At the check nodes we perform the same operation as in Algorithm E (see (6)). The final decision, after iterating (6) and (17) at most I max times, is given bŷ Again, as for the MF algorithm, the probability p ( ) e may be decreased as grows following (8).
Density Evolution Based on the analysis of Algorithm E in [12], we derive the DE analysis of our modified algorithm from Sec. 3.2.
Since the CN operation is the same as in Algorithm E, we can compute q  (14), (15) and (16), respectively. The probability p ( ) +1 can be expressed as The probability p ( ) −1 is given by Finally, the probability p ( ) 0 can then be expressed as As before, note that since in our scenario we do not have erasures in the ciphertext we have p (0) 0 = 0 which allows to simplify the expressions above.

Masked Belief Propagation (MBP) Decoding
Using the ideas from the MF algorithm we now modify the classical BP decoding algorithm (see Sec. and m v→c =m v→c otherwise. In other words, if the sign of a message that is supposed so be sent by VN v is different from the sign of the corresponding initial value m ch , then with probability p ( ) e the initial value m ch is sent. The CNs operation remains the same as in (11). After iterating (19), (11) at most I max times, the final decision at each VN is made according to (12). For masked belief propagation (MBP) decoding we do not provide an explicit description on how DE has to be modified since the analysis can be carried out by applying minor changes to quantized DE [22].
We shall see next that, due to the modified operation at the VNs, the MBP algorithm allows to conceal the structure of H(X) by tuning the probability p ( ) e . We empirically verified that the idea of introducing random erasures as in Sec. 3.1 and Sec. 3.2 does not conceal the structure of H(X) for BP decoding. Moreover, we will see that, differently from the REMP modifications of Algorithm E, the modification of BP decoding comes at the cost of a reduced error correction performance. Thus, the decoding algorithms from Sec. 3.1 and Sec. 3.2 are preferable since they show a similar performance at a lower decoding complexity.

Performance Analysis & Simulation Results
Density Evolution Analysis We first analyze the error-correction capability of the two modifications of Algorithm E from Sec 3.1 and Sec. 3.2. As first estimate of the code performance, we employ the DE analysis [12] to determine the iterative decoding threshold of a (d v , d c ) unstructured LDPC code ensemble over a BSC with error probability ∆. The decoding threshold is denoted as ∆ and represents the largest channel error probability for which, in the limit of large n and large I max , the bit error probability of code picked randomly from the ensemble becomes vanishing small [12]. We then get a rough estimate on the error correction capability as 5 δ = n∆ . 5 Note that at the decoding threshold ∆ a vanishing small bit error probability may not imply a vanishing small block error probability. However, for the regular MDPC ensembles under consideration the threshold on the bit error probability and the one on the block error probability do coincide over binary-input output-symmetric memoryless channel under BP decoding [23]. In our estimate, we implicitly assume that the result extends to Algorithm E and its variants.
Note that, for a moderate block length n, δ provides only a coarse estimate to the number of errors at which we expect the FER to rapidly decrease (socalled waterfall region), with the accuracy of the prediction improving as n grows large. With a slight abuse of the wording, we refer to δ as decoding threshold as well. We further denote the decoding threshold under Algorithm E, REMP-1 and REMP-2 as δ E , δ 1 and δ 2 , respectively. The decoding thresholds do not only depend on the selected algorithm, but also on the algorithm parameters.
The results for the (9602, 4801) MDPC ensemble with d v = 45 and d c = 90 are summarized in Table 1. For Algorithm E, the value of ω has been chosen to maximize the decoding threshold. Remarkably, the variants REMP-1 and REMP-2 do not yield a threshold degradation, and in some cases they even provide slight gains for suitable choices of the parameters (ω, p * , p dec ). Simulation Results To validate the performance estimates obtained through DE, we simulated the error-correction capability of the decoding schemes from Section 2.3 and Section 3. The results in terms of FER as a function of the error pattern weight are depicted in Figure 2. The results confirm the trend predicted by the DE analysis. In particular, the error-correction capability improves upon existing decoding algorithms. Even for erasure probability values chosen to conceal the structure of H(X) (yielding a suboptimal choice with respect to the error correction performance), REMP-2 outperforms Algorithm E and the BF/MF algorithms.

Resilience against the GJS Attack
We now analyze the resilience of the proposed decoding schemes against the GJS attack. For the REMP variants of Algorithm E as well as for the MBP decoder we performed Monte Carlo simulations for codes randomly picked from C collecting up to 200 decoding failures (frame errors) with I max = 50 iterations. For each multiplicity in D(h 0 ), 11 different error sets Ψ d (simulation points) were simulated. The simulation results in Figure 3 show that, for an appropriate choice of parameters, the REMP-1 and REMP-2 decoding schemes have a similar FER for all multiplicities appearing in D(h 0 ). Hence, the reconstruction of the distance profile D(h 0 ) from the observed FER is not possible.  Figure 4 shows that for an appropriate choice of parameters also the MBP algorithm is able to conceal the structure of the secret key. For the choice of parameters that conceal the secret key the FER of MBP decoding and REMP-2 decoding at error weight e = 106 is similar. Hence, due to the higher complexity of MBP, the REMP scheme is preferable.
To conceal the structure of H(X) the choice of p ( ) e for a particular error weight e is crucial. If p ( ) e is chosen too large the picture is inverted, i.e. higher multiplicities have a higher FER than lower multiplicities. Thus the error weight e should be computed after decoding and ciphers generated with an error weight different from e should be rejected to prevent attacks that exploit this effect.

Conclusions
We analyzed classical iterative decoding schemes for moderate-density paritycheck (MDPC) codes with respect to their error-correction capability as well as their resilience against a recent key-recovery attack by Guo, Johansson and Stankovski (GJS). The simulation results show that a decoding scheme by Miladinovic and Fossorier (MF) is able to defeat the attack for an appropriate choice of decoding parameters.
A new decoding method called random erasure message-passing (REMP) that allows to improve existing message-passing (MP) decoding algorithms with respect to their error-correction capability as well as their resilience against the GJS attack was proposed. Two REMP variants of an existing MP decoder that have an improved error-correction performance for MDPC codes compared to existing schemes were presented and analyzed. The simulation results show that the proposed REMP schemes are able to defeat the GJS attack for an appropriate choice of decoding parameters.
A new variant of the belief propagation decoding algorithm that is able to resist the GJS attack was presented.