A Quantum-Secure Niederreiter Cryptosystem using
Quasi-Cyclic Codes
Ayan Mahalanobis∗

Upendra Kapshikar

arXiv:1803.07827v1 [cs.CR] 21 Mar 2018

March 22, 2018

Abstract
In this paper, we describe a new Niederreiter cryptosystem based on quasi-cyclic
m−1
codes that is quantum-secure. This new cryptosystem has good transmission
m
rate compared to the one using binary Goppa codes and uses smaller keys.

1

Introduction

In this paper, we develop a new Niederreiter cryptosystem using m−1
m quasi-cyclic codes.
These are well known linear block codes. The main result in this paper is that the Niederreiter cryptosystem built with these codes is quantum-secure. Many attempts were made
by many distinguished authors to built new McEliece or Neiderreiter cryptosystems using
different codes. However, none of these authors demonstrated that their cryptosystem
is quantum-secure. One of the main reason to study the Niederreiter cryptosystem is
that it can be quantum-secure. In today’s world designing cryptosystem just got twice as
hard. One needs to ensure that it is secure from known classical attacks as well as secure
from the known quantum attacks, i.e., from the hidden subgroup problem arising out of
quantum Fourier sampling.
The concept of security which is tied to quantum Fourier sampling for non-abelian
groups has a rich tradition in the work of Hallgreen et al. [11] and Kempe and Salev [13].
Dinh et al. [7] using earlier work showed that the McEliece cryptosystem built on binary
Goppa codes is quantum-secure. We use their theorem [7, Theorem 4] to show that our
proposed cryptosystem is quantum-secure.
Description of the parity check matrix used for the proposed Neiderreiter
cryptosystem Recall that we are talking about m−1
m quasi-cyclic codes over F2l . For
the cryptosystem to be quantum-secure the parity check matrix H for the [n = mp, k =
(m − 1)p], m−1
m quasi-cyclic code should satisfy the following conditions:
I Integers m, p, such that p is a prime and m is bounded above by a polynomial in p.
II The matrix H is of size p × mp over F2l .
III The matrix H is of the form [ C0 = I | C1 | C2 | . . . | Cm−1 ], where each Ci is a circulant
matrix of size p. Each Ci for i > 0 should contain an element from a proper extension
of F2 . Furthermore, we denote the matrix H as [ I | C ] where C is the concatenation
of the circulant matrices Ci , i > 0.

IV We define TH = P1 ∈ Sp | ∃P2 ∈ Sp(m−1) such that P1 CP2 = C , where Sn is the
symmetric group acting on n letters. It is easy to see that TH is a permutation group
action on p letters. The condition we impose on H is that TH is not 2-transitive.
V No two columns of C are identical.
For more on quantum security of the proposed cryptosystem a reader can skip to Section 5.
∗

IISER Pune, Pune, INDIA ayan.mahalanobis@gmail.com

1

2

Review of Niederreiter Cryptosystem

In 1978, Robert McEliece [16] suggested a cryptosystem based on algebraic codes. The
system did not gain much popularity then because of its large key sizes. However, with
quantum computing becoming a reality, McEliece cryptosystems have become the center of
attention for cryptographers. Unlike RSA or ElGamal cryptosystem, McEliece cryptosystem is based on a non-commutative structure which allegedly makes it a strong candidate
for post-quantum cryptography. Compared to traditional cryptosystems, a McEliece cryptosystem has following advantages:
a) It is fast. Faster than RSA or ElGamal.
b) It is believed to be quantum secure.
The disadvantages are the following:
a) The key sizes are huge.
b) The ciphertext becomes much larger than the plaintext because of the redundancy
added by the encoding process.
In this paper we focus on building a Niederreiter cryptosystem. Apart from fulfilling the
obvious requirement of a signature scheme, Niederreiter cryptosystem is faster compared to
a McEliece cryptosystem. Li et al. [15] proved that the security of a McEliece cryptosystem
and its Niederreiter counterpart are equivalent under the Lee-Brickell attack [14]. For these
reasons, in this paper our main focus is on building a Niederreiter cryptosystem.
All codes in this paper are linear block codes and our standard reference for coding
theory is Blahut [6, Chapter 3]. A binary linear code C of length n and rank k is a k
dimensional linear subspace of Fn2 . Hamming weight or simply weight t of a codeword
means that the codeword has t non-zero entries. Standard distance on C is the hamming
distance. Distance of a linear code C is defined as minimum distance between two nonzero codewords. Traditionally, such a code is denoted as [ n, k] code. The ratio nk is the
transmission rate of the code.
A generator matrix M of an [n, k] linear code C is a k × n matrix such that C = {xG :
x ∈ Fqk }. A generator matrix M of the form [ Ik | G′ ] is said to be in the systematic form.
A parity check matrix H of an [n, k] linear code C is an (n − k) × n such that Hx = 0 if
and only if x ∈ C. A code generated by H is known as the dual code and denoted by C ⊥ .
A decoding problem is given x ∈ Fn2 find a codeword c ∈ C that is closest to x. This
problem for a random linear code is called the general decoding problem and is known to
be NP-hard [4]. But for some codes this decoding problem can be solved efficiently. If
such an algorithm is available for a code C, we say that C has a decoder.

2.1

Quasi-Cyclic codes

A quasi-cyclic code (QCC) is a block linear code which is a simple generalisation of the
cyclic code. It is such that any cyclic shift of any codeword by m symbols gives another
codeword. We are particularly interested in m−1
m rate codes. In particular our system is
1
based on m−1
.
Such
codes
along
with quasi-cyclic codes of rate m
rate
codes
over
F
were
l
2
m
studied in great detail by Gulliver [10].
Definition 2.1 (Circulant matrix). A matrix is called circulant if every row, except for
the first row, is a circular right shift of the row above that.
A typical example of a circulant matrix

c0 c1
 cp−1 c0

 ..
..
 .
.
c1

of size p is
···
···
..
.

c2 · · ·
2

cp−1
cp−2
..
.
c0







A rate m−1
m systematic quasi-cyclic code has an p × mp parity check matrix of the form
H = [ Ip | C1 | C2 | . . . | Cm−1 ] where each Ci is a circulant matrix of size p and Ip is the
identity matrix of size p.
For compactness we denote H = [ I | C ]. In a recent work Aylaj et al. [1] found a way to
construct generator matrices for such codes over F2 . Since these generator matrices are in
systematic form one can easily construct parity check matrix from these generaor matrices.
As said previously, our main interest lies in codes over extension fields. Gulliver [10,
Chapter 6] shows that quasi-cyclic codes over extension fields can be MDS (maximum
distance separable) codes. As the name suggests, MDS codes can achieve large minimum
distance and so there would be no low weight codewords. This plays an imporatnt role
in the classical security of McEliece and Neiderreiter cryptosystems, such as the Stern’s
attack and the Lee-Brickell attack. Though Gulliver [10] only presents examples of MDS
1
, he does present a case to study quasi-cyclic codes of rate m−1
codes with rate m
m with
large minimum distances.

2.2

Decoding

Quasi-cyclic codes are well studied and well established codes and depending on how
one constructs them there are various decoders available. We briefly mention some of
them here. Gulliver [10, Appendix B] presents some ML (majority logic) decodable
QCCs. Another new and intersting way of decoding quasi-cyclic codes using Gröbner
basis formulation can be found in the work of Zeh and Ling [19].

2.3

Niederreiter Cryptosystem

Let H be a k × n parity check matrix for a [n, n − k] linear code C for which a fast decoding
algorithm exists. Let t be the number of errors that C can correct.
Private Key: (A0 ,H,B0 ) where A0 ∈ GLk (F2 ) and B0 is a permutation matrix of size n.
Public Key: H′ = A0 HB0 .
Encryption:
Let X be a n-bit plaintext with weight at most t. The corresponding ciphertext Y of
k-bits is obtained by calculating Y = H′ X T .
Decryption:
T
Compute y = A−1
0 Y. Thus y = HB0 X .

Using Gaussian elimination find a z such
t and Hz T = y.
 that weight of z is at most
T
T
T
T
Since y = HB0 X , H z − B0 X = 0. Hence we have z − X B0 ∈ C.
Now use fast decoding on z with H to get X B0T and thus recover X .

For further details on Niederreiter cryptosystem the reader is referred to [17, Chapter 6].

3

Classical Attacks

In this seciton we briefly go over the generic classical attacks against McEliece and Niederreiter cryptosystems. We also mention some attacks exploiting the circulant structures in
the keys. Interestingly, Li et al. [15, Section III] proved (see also [17, Theorem 6.4.1]) that
both McElice and Niederreiter cryptosystems are equivalent in terms of classical security.
The proof follows from the fact that the encryption equation for one can be reduced to
the other. This implies the equivalence of security of both the cryptosystems for attacks
that try to extract the plaintext from a ciphertext.
Most generic attacks over algebraic code based cryptosystems are information set decoding attacks(ISD). Two most popular ways of implementing ISD attacks are by Lee and
3

Brickell [14] and Stern [18]. As mentioned by Baldi et al. [3] ISD attacks are the best
known attacks with the least work factor as far as classical cryptanalysis is considered.
Hence these work factors are considered as security levels for a McEliece and Neiderreiter
cryptosystems.
The basic idea behind one of the attacks was suggested by McEliece himself. Lee and
Brickell [14] improved the attack and added an important verification step where attacker
confirms that recovered message is the correct one. In this case, we are dealing with
a McEliece cryptosystem over a [n, k] linear code. The strategy is based on repeatedly
selecting k bits at random from a n-bit ciphertext in hope that none of the selected
bits are part of the error. Similar attacks can also be implemented over Niederreiter
cryptosystems. Lee and Brickwell also provided a closed-form equation for complexity of
the attack. As our system is based on (n = mp, k = (m − 1)p, dmin = 2E + 1) code the
expression for minimal work factor (with α = β = 1 as taken by Lee and Brickell) takes
the following form
Wmin = W2 = T2 (m − 1)3 p3 + (m − 1)pN2







1
and Qi = Ei n−E
/ nk with N2 = 1 + k + k2 .
k−i
Q0 + Q1 + Q2
In Table 1 we present numerical data for work factor for diferent values of parameters.
Recently, Aylaj et al. [1] developed an algorithm to construct stack-circulant codes with
high error correcting capacity which makes the proposed Niederreiter cryptosystem much
more promising.
Other ISD attacks are based on a strategy given by Stern. To recover the intentional
′′
error vector e in a McEliece cryptosystem
 such strategies use an extension code C gen
′
M
. Bernstein et al. [5] later improved this attack.
erated by generator matrix M ′′ =
x
Probability of success and work factor for Stern’s attack is described in [12]. In the Table 1
we also provide probability of success for parameters l = 16 and Aw ≈ n − k. Both the parameters can be optimized further to obtain the least work factor but not much variation
is seen as we change any of these parameters. With such low probabilities, it is clear that
the work factor for Stern’s attack is worse than the Lee-Brickell attack. Even when one
considers improvements suggested by Bernstein et al. [5], Lee-Brickell’s [14] attack seems
to outperform the attack by Bernstein et al. as it produces speedup upto 12 times and
hence the security of the system against the Lee-Brickell attack should be considered the
security of the system. Key sizes should be devised according to that.
Another attack worth mentioning for quasi-cyclic codes is the attack on the dual code.
This attack works only if the dual code has really low weight codewords and is often
encountered only when sparse parity check matrices are involved. For example, McEliece
with QC-LDPC [3]. Such attacks can easily be stopped by choosing codes that do not
have low weight codewords. From the work of Aylaj et al. [1] this can be achieved.
After this discussion on classical security we now move towards quantum-security of
the proposed McEliece and Neiderreiter cryptosystems which is one of the major goal of
this paper.

where T2 =

4
4.1

Quantum Attacks
Hidden Shift and Hidden Subgroup problems

Quantum Fourier sampling works behind the scene for almost all known quantum algorithms. It is the reason Shor’s algorithm for factoring and solving the discrete logarithm
problem works. The main idea in this paper is to show that quantum Fourier sampling will
not work in some situations, in particular, a Niederreiter cryptosystem using quasi-linear
m−1
m codes.
4

However, before we go there let us briefly sketch how quantum Fourier sampling is used
to break a McEliece or Niederreiter cryptosystems. We recall, the scrambler-permutation
attack [7, Section 2]. This structural attack is exactly same for a McEliece or a Niederreiter
cryptosystem except that instead of finding a scrambler-permutation pair from generator
matrix M to M ′ one has to find scrambler-permutation pair from parity check matrix H
to H′ . The problem essentially remains the same. In this attack, we assume H and H′
are known, the attack is to find A and B. Notice that finding any A′ and B ′ such that
A′ HB ′ = H′ will also make the attack successful.
Definition 4.1 (Hidden Shift Problem). Let G be a group. Let f0 and f1 be two functions
from group G to a set X. Given f0 (g) = f1 (g0 g) the task is to find a constant g0 ∈ G.
Note that there can be many g0 that satisfy the above condition. Hidden shift problem asks
us to find any one of those constants.
Let M ′ = AM B. A Niederreiter cryptosystem will be broken if we find one possible
pair (A, B) from M and M ′ . Consider two functions from group G = GLk (F2 ) × Sn given
by
f0 (A, B) = A−1 M B
(1)
f1 (A, B) = A−1 M ′ B.
f0 ((A−1
0 , B0 ).(A, B)),

(2)
A−1
0 , B0

Then one can check that f1 (A, B) =
that is
is the shift
between f0 and f1 . Hence, if one can solve the hidden shift problem over G = GLk (F2 )×Sn
he can break the Niederreiter cryptosystem. The general procedure to solve this hidden
shift problem is to reduce it to a hidden subgroup problem.
Definition 4.2 (Hidden Subgroup Problem). Let G be a group and f a function1 from G
to a set X. We know that f (g0 ) = f (g1 ) if and only if g0 H = g1 H for some subgroup H.
The problem is, given f find a generating set for the unknown subgroup H.
We can now reduce the hidden shift problem with functions f0 and f1 defined above
on the group G = GLk (F2 ) × Sn to the hidden subgroup problem over (G × G) ⋊ Z2 [7,
Section 2.2]. The hidden subgroup in this case is
K = (((H0 , s−1 H0 s), 0) ∪ ((H0 s, s−1 H0 ), 1)),

(3)

where H0 = {(A, P ) ∈ GLk (F2 ) × Sn : A−1 MP = M} and s is a shift from f0 to f1 .
In short, the scrambler-permutation problem is one of the key ways to attack a Niederreiter cryptosystem. This problem can be formulated as a hidden shift problem which
further can be reduced to a hidden subgroup problem. So we can attack Niederreiter
cryptosystems by trying to solve a hidden subgroup problem over (G × G) ⋊ Z2 where
G = GLk (F2 ) × Sn .

4.2

Successful Quantum Attacks

In the previous section we saw that solving the hidden subgroup problem as a standard
way to attack a Niederreiter cryptosystem. An interesting question is, when is the hidden
subgroup problem hard to solve? This way we can ensure the security of a Niederreiter
cryptosystem against known quantum attacks.
We briefly sketch some thoughts behind effectiveness of QFS. The algorithm of QFS
in a general scenario and its use for solving the hidden subgroup problem is very well
explained by Grigni et al. [9]. Arguments particular to Niederreiter cryptosystems and
corresponding hidden subgroup problem are described in details by Dinh et al. [7, Section
3]. The standard model of QFS yields a probability distribution as a function of the hidden
subgroup. The basic idea behind indistinguisability of two subgroups H1 and H2 with
1

The function f in the hidden subgroup problem is said to be separating cosets of H as f is constant
on a each coset and different on different cosets.

5

probability distributions PH1 and PH2 is that PH1 and PH2 are very close. For the purpose
of defining closeness we need to define a metric on the space of probability distributions.
In this case, the metric chosen is the total variation distance between two distributions.
This follows from the work of Kempe and Shalev [13]. Later Dinh et al. [7] used the
L1 distance to define distinguishibility. Furthermore, the probability distribution for the
hidden subgroup problem with the identity subgroup gives us the uniform distribution [7,
Section 3.2]. When that is the case, QFS will not give us much information to solve
the hidden subgroup problem. Kempe and Shalev [13] provided a necessary condition to
distinguish a subgroup of Sn from the trivial subgroup hei. Later Dinh et al. [7] extended
this result while keeping the group relevant to a Niederreiter cryptosystem in mind. Their
result can be viewed as a study of the hidden subgroup problem for the group G =
(GLk (F2 )×Sn )2 ⋊Z2 which is the group for Niederreiter cryptosystems. They demonstrated
a case when the hidden subgroup H can not be distinguished from either its conjugate
subgroups gHg−1 or the trivial subgroup hei and proved a general result on a sufficient
condition for indistinguishibility [7, Theorem 4]. We use their result to prove that the
proposed Niederreiter cryptosystem is quantum-secure.
First note that weak Fourier sampling gives the same distributions for all the conjugate subgroups, i.e., PH is the same as PgHg−1 . Hence weak Fourier sampling can not
differentiate a subgroup from its conjugate subgroup. Thus it suffices to look at strong
Fourier sampling. Dinh et al. [7], inspired by the work of Kempe and Shalev [13] defines
distinguishability of a subgroup H by strong Fourier sampling.
Definition 4.3 (Distinguishability of a subgroup by strong QFS). We define distinguishability of a subgroup H of a group G, denote it by DH , to be the expectation of the squared
L1 distance between PgHg−1 and the uniform distribution, where g ∈ G. In other words,


DH := Eρ,g kPgHg−1 (·|ρ) − Phei (·|ρ)k21 .
A subgroup H is called indistinguishable by strong Fourier sampling if DH ≤ log −ω(1) |G|.
The ρ above belongs to the set of irreducible complex representations of the group G.
Note that if a subgroup H is indistinguishable according to this definition then by
Markov’s inequality, for all c > 0, kPgHg−1 (·|ρ) − P{e} (·|ρ)kt.v. ≤ log−c |G| which is analogous to the definition provided by Kempe and Shalev [13] for indistinguishability of a
subgroup by weak Fourier sampling.
We now define the minimal degree of a permutation group, the automorphism group
of a matrix (as defined by Dinh [7, Section 4.2]) and recall the definition of TM for a k × n
matrix M .
Definition 4.4 (Automorphism Group). The automorphism group of M is defined as
Aut(M) = {P ∈ Sn such that there exists A ∈ GLk (Fq ), AMP = M}.
Definition 4.5 (Minimal Degree). The minimal degree of a permutation group G 6 Sn
acting on set of n symbols is defined to be minimum number of elements moved by a
non-identity element of the group G.
Definition 4.6. Consider a k × n matrix M , we define TM for the matrix M = [ Ik |M ∗ ]
as TM = {P1 ∈ Sk such that there exists P2 ∈ Sn−k with P1 M ∗ P2 = M ∗ }.
We will use the following theorem which we state for the convinience of the reader.
2

Theorem 4.1 (Dinh et al. [7, Theorem 4]). Assume q k 6 nan for some constant 0 < a <
1/4. Let m be the minimal degree of the automorphism group Aut(M). Then for sufficiently
large n, the subgroup K, DK 6 O(|K|2 e−δm ), where δ > 0 is a constant.
6

5

The proposed Niederreiter cryptosystem

In this section we explain the proposed Niederreiter cryptosystem and establish its quantum security against the hidden subgroup attack.
Recall that our variant of the Niederreiter cryptosystem consists of a parity check
matrix H defined as follows: The matrix H is an array of circulants in the systematic
form2 , that is, H = [ C0 = I | C1 | C2 | . . . | Cm−1 ] where each Ci is a circulant matrix of
size p (a prime) over F2l . For simplicity let us denote [ C1 | C2 | . . . | Cm−1 ] as C so that
H = [ I | C ]. Recall the conditions of the parity check matrix H from Section 1. A parity
check matrix H satisfying these conditions is easy to construct. We present a way to
do so in the next section. Before that, we prove security of the proposed Niederreiter
cryptosystem against quantum attacks.

5.1

Proof of indistinguishability of the hidden subgroup

We prove indistinguishibility in a sequence of lemmas.
Lemma 5.1. Let P ∈ Aut(H) then P = P1 ⊕ P2 where P1 is a block of size p and P2 is
a block of size (m − 1)p and P1 ⊕ P2 is a block diagonal matrix of size mp × mp with the
top block P1 and the bottom block P2 .
Proof. Let P ∈ Aut(H), from the definition of automorphism there is an A such that
AHP = H. This implies that
A [ I | C ] P = [ A | AC ] P = [ I | C ] .
As action of right multiplication by a permutation matrix permute columns, the above
equality shows that [ A | AC ] has same columns as [ I | C ] possibly in different order. Now
since every column of C contains an entry from a proper extension of Fq , no column of
A can be column of C. This forces A to have same columns as I and AC to have same
columns as that of C. Hence P permutes first p columns within themselves and last
(m − 1)p columns in themselves. Hence every P ∈ Aut(H) can be broken into P1 ⊕ P2 so
that P1 acts on I and P2 acts on C.
An obvious corollary follows:
Corollary 5.2. If P ∈ Aut(H) then the corresponding A ∈ Sk .
The next lemma is central to quantum-security. It gives us a way to move from H to C
by noting, the P1 from the P ∈ Aut(H) is actually a member of TH .
Lemma 5.3. The cardinality of Aut(H) is the cardinality of the set {(P1 , P2 )} that satisfy
P1 CP2 = C where H = [ I | C ] as defined earlier.
Proof. The proof follows from the fact, if P belongs to Aut(H), then P = P1 ⊕ P2 . Then
A [ I | C ] P = [ I | C ] translates into A [ I | C ] (P1 ⊕ P2 ) = [ I | C ]. Keeping in mind the
block diagonal nature of P , it follows that [ AIP1 | ACP2 ] = [ I | C ]. Then A = P1−1 and
P1−1 CP2 = C. This proves the lemma.
The next lemma proves that for each P1 there is atmost one P2 .
Lemma 5.4. Cardinality of the set {(P1 , P2 ) that satisfy P1 CP2 = C} equals |TH |.
Proof. Recall that TH = {P1 that satisfy P1 CP2 = C}. So it suffices to show that for
every P1 there is at most one P2 . Since no two columns of C are identical, no two columns
of P1 C are identical. Hence, there is at most one way to re-order them to get back C.
Thus for every P1 there is at most one P2 .
2

A systematic matrix is a matrix whose first block is the identity.

7

Theorem 5.5 (Burnside [8, Theorem 3.5B]). Let G be a subgroup of Sym(Fp ) containing
a p-cycle µ : ξ 7→ ξ + 1. Then G is either 2-transitive or G ≤ AGL1 (Fp ) where AGL1 (Fp )
is the affine group over p.
We prove a theorem on the size of the automorphism group of H.
Theorem 5.6. If H satisfies conditions I,II and III then |Aut(H)| 6 p(p − 1).
Proof. From Lemma 5.3 and Lemma 5.4, the group Aut(H) has same size as TH . It is
now easy to check that the circulant matrix µ with first row [0, 1, 0, . . . , 0] of size p belongs
to TH . The corresponding P2 will be a block diagonal (m − 1)p matrix with blocks of
size p and each consisting of µ−1 . Now notice that the circulant matrix µ corresponds to
the p-cycle ξ 7→ ξ + 1. By our condition III, TH is not 2-transitive. Now by Burnside’s
theorem TH ≤ AGL1 (Fp ). Thus |Aut(H)| 6 p(p − 1).
After this bound on the size of the automorphism group we move towards the minimal
degree of the Automorphism group.
Lemma 5.7. The minimal degree of Aut(H) is bounded below by p − 1.
Proof. Notice that any P ∈ Aut(H) = P1 ⊕ P2 . By the twist, from P ∈ Aut(H) to
P1−1 ∈ TH , it is easy to see that P1 ∈ AGLk (Fq ). Then P1 (x) = ax + b (mod q) for some
a, b ∈ Fq . If P fixes two distinct points, then a = 1 and b = 0 is the only possible solution.
This corresponds to the identity element and thus a non-identity element can not fix more
that one point. So minimal degree of Aut(H) is bounded below by p − 1.
We now prove the main theorem of this paper.
Theorem 5.8. Let p be a prime and m a positive integer bounded above by a polynomial
in p, such that, p ≤ 14 m (log m + log p). Then the subgroup K (Equation 3) defined above
is indistinguishable.
Proof. We will use Theorem 4.1 in this proof. First note, the minimal degree is bounded
below by p − 1. Now it is well known that |K| = 2|H0 |2 and |H0 | = |Aut(H)| × |Fix(H)|.
We have shown that |Aut(H)| ≤ p(p − 1) and it is easy to see that |Fix(H)| = 1. Putting
all these together, we see that |K|2 e−δp ≤ 4p8 e−δp for some positive constant δ. However,
from the bound on the size of m, it is obviously true that 4p8 e−δp ≤ (mp log (mp))−ω(1)
for large enough p.
2
Now, if p ≤ am (log m + log p), then p2 ≤ amp (log m + log p) which gives 2p ≤
(mp)amp for 0 < a < 41 . This satisfies the premise of Theorem 4.1 and hence K is indistinguishable.

5.2

Construction of required parity check matrix

Now we address the last question about the proposed Niederreiter cryptosystem, how to
construct a matrix H satisfying conditions I - V? Clearly, conditions I, II and III are trivial
to set up and deserve no special attention. We suggest a particular way for construction
of parity check matrix H so that condition IV is satisfied. It should be noted that there
may be other ways to satisfy condition IV as well.
Choose a pair of distinct elements a, b ∈ Fql . Now construct H such that C1 contains
both a and b exactly once in each column and no other Ci contains both a and b. We
restate this condition as our condition IV′ . We could have replaced C1 by any other Ci
for i > 1 and the proof remains the same. For sake of simplicity we stick with C1 .
IV′ Two distinct elements a, b ∈ Fql occurs as entries of C1 exactly once in each column
and no other Ci contain both a and b.
Lemma 5.9. If the matrix H satisfies IV′ , it also satisfies IV.
8

Proof. Let P1 ∈ TH . From P1 CP2 = C it follows that P1 C should have the same set
of columns as C but possibly in a different order. Let α denote the row of a in the first
column of C1 and β denote the row of b in the same column. Now notice that every column
in C that contains both a and b contains them such that difference between rows of a and
b is α − β mod p where p is the size of each circulant matrix. Now let σ ∈ TH such that it
sends β to α and α to β. It then follows from the fact that p is a odd prime, α = β which
contadicts our assumption. Hence, TH is not 2 transitive.
Condition V can be easily satisfied using brute force and other means and this completes the construction of a parity check matrix H satisfying I - V and hence, a Niederreiter cryptosystem that resists quantum Fourier sampling is found.

6

Advantages of the proposed cryptosystem

One of the prime advantages of our proposed cryptosystem is quantum-security. Apart
from that it also has high transmission rate which translated into high encryption rate. It is
known that the current McEliece cryptosystem built on Goppa codes has transmission rate
of about 0.52. For a McEliece cryptosystem its rate is same as that of the transmission rate
of the underlying code and is nk . Niederreiter cryptosystems have a slightly different rates
due to diffrence in their encrytion algorithm. For a general cryptosystem its encryption
rate or information rate can be defined as follows [17, Chapter 6]:
Let S(C) denote possible number of palintexts and T (C) denote possible number of
ciphertexts then information rate of the system is defined by
R(C) =

log S(C)
.
log T (C)

This information rate can be viewed as amount of information contained in one bit of
ciphertext.
Our proposed Niederreiter cryptosystem have good encrytion rate (see Table 1). This
gives the proposed cryptosystem an edge over those constructed on classical Goppa codes
or with GRS codes (generlised Reed-Solomn codes).
As discussed before another problem with McEliece and Niederreiter cryptosystems is
large key size. Circulant matrices seems like a good choice when it comes to key-sizes.
Matrices are 2-dimensional objects but circulant matrices behave like a 1-dimensional
object as they can be described by their first row. Though this circulant structure is
lost in public key due to the scrambler-permutation pair, the size of the key still remains
smaller than the conventional Neiderreiter cryptosystem. Our system is slightly better
than original Niederreiter cryptosystem because of the less number of rows in the public
key matrices. With p = 101, this number is less than one-tenth of the original Niederreiter
cryptosystem. Though there are two factors that increase size of matries in our variant
compared to original McEliece: one, our matrices have large number of columns and two,
our system is based on extension field F2l which makes the effective size of the matrix l
times compared to McEliece which is based on F2 . However, in most cases due to very less
number of rows the net result indicates that our system requires shorter keys than original
McEliece. For instance, at 80-bit security with p = 101 and l = 3 our keys are almost half
of the keys corresponding to original McEliece at same security level. At 256-bit security
level with p = 211, t = 40 and l = 3 the proposed cryptosystem has key size of about
one-forth of the original McEliece.
In Table 1, we provide some parameters for the proposed Niederreiter cryptosystem
and show in details the benefits of the proposed cryptosystem. There are two kind of
attacks – classical and quantum. For the classical we come out with a value of m and call
it mC and for quantum we call it mQ . The maximim of these two is the m that one should
use for that said parameter. As explained earlier we use p for the size of the matrix and t
9

Table 1: Parameters for the proposed Niederreiter cryptosystem
Security
p
t mC mQ m Probability Public Key Size
in bits
of success No. rows No. cols
101
80-bits
211
101
100-bits
211
101
120-bits
211
256-bits

211

Rate

15
20
35
40

17
9
4
3

35
35
62
62

35
35
62
62

2−132
2−190
2−398
2−465

101
101
211
211

3535
3535
13082
13082

0.60
0.77
0.71
0.80

15
20
35
40

40
17
5
5

35
35
62
62

40
35
62
62

2−136
2−190
2−398
2−465

101
101
211
211

4040
3535
13082
13082

0.61
0.77
0.71
0.80

15
20
35
40

95
32
8
6

35
35
62
62

95
35
62
62

2−171
2−190
2−398
2−465

101
101
211
211

9595
3535
13082
13082

0.67
0.77
0.71
0.80

35
20

98
55

62
62

98
62

2−443
2−465

211
211

20678
13082

0.75
0.80

as the error correcting capacity. We also provide success probability from classical attack,
key size and the rate of the cryptosystem.

7

Conclusion

In this paper, we develop a Niederreiter cryptosystem using quasi-cyclic codes that is both
classically and quantum secure against the current known attacks. In particular, we show
that for the proposed cryptosystem the hidden subgroup problem from the natural reduction of the corresponding scrambler-permutation problem is indistinguishable by quantum
Fourier sampling. We also show that the proposed cryptosystem has high encryption rate
and shorter keys compared to classical McEliece cryptosystems. One of the important
problem that needs to be addressed is finding quasi-cyclic codes that satisfy the suggested
parameter sizes. It would be interesting to see if the cryptosystem remains classically
secure if we use other sparse keys. It is very clear that the system remains secure against
quantum computers as the group structure for the system remains the same. This is
important because it could reduce key sizes substantially.

References
[1] Bouchaib Aylaj, Mostafa Belkasmi, Said Nouh, and Hamid Zouaki. Good quasi-cyclic
codes from circulant matrices concatenation using a heuristic model. International
journal of advanced computer science and applications, 7(9):63–68, 2016.
[2] Marco Baldi, Marco Bianchi, Franco Chiaralunce, Joachim Rosenthal, and Davide
Schipani. Enhanced public key security for the McEliece cryptosystem. Journal of
Cryptology, 29(1):1–27, 2016.
[3] Marco Baldi, Marco Bodrato, and Franco Chiaraluce. A new analysis of the McEliece
cryptosystem based on QC-LDPC codes. Security and Cryptography for Networks,
pages 246–262, 2008.
10

[4] Elwyn Berlekamp, Robert McEliece, and Henk Van Tilborg. On the inherent intractability of certain coding problems (corresp.). IEEE Transactions on Information
Theory, 24(3):384–386, 1978.
[5] Daniel J. Bernstein, Tanja Lange, and Christiane Peters. Attacking and defending
the McEliece cryptosystem. In Post-Quantum Cryptography. PQCrypto 2008, pages
31–46.
[6] Richard E. Blahut. Algebraic codes for data transmission. Cambridge University
Press, 2003.
[7] Hang Dinh, Cristopher Moore, and Alexander Russell. McEliece and Niederreiter
cryptosystems that resist quantum fourier sampling attacks. volume 6841 of LNCS,
2011. CRYPTO2011.
[8] J. D. Dixon and B. Mortimer. Permutation Groups. Graduate Texts in Mathematics.
Springer, New York, 1996.
[9] Michelangelo Grigni, Leonard Schulman, Monica Vazirani, and Umesh Vazirani.
Quantum mechanical algorithms for the nonabelian hidden subgroup problem. In
Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages
68–74. ACM, 2001.
[10] Thomas A. Gulliver. Construction of quasi-cyclic codes. PhD thesis, University of
Victoria, 1989.
[11] Sean Hallgrean, Alexander Russell, and Amnon Ta-Shma. The hidden subgroup
problem and quantum computation using group representation. SIAM Journal of
Computation, 32(4):916–934, 2003.
[12] M. Hirotomo, M. Mohri, and M. Morii. A probabilistic computation method for the
weight distribution of low-density parity-check codes. In International Symposium on
Information Theory, 2005.
[13] Julia Kempe and Aner Shalev. The hidden subgroup problem and permutation group
theory. In Proceedings of the sixteenth annual ACM-SIAM symposium on discrete
algorithms, pages 1118–1125. Society for Industrial and Applied Mathematics, 2005.
[14] Pil Joong Lee and Ernest F Brickell. An observation on the security of McEliece’s
public-key cryptosystem. In Eurocrypt 1988, volume 330 of LNCS, pages 275–280.
Springer, 1988.
[15] Yuan Xing Li, Robert H Deng, and Xin Mei Wang. On the equivalence of McEliece’s
and Niederreiter’s public-key cryptosystems. IEEE Transactions on Information Theory, 40(1):271–273, 1994.
[16] R. J. McElice. A public key cryptosystem based on algebraic coding theory. Technical
report, Communications system research centre, NASA, Jan-Feb 1978.
[17] Harald Niederreiter and Chaoping Xing. Algebraic Geometry in Coding Theory and
Cryptography. Princeton University Press, 2009.
[18] Jacques Stern. A method for finding codewords of small weight. In International
Colloquium on Coding Theory and Applications, pages 106–113. Springer, 1988.
[19] Alexander Zeh and San Ling. Decoding of quasi-cyclic codes up to a new lower bound
on the minimum distance. In 2014 IEEE International Symposium on Information
Theory, Honolulu, HI, 2014.

11

