1

arXiv:1712.02167v1 [cs.CR] 6 Dec 2017

Cryptanalysis of a public key encryption scheme
based on QC-LDPC and QC-MDPC codes
Vlad Dragoi∗† and Hervé Talé Kalachi ‡
∗ Faculty of Exact Sciences, “Aurel Vlaicu” University of Arad, Romania
Email: ∗ vlad.dragoi@uav.ro
† Normandie University, France; UR, LITIS Mont-saint-aignan, France
Email: † vlad-florin.dragoi@univ-rouen.fr
‡ ERAL, University of Yaounde 1
Email: ‡ hervekalachi@gmail.com

Abstract—This letter presents a cryptanalysis of the modified
McEliece cryptosystem recently proposed by Moufek, Guenda
and Gulliver [24]. The system is based on the juxtaposition of
quasi-cyclic LDPC and quasi-cyclic MDPC codes. The idea of
our attack is to find an alternative permutation matrix together
with an equivalent LDPC code which allow the decoding of any
cipher-text with a very high probability. We also apply a recent
technique to determine weak keys [4] for this scheme. The results
show that the probability of weak keys is high enough that this
variant can be ruled out as a possible secure encryption scheme.
Index Terms—Post-quantum cryptography; McEliece cryptosystem; QC-LDPC and QC-MDPC codes.

I. I NTRODUCTION
The problem of finding a practical solution for quantum
resistant cryptography has become an urgent issue, mainly
for two reasons: the existence of a quantum polynomial time
algorithm [29] that breaks the actual RSA and ECC solutions
and the improvements of classical algorithms for the discrete
logarithm in small characteristic [2]. Among the possible
candidates for post-quantum cryptography, code-based cryptography is one of the most promising solutions [6]. It is also
one of the oldest public key encryption solutions thanks to
McEliece’s idea [21].
In the original paper, McEliece proposed to use binary
Goppa codes, which remain unbroken, to date. Other families
of algebraic codes were proposed (see [25], [31], [14] ect).
But they were successfully cryptanalyzed, mainly due to their
algebraic structure [9], [22], [32]. Probabilistic codes were also
considered: concatenated codes were analyzed in [28], [31];
convolutional codes were proposed in [17], but successfully
cryptanalyzed in [16]. Polar codes were also proposed in [30]
and cryptanalyzed in [3].
The emergence of all these attacks on several variants of the
McEliece cryptosystem shows the importance and necessity
of proposing new masking techniques. For example a code
with an efficient decoding algorithm could be masked with
the use of an arbitrary code in order to sustain the security of
the scheme. This technique was proposed for the first time by
Wieschebrink in [35] to avoid the Sidelnikov-Shestakov attack
[32]. The idea is to use the juxtaposition of a Generalized
Reed-Solomon code and a random code. This solution became
famous since it was also used in the case of Reed-Muller codes

[12]. But these two variants were broken using the square code
technique in [8], [26]. Nonetheless the idea was not totally
abandoned since Wang [34] proposed to use the juxtaposition
of a GRS code with a random code and then to multiply
the generator matrix of the resulting code with a matrix that
linearly combines the columns of the GRS and the random
code. The main motivation is to obtain a random like code in
the end.Another technique was introduced in [18] where the
authors propose to use the “u|u + v” construction with two
GRS codes. This new trend also inspired researchers to use
the juxtaposition of LDPC and MDPC codes [24]. This is the
variant that we analyze in the present article.
a) Our contribution: We describe a key recovery attack
against the modified McEliece cryptosystem based on the
juxtaposition of LDPC and MDPC codes [24]. The idea of
our attack is to find an alternative permutation matrix together
with an equivalent LDPC code which allow the decoding of
any cipher-text with a very high probability.
II. BACKGROUND

ON

C ODING T HEORY

Throughout the paper we denote by F2 the finite field with 2
elements and M k,n (F2 ) the set of k × n matrices with entries
in F2 . The Hamming weight wt(x) of a vector x ∈ F2n is
the number of non-zero coordinates of x. A binary linear
code C of length n and dimension k is a k-dimensional linear
subspace of F2n . A generator matrix of C is any k × n matrix
G ∈ M k,n (F2 ) with rows that generate C . The dual C ⊥ of C
is the n − k-dimensional linear subspace defined by
n
o
Õ
C ⊥ = z ∈ F2n : ∀c ∈ C ,
ci zi = 0 .
i

A parity check matrix of C is a generator of C ⊥ .
Definition 1. A (n, k, ω)-code is a binary linear code defined
by a k × n parity-check matrix (k < n) where each row has
weight ω. When n → ∞ we define
• An LDPC code is a (n, k, ω)-code with ω = O (1) [11].
√ 
• An MDPC code is a (n, k, ω)-code with ω = O
n [23].
Furthermore we will use the (n, k, ωldpc ) notation, respectively (n, k, ωmdpc ). The original decoding technique for LDPC
codes is the well-known bit flipping algorithm [11]. This

2

technique is known to provide an error-correction capability
which increases linearly with the length of the code, but decreases with the weight of the parity-checks. Therefore MDPC
codes suffer from a degradation in decoding performance,
compared with LDPC codes. A full description of the bit
flipping algorithm can be found in [7], [11], [23].
Remark 1. Since the performance and the correctness of the bit
flipping algorithm depend on the density of the parity-check
matrix, any equivalent parity-check matrix that respects the
density condition enables a correct decoding algorithm.
III. M OUFEK , G UENDA AND G ULLIVER ’ S CRYPTOSYSTEM
In [24] Moufek, Guenza and Gulliver proposed a McEliece
type cryptosystem, based on LDPC and MDPC codes. The
scheme is composed of three algorithms: key generation
KeyGen(·), encryption Encrypt(·) and decryption Decrypt(·).
a) KeyGen(n, k, t1, t2 ) = (pk, sk):
• Pick a generator matrix G1 of a (n1, k, ωldpc ) LDPC code
C1 that can correct t1 errors, and a generator matrix G2 of
a(n2, k, ωmdpc ) MDPC code denoted C2 that can correct
t2 errors.
• Pick at random S in GLk (F2 ) and an n × n permutation
matrix P, where n = n1 + n2 .
def
• Compute Gpub = SGP, where G = (G1 | G2 ) .
• Return pk = (Gpub, t1, t2 ) and sk = (S, G1, G2, P ).
b) Encrypt(m, pk) = z:
n
n
• Randomly generate e = (e1 | e2 ) ∈ F2 with e1 ∈ F2 1 ,
n2
e2 ∈ F2 , wt(e1 ) = t1 and wt(e2 ) = t2 .
• Compute z = mGpub + e.
c) Decrypt(z, sk) = m:
• Compute z ∗ = zP −1 and decode using the bit flipping
algorithm for C1 and C2 . The output is m∗ ∈ F2k .
∗ −1
• Return the message m S .
∗
Remark 2. During the
decryption,
 we −1have ∗z n1=

∗
∗
∗
∗
mS (G1 | G2 )+ e1 | e2 with e1 | e2 = eP and e1 ∈ F2 .
The authors of this scheme propose to use the decoding
capability of both LDPC and MDPC codes to find e∗1 and
e∗2 . However, we emphasize that one can obtain wt(e∗1 ) > t1 or
wt(e∗2 ) > t2 . This can imply a failure in the decoding algorithm
of C1 or C2 . But both situations cannot occur simultaneously
since these would then imply that wt(eP −1 ) > t. It is also
important to remark that obtaining e∗1 or e∗2 is sufficient to
recover mS and thus m.
IV. C RYPTANALYSIS OF THE M OUFEK , G UENDA
G ULLIVER ’ S SCHEME .

AND

We propose here a key recovery attack against the previous
cryptosystem. One of the key points in our attacks is the
following proposition.

weight parity-check matrix of the MDPC code, (A | B) ∈
M k,n1 +n2 (F2 ) a full-rank matrix such that G1 At + G2 B t = 0
and A, B , 0.
Proof. The proof is obvious since we have H ′Gtpub = 0.



This proposition shows the existence of a sufficient number
of codewords with weights ωldpc in the dual of the public
code. We represent this set of codewords by the matrix
H ∗ ∈ M k ∗,n1 +n2 (F2 ) , each row of H ∗ being an element
of the set and conversely. Since these
 codewords of weights
ωldpc contain the rows of Hldpc 0 P, we have rank(H ∗ ) ≥
n1 − k. One can expect to have rank(H ∗ ) > n1 − k but
our practical experiments always gave an equality, that is to
say rank(H ∗ ) = n1 − k. In the sequel we can suppose that
k ∗ = n1 − k. If k ∗ > n1 − k, one can select only n1 − k rows
of H ∗ that are linearly independent.
The attack starts with a search for codewords of weights
ωldpc .
a) Search of codewords of weights ωldpc : This step
aims to find the rows of the matrix H ∗ ∈ M k ∗,n1 +n2 (F2 ) .
Assuming without loss of generality that an adversary knows
the value of the parameter ωldpc, this step can be achieved
by applying any of the ISD variants such as, for example,
Dumer’s algorithm [10]. This issue is discussed in detail in
Section V, where a complexity analysis of our attack is given.
We emphasize that ωldpc can be easily guessed during this step
by starting with ωldpc = 1 and increasing up to the value that
satisfies the condition rank(H ∗ ) = n1 − k.
Remark 3. At the end of this step we have managed to build
the matrix H∗ ∈ M k ∗,n1 +n2 (F2 ) that generates the same code
as Hldpc | 0 P and therefore has n2 zero columns.

∗
Proposition 2. There
 exists a permutation matrix P such that
H ∗ P ∗ = H1∗ | 0 with H1∗ ∈ M k ∗,n1 (F2 ) . Such a matrix can
be computed with complexity O(n) and satisfies


• Hldpc | 0 P P ∗ = Hldpc P1 | 0 ,


P1 0
• PP∗ =
.
0 P2

P1 and P2 being permutation matrices of sizes n1 and n2
respectively.
Proof. The existence of P ∗ comes
 directly from Remark

3 which also provides Hldpc | 0 P P ∗ = Hldpc P1 | 0 .
∗
Furthermore, this last equality with the fact that
 P1 and
 PP
P
0
1
are permutation matrices imply that P P ∗ =
where
0 P2
P2 is also a permutation matrix. To finish, given the matrix
H ∗, a matrix P ∗ can be easily computed by identifying the
n2 zero columns of H ∗ .


Proposition 1. A parity check matrix of the public code is
H
© ldpc
H ′ = HP = ­ 0
« A

ª
Hmdpc ® P,
B ¬
where Hldpc ∈ M n1 −k,n1 (F2 ) is the low weight parity-check
matrix of the LDPC code, Hmdpc ∈ M n2 −k,n2 (F2 ) the low
0

This proposition shows that a cryptanalysis is able to find an
alternative permutation matrix P ∗ together with a parity check
matrix H1∗ of an equivalent LDPC code that can correct the
same number of errors as the secret one.
 In the sequel, we are
going to show that the pair P ∗, H1∗ is sufficient to decode
any cipher-text with a high probability.

3


b) Decryption with P ∗, H1∗ : We show here the way
to decrypt
with P ∗ and H ∗ . Let e∗ = eP ∗ =
 any cipher-text
∗
∗
∗
∗
e1 | e2 and z = zP = z1∗ | z2∗ with e∗1, z1∗ ∈ F2n1 . So


z ∗ = mGpub + e P ∗ = mS (G1 P1 | G2 P2 ) + e∗1 | e∗2 .

TABLE I
T HE PROBABILITY Pr(wt(x1 ) > t1 ) FOR t1 = n1 /20 AND t2 = n2 /40 WITH n1 = 4k AND n2 = 2k . T HE FIRST
NAMELY

This implies that z1∗ = mSG1 P1 +e∗1 . Since SG1 P1 generates
an LDPC code with parity-check matrix H1∗, we can recover
e∗1 using the bit-flipping algorithm, assuming that wt(e∗1 ) ≤ t1 .
In the next paragraph we prove that the probability that
wt(e∗1 ) ≤ t1 is asymptotically close to 1 when the length of
the codes goes to infinity.
Theorem 1. For i ∈ {1, 2} let ni, ti be integers such that ti < ni
with n1 = γn2 and t1 > γt2, where γ ≥ 1. Let x = (x1 | x2 )
be a random vector over F2n1 +n2 with wt(x) = t1 + t2, where
xi ∈ F2ni for i ∈ {1, 2}. Then we have
n1  n2 
Pr(wt(x1 ) > t1 ) < t2

Proof. First notice that we have

t1 +1 t2 −1
n1 +n2 
t1 +t2

∀ 0 ≤ i ≤ t1 + t2 , Pr(wt(x1 ) = i) =

.

n1 
n2 
i t1 +t2 −i
.
n1 +n2 
t1 +t2

(1)

Using the latter probability we obtain by a simple computation
Pr(wt(x1 ) = i)
(i + 1)(n2 − t1 − t2 + i + 1)
=
.
Pr(wt(x1 ) = i + 1)
(n1 − i)(t1 + t2 − i)
Hence for any i ≥ t1 + 1 we obtain

Pr(wt(x1 ) = i)
≥
Pr(wt(x1 ) = i + 1)

(t1 + 2)(n2 − t2 + 2)
. Replacing n1 = γn2 and t1 > γt2 in the
(n1 − t1 )t2
latter fraction we obtain that
∀ i ≥ t1 + 1 we have Pr(wt(x1 ) = i) > Pr(wt(x1 ) = i + 1)
(2)
From (2) and (1) we deduce the desired result.

When t1 and t2 are linear in the code length we obtain the
following asymptotic approximation
Corollary 1. Let n2 = n, n1 = γn and t1 = αn1, t2 = βn2 with
β < αγ ≤ 1/2. Then when n → ∞ we have
√ −n
Pr(wt(x1 ) > t1 ) < cα,β,γ n2



(γ+1)h(α+ β−α
γ+1 )−γh(α)−h(β)



,

where cα,β,γ is a constant and h is the binary entropy function.
Proof. Apply the Stirling approximation for factorials and
expand the series to obtain the result.

V. C OMPLEXITY

ANALYSIS AND NUMERICAL RESULTS .

a) Complexity analysis: The work factor of computing
an alternative private key (P ∗, H ∗ ) is given by the work
factor of the low weight codewords search algorithm plus
the computation required to find P ∗ . The first step can be
done using any of the ISD variants such as Dummer (DISD, [10]), May, Meurer and Thomae (MMT-ISD, [19]) or
Becker, Joux, May and Meurer (BJMM-ISD, [5]) or May
and Ozerov (MO-ISD [20]). These algorithms have a time

T HEOREM 1,

n1  n2  n1 +n2 
ubk, t , t = t2
/ t +t . T HE THIRD ROW IS THE ASYMPTOTIC VALUE OF THE UPPER
t1 +1 t2 −1
1 2
1 2


β−α
√ −n (γ+1)h(α+ γ+1 )−γh(α)−h(β)
.
BOUND FROM C OROLLARY 1, I . E . ub k, α, β,γ = n2

ROW IS THE EXACT VALUE FOR THE PROBABILITY AND THE SECOND ROW IS THE UPPER BOUND FROM

k
log2 (Pr(wt(x
1) > t1 ))


log2 ub k, t1, t2 Thm1

log2 ub k, α, β,γ Cor1

6851
-117

8261
-141

9857
-166

-110

-133

-159

-106

-129

-155

complexity equal to O(e−ω ln(1−k/n)(1+o(1)) ), as long as ω = o(n)
when n → ∞ [33]. Hence, in our case computing the
matrix H ∗ requires a work factor asymptotically equal to
O(e−ωldpc ln(k/(n1 +n2 ))(1+o(1)) ), when n1 + n2 tends to infinity.
Regarding the complexity of computing P ∗, it requires n1 + n2
basic operations (here we consider binary additions of length
k binary vectors). Thus the complexity of our attack, denoted
by WF A (n1, n2, k, ωldpc ) is in the worst case dominated by the
cost of the best ISD variant.
b) Numerical results: We analyze the effective cost of
our attack on some practical parameters. Firstly we considered
suggested values given in [24], more precisely n1 +n2 = 16128.
As for the co-dimension we analyzed three different cases,
n1 + n2 − k ∈ {8064, 10080, 12096}. Hence the complexity of
finding the codewords of weight 15 in the dual of the public
code ( i.e. ωldpc = 15), using the BJMM-ISD variant equals
26.13, 210.97 respectively 219,20 . The computations were done
using a PariGP implementation similar to that in [27]. The
probability Pr(wt(x1 ) > t1 ) (for these parameters) is given in
Table I. These results show that the parameters proposed in
[24] are too vulnerable to be considered in practice.
One might generate a more resistant set of parameters for
the scheme, which fact we illustrate in Table II. However, it is
important to consider the weak keys approach, a recent technique introduced in [4], where the authors use the Extended
Euclidean algorithm in order to recover a private key given a
public key. We compute the probability of weak keys for the
Moufek et al. variant with reasonable parameters in Table II.
TABLE II
T HE PROPORTION OF WEAK KEYS AND THE COMPLEXITY OF OUR ATTACK AGAINST THE M OUFEK ET AL . M C E LIECE
VARIANT USING A



(4k, k, ωldpc ) LDPC CODE AND A (2k, k, ωmdpc ) MDPC CODE .

(k, ωldpc )

log WFA (4k, 2k, k, ωldpc )
Proportion of weak keys



(6851, 36)

(8261, 44)

(9857, 54)

80.9

101.6

127.4

2−7.3

2−10.6

2−14

Remark 4. In the first place we remark that the key size for the
[24] scheme is considerably greater than for similar schemes
such as [1], [23].
Notice from Table II that the odds of generating weak keys
are too big to imagine that the scheme can be protected against
this type of attack. Indeed, we find that the scheme might
be secured against the weak keys approach by increasing the
values of the ωldpc . But in order to obtain reasonable secure
parameters this solution is equivalent to replacing the LDPC

4

code with an MDPC code and thus is of no interest compared
with the MDPC McEliece variant [23].
Remark 5. It is also worth mentioning the recent reaction
attacks against the QC-MDPC scheme [13] and the QCLDPC scheme [15]. This technique can be used to recover
the structure of the MDPC code in the case of Guenda’s et al.
variant. Nonetheless we remark from Theorem 1 and Corollary
1 that the weight of x2 is likely to be much bigger than the
error capacity of the MDPC code. Hence, one might not be
able to retrieve the initial message unless it uses the LDPC
code.
However, the reaction attack remains highly interesting in
similar constructions, namely in the case of the direct sum
or Plotkin sum of LDPC and MDPC codes. Indeed, in these
cases attacking the LDPC code with our technique is not
sufficient for retrieving the initial message, and thus revealing
the structure of the MDPC code is necessary.
VI. C ONCLUSION
We have proposed a successful cryptanalysis of the
McEliece variant in [24]. Our attack exploits the structure of
the dual of the public code and its complexity is dominated
by the low weight search algorithm on this dual. The attack
is entirely based on finding the structure of the LDPC code,
regardless of the nature of the second code. As a consequence,
our result can be applied even if the MDPC code is replaced
by another code.
We notice that this variant is also vulnerable to the weak
keys approach [4], since the proportion of weak keys is not
negligible. Hence, one can consider that the McEliece variant
[24] is too vulnerable to be practical. We also emphasize that
similar constructions, such as the direct sum or Plotkin sum
of MDPC and LDPC codes can be attacked by combining our
technique with the latest reaction attacks.
R EFERENCES
[1] Marco Baldi. QC-LDPC Code-Based Cryptography 2014. Springer,
Berlin, Heidelberg.
[2] Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, and Emmanuel
Thomé. A heuristic quasi-polynomial algorithm for discrete logarithm
in finite fields of small characteristic. In Nguyen, P.Q. Oswald, E.
(eds.) EUROCRYPT 2014 LNCS, vol. 8441, pp. 1–16,Springer, Berlin,
Heidelberg.
[3] Magali Bardet, Julia Chaulet, Vlad Dragoi, Ayoub Otmani, and JeanPierre Tillich. Cryptanalysis of the McEliece public key cryptosystem
based on polar codes. In Post-Quantum Cryptography 2016, LNCS,
Fukuoka, Japan. Springer International Publishing, Cham.
[4] Magali Bardet, Vlad Dragoi, Jean-Gabriel Luque, and Ayoub Otmani.
Weak keys for the quasi-cyclic MDPC public key encryption scheme.
In AFRICACRYPT 2016, Fes, Morocco, Proceedings, pages 346–367.
Springer International Publishing, Cham.
[5] Anja Becker, Antoine Joux, Alexander May, and Alexander Meurer.
Decoding random binary linear codes in 2 n/20 : How 1 + 1 = 0 improves
information set decoding. In EUROCRYPT 2012, LNCS Springer,
Berlin, Heidelberg.
[6] Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, editors.
Post-Quantum Cryptography. Springer-Verlag, 2009.
[7] Julia Chaulet and Nicolas Sendrier. Worst case QC-MDPC decoder for
McEliece cryptosystem. In IEEE Int. Symposium on Inf. Theory, ISIT
2016, Barcelona, Spain, pages 1366–1370.
[8] Alain Couvreur, Philippe Gaborit, Valérie Gauthier-Umaña, Ayoub Otmani, and Jean-Pierre Tillich. Distinguisher-based attacks on publickey cryptosystems using Reed-Solomon codes. Des. Codes Cryptogr.,
73(2):641–666, 2014.

[9] Alain Couvreur, Irene Márquez-Corbella, and Ruud Pellikaan. A
polynomial time attack against algebraic geometry code based public key
cryptosystems. In Proc. IEEE Int. Symposium Inf. Theory - ISIT 2014,
pages 1446–1450.
[10] Ilya Dumer. On minimum distance decoding of linear codes. In Proc.
5th Joint Soviet-Swedish Int. Workshop Inform. Theory, pages 50–52,
Moscow, 1991.
[11] R. G. Gallager. Low Density Parity Check Codes. M.I.T. Press,
Cambridge, Massachusetts, 1963.
[12] Cheikh Thiecoumba Gueye and El Hadji Modou Mboup. Secure
cryptographic scheme based on modified Reed Muller codes. Int.
Journal of Security and Its Applications, 7(3):55–64, 2013.
[13] Guo Qian and Johansson Thomas and Stankovski Paul. A key recovery
attack on MDPC with CCA security using decoding errors, ASIACRYPT
2016, Vietnam, 2016, Proceedings, Part I 22, pages 789–815, Springer,
Berlin, Heidelberg.
[14] Heeralal Janwa and Oscar Moreno. McEliece public key cryptosystems
using algebraic-geometric codes. Des. Codes Cryptogr., 8(3):293–307,
1996.
[15] Tomáš Fabšič, Viliam Hromada, Paul Stankovski, Pavol Zajac, Qian
Guo, and Thomas Johansson. A reaction attack on the QC-LDPC
McEliece cryptosystem. In Post-Quantum Cryptography 2017, Utrecht,
The Netherlands, pages 51–68, Springer, Cham.
[16] Grégory Landais and Jean-Pierre Tillich. An efficient attack of a
McEliece cryptosystem variant based on convolutional codes. In P. Gaborit, editor, Post-Quantum Cryptography’13, volume 7932 of LNCS,
pages 102–117, June 2013. Springer, Berlin, Heidelberg
[17] Carl Löndahl and Thomas Johansson. A new version of McEliece PKC
based on convolutional codes. In Inf. and Communications Security,
ICICS,2012, volume 7168 of LNCS, pages 461–470. Springer, Berlin,
Heidelberg.
[18] Irene Márquez-Corbella and Jean-Pierre Tillich. Using Reed-Solomon
codes in the (u |u + v) construction and an application to cryptography.
In Proc. IEEE Int. Symposium Inf. Theory - ISIT, pages 930–934, 2016.
[19] Alexander May, Alexander Meurer, and Enrico Thomae. Decoding
random linear codes in O(20.054n ). In ASIACRYPT 2011, volume 7073
of LNCS, pages 107–124. Springer, Berlin, Heidelberg.
[20] Alexander May and Ilya Ozerov. On computing nearest neighbors with
applications to decoding of binary linear codes. In EUROCRYPT 2015,
volume 9056 of LNCS, pages 203–228. Springer, Berlin, Heidelberg.
[21] Robert J. McEliece. A Public-Key System Based on Algebraic Coding
Theory, pages 114–116. Jet Propulsion Lab, 1978. DSN Progress Report
44.
[22] Lorenz Minder and Amin Shokrollahi. Cryptanalysis of the Sidelnikov
cryptosystem. In EUROCRYPT 2007, volume 4515 of LNCS, pages
347–360, Barcelona, Spain. Springer, Berlin, Heidelberg.
[23] Rafael Misoczki, Jean-Pierre Tillich, Nicolas Sendrier, and Paulo S.
L. M. Barreto. MDPC-McEliece: New McEliece variants from moderate
density parity-check codes. In Proc. IEEE Int. Symposium Inf. Theory
- ISIT, pages 2069–2073, 2013.
[24] Hamza Moufek, Kenza Guenda, and T Aaron Gulliver. A new variant of
the McEliece cryptosystem based on QC-LDPC and QC-MDPC codes.
IEEE Communications Letters, 21(4):714–717, 2017.
[25] Harald Niederreiter. Knapsack-type cryptosystems and algebraic coding
theory. Problems of Control and Information Theory, 15(2):159–166,
1986.
[26] Ayoub Otmani and Hervé Talé Kalachi. Square code attack on a modified sidelnikov cryptosystem. In Codes, Cryptology, and Information
Security 2015, pages 173–183. Springer, Cham.
[27] Christiane Peters. Information-set decoding for linear codes over F q . In
Post-Quantum Cryptography 2010, volume 6061 of LNCS, pages 81–94.
Springer, Berlin, Heidelberg.
[28] Nicolas Sendrier. On the concatenated structure of a linear code. Appl.
Algebra Eng. Commun. Comput. (AAECC), 9(3):221–242, 1998.
[29] P.W. Shor. Algorithms for quantum computation: Discrete logarithms
and factoring. In S. Goldwasser, editor, FOCS, pages 124–134, 1994.
[30] Sujan Raj Shrestha and Young-Sik Kim. New McEliece cryptosystem
based on polar codes as a candidate for post-quantum cryptography. In
2014 14th Int. Symp. on Comm. and Inf. Tech. (ISCIT), pages 368–372.
IEEE, 2014.
[31] Vladimir Michilovich Sidelnikov. A public-key cryptosytem based on
Reed-Muller codes. Discrete Math. Appl., 4(3):191–207, 1994.
[32] Vladimir Michilovich Sidelnikov and S.O. Shestakov. On the insecurity
of cryptosystems based on generalized Reed-Solomon codes. Discrete
Math. Appl., 1(4):439–444, 1992.

5

[33] Rodolfo Canto Torres and Nicolas Sendrier. Analysis of information set
decoding for a sub-linear error weight. In Post-Quantum Cryptography
2016, Fukuoka, Japan, February 24-26, Proceedings, pages 144–161.
Springer, Cham.
[34] Yongge Wang. Quantum resistant random linear code based public key
encryption scheme rlce. In Proc. IEEE Int. Symposium Inf. Theory ISIT, pages 2519–2523, 2016.
[35] Christian Wieschebrink. Two NP-complete problems in coding theory
with an application in code based cryptography. In Proc. IEEE Int.
Symposium Inf. Theory - ISIT, pages 1733–1737, 2006.

