Structural Properties of Twisted Reed–Solomon
Codes with Applications to Cryptography
Peter Beelen1 , Martin Bossert2 , Sven Puchinger2 , and Johan Rosenkilde1

arXiv:1801.07003v1 [] 22 Jan 2018

1

Department of Applied Mathematics & Computer Science, Technical University of Denmark, Lyngby, Denmark
2
Institute of Communications Engineering, Ulm University, Ulm, Germany
Email: pabe@dtu.dk, martin.bossert@uni-ulm.de, sven.puchinger@uni-ulm.de, jsrn@jsrn.dk

add sufficiently many twists. The last attack – Wieschebrink’s
attack on the dual code – does not apply in any obvious way,
but could conceivably apply in a surprising manner. The
number of twists in our codes is ` = b R1 c for long enough
codes, where R is the code rate.
`
The new codes are over large fields with field size q ≈ n2 .
This increases the size of storing the public key at a given
length and dimension, i.e. the generator matrix, but since the
complexities of generic attacks strongly depend on the field
size, quite short lengths are sufficient for a target security
level. We give example parameters for security levels 2100
and 2128 whose public key sizes are reduced by factors 2.7
I. INTRODUCTION
and 7.4 compared to suggested parameters when using binary
Twisted Reed–Solomon codes [1] are maximum distance Goppa codes [10], [11] for the same security levels.
Notationally, matrices and vectors are generally bold-face,
separable (MDS) codes1 that can be efficiently decoded.
e.g.
A and v. If v is a vector, then vi denotes its i’th element.
Their construction is based on Reed–Solomon (RS) codes,
When
adding a constant to a vector, e.g. v+1, we really mean
by adding an extra monomial (“twist”) to the low-degree
v
+
(1,
. . . , 1). The diagonal matrix with diagonal entries v
evaluation polynomials and choosing the evaluation points
is
denoted
diag(v). We say that two codes are “equivalent”
in a suitable way.
if
one
can
be
obtained from the other by permuting positions
We present a generalisation of twisted RS codes, where
and
element-wise
scaling with non-zero field elements.
instead of one additional monomial, we add ` monomials
(“twists”) to the evaluation polynomials, similar to the recent
I I . M U LT I - T W I S T E D R E E D – S O L O M O N C O D E S
extension of twisted Gabidulin codes [2]. We describe a large
family of these which are MDS codes. We study the Schur A. Definition
square of twisted RS code and show that, unlike for RS codes,
Let V ⊂ Fq [X] be a Fq -linear subspace of polynomials.
the dimension of the Schur square is not small. Moreover,
Let α1 , . . . , αn ∈ Fq be distinct and write α = [α1 , . . . , αn ].
we prove that the dual of a large class of twisted RS codes
We call α1 , . . . , αn the evaluation points. Then we define
is equivalent to a twisted RS code. Finally, we show that
the evaluation map of α on V by
decoding is feasible for codes with few twists.
As a potential application, we consider the use of twisted
evα (·) : V → Fnq , f 7→ [f (α1 ), . . . , f (αn )].
RS codes in the McEliece cryptosystem [3], which is a
public-key cryptosystem and one of the candidates for post- In this notation, an [n, k] Reed–Solomon (RS) code with
quantum cryptography: a structured code C with an efficient evaluation points α is just the image of evα (Fq [X]<k ), where
decoding algorithm is the “secret key”, while an obfuscated Fq [X]<k denotes the set of polynomials in Fq [X] of degree
generator matrix G̃ of C is made public, together with the at most k − 1. A generalised Reed–Solomon code (GRS) is
decoding algorithm’s decoding radius τ . Encryption consists a code which is equivalent to an RS code.
Definition 1: Given a finite field Fq and code parameters
of encoding a secret message with G̃ and adding τ errors
[n,
k], let ` ∈ Z>0 and t, h ∈ Z`>0 such that
at random. A “structural attack” on the system is to recover
an efficiently decodable code that is sufficiently close to C
• The ti are all distinct and 1 ≤ ti ≤ n − k.
so that decoding the encrypted message is feasible. Such
• The hi are all distinct and 0 ≤ hi < k.
an attack is mostly interesting if it is faster than a generic Furthermore, let η ∈ (F \ {0})` . The set of (t, h, η)-twisted
q
decoding algorithm, e.g. information-set decoding see e.g. [3], polynomials is given as:
[4], [24]. The original proposal [3], which remains unbroken,


`
uses binary Goppa codes. For most other proposed codes,
k−1

X
X
n,k
Pt,h,η
=
fi X i +
ηj fhj X k−1+tj fi ∈ Fq .
efficient structural attacks have been found (cf. [5]). Attacks


i=0
j=1
on RS-like codes were presented in [6]–[9].
We single out a family of twisted RS codes for which all
n,k
but one of these attacks will provably not work, provided we Pt,h,η is a k-dimensional Fq -linear subspace of Fq [X]. We
say that the space of polynomials has ` twists, each with
1 Their length n, dimension k, and minimum distance d fulfil d = n−k+1.
twist ti , hook hi and coefficient ηi .

Abstract—We present a generalisation of Twisted Reed–
Solomon codes containing a new large class of MDS codes.
We prove that the code class contains a large subfamily that
is closed under duality. Furthermore, we study the Schur
squares of the new codes and show that their dimension is
often large. Using these structural properties, we single out a
subfamily of the new codes which could be considered for codebased cryptography: we show that these codes resist existing
structural attacks for Reed–Solomon-like codes, i.e. methods for
retrieving the code parameters from an obfuscated generator
matrix.
Index Terms—MDS Codes, Reed–Solomon Codes, McEliece
Cryptosystem, Structural Attacks

P`
decode r −evα ( i=1 gi ηi X ti +k−1 ) as if it is a codeword in
the [n, k] RS code with evaluation points α. This will succeed
when
gi = fhi for i = 1, . . . , `, where evα (f ) is the sent
n,k
`
n,k
C n,k (α, t, h, η) = evα (Pt,h,η
) ⊆ Fnq .
codeword and f ∈ Pt,h,η
. This requires q ` ≥ n`2 rounds of
For brevity, we will use the phrase twisted RS codes. Note that RS decoding to succeed. Some of these rounds might output
C n,k (α, t, h, η) indeed has dimension k since the evaluation purported message polynomials fˆ0 +. . .+fˆk−1 xk−1 for which
n,k
map is injective: any polynomial f ∈ Pt,h,η
satisfies deg f ≤ gi 6= fˆhi : these will not correspond to close codewords in
the twisted RS code and should be sifted away.
k − 1 + maxi {ti } < n.
This will be a τ -error correcting decoder for C when using a
The twisted RS codes of [1] are the special case of the
τ
-error
correcting RS decoder – even if the minimum distance
above definition when ` = 1; these will be referred to as
of
the
twisted
RS code is much lower than n−k+1. Of course,
“single-twisted RS codes”. Specifically, the (∗)-twisted codes
n,k
in
spite
of
the
many decoding attempts, the usual bounds apply
introduced in [1] are the codes C (α, 1, 0, η), where the
to
the
number
of successful decoded words (after sifting
set of coordinates α is a subset of {0} ∪ G for a proper
∗
k −1
∗
away
spurious
RS
decoding successes): if C is MDS and
subgroup G of Fq and (−1) η ∈ Fq \ G. The (+)-twisted
n−k
n,k
τ
=
b
then
there
can be at most 1 successful decoding.
c,
codes from [1] were defined as C (α, 1, k − 1, η), where
2
Similarly,
if
we
use
an
RS list-decoder, e.g. the Guruswami–
the set of coordinates α is a subset of {∞} ∪ V for a proper
−1
Sudan
algorithm
[12],
then
the total output list size will be
subspace V of Fq and η ∈ Fq \ V . Note that in [1] we
bounded
by
the
Johnson
bound
[13] or the stronger Cassuto–
defined evaluation at ∞, but that in the current paper we for
Bruck
bound
[14].
simplicity refrain from using ∞ as an evaluation point.
The complexity will be q ` times the cost of the RS
B. A Constructive Class of MDS Twisted RS Codes
decoder. The current best complexity for half-the-minimum
Not all twisted RS codes as defined in the previous section distance RS decoding is O(n log2 n log log n) operations in
are MDS. We will now describe a simple way to choose Fq [15], while list-decoding up to the Johnson radius using
the parameters which lead to a large family of MDS codes. the Guruswami–Sudan algorithm has a Las Vegas randomized
This generalises a construction in [1] and is also inspired by algorithm in O(m4 n(log2 (mn) + log(q)) log log(mn)) opera recently proposed family of twisted Gabidulin codes [2] ations in Fq [16], [17], where m is the “list size” parameter of
which are MRD, i.e., MDS with respect to the rank metric. the decoder. In either case, the twisted RS decoder then has a
Consider some [n, k] `-twisted RS code C n,k (α, t, h, η) complexity of O∼(n`2` +1 4` ) bit operations, ignoring ` log(n)and write H = {hi | i = 1, . . . , `}. A generator matrix factors, considering m a constant, and assuming q ∈ O(n2` ).
G ∈ Fq [η]k×n for C n,k (α, t, h, η) can be obtained as the m can be considered a constant if one takes τ = (1 − )J
n,k
n,k
p
image of evα on the monomial-like basis of Pt,h,η
; that is, for some constant  < 1, where J
=
n
−
n(k
−
1)
is
n,k
row j of G equals evα (xj ) if j ∈
/ H, while row hi equals the Johnson radius.
evα (xhi + ηi xk−1+ti ). Recall that C n,k (α, t, h, η) is MDS
Hence, decoding is feasible only for a very small number
if and only if any k columns of G are linearly independent. of twists, e.g., ` = 1, 2, and finding more efficient algorithms
Theorem 1: Let s0 , . . . , s` ∈ Z≥0 such that Fs0 ( Fs1 ( is an open problem.
· · · ( Fs` = Fq is a chain of subfields. Let k < n ≤ s0
and α1 , . . . , αn ∈ Fs0 be distinct, and let t, h, and η be
I I I . S T RU C T U R A L P RO P E RT I E S
chosen as in Section II-A and such that ηi ∈ Fsi \ Fsi−1 for
A. Duals
i = 1, . . . , `. Then C n,k (α, t, h, η) is MDS.
Proof: We will prove that any k × k sub-matrix of G Twisted RS codes as defined in Definition 1 do not generally
is invertible, where G is the generator matrix defined above. seem to be closed under duality; however, if we choose
Consider an arbitrary such sub-matrix
that det Ĝ will evaluation points which form a multiplicative group, then
Q Ĝ. Note
Q
hj
`
i
they are:
α
equal a sum of terms of the form i∈H
/
j=1 (ασ(hj ) +
σ(i)
Theorem 2: Let α1 , . . . , αn be a multiplicative subgroup
k−1+tj
ηj ασ(hj ) ) ranging over all k-permutations σ. In particof F∗q and let C n,k (α, t, h, η) be some twisted RS code
ular, we can write det Ĝ = η` u` + v` where u` , v` ∈ with α = [α1 , . . . , αn ]. Then C n,k (α, t, h, η)⊥ equals
Fs0 [η1 , . . . , η`−1 ] ⊆ Fs`−1 and both of total degree at most C n,n−k (α, k − h, n − k − t, −η) up to column multipliers.
1 in the η1 , . . . , η`−1 . Since η` ∈
/ Fs`−1 then det Ĝ = 0 only
Proof: Let J be the matrix with 1’s on the anti-diagonal
if u` = v` = 0. We can continue similarly and write both u` and zeroes elsewhere of suitable size. Left-multiplying by J
and v` as linear expressions in η`−1 over Fs0 [η1 , . . . , η`−2 ] reverses rows while right-multiplying reverses columns. We
and conclude that their coefficients all needs to be identically denote by V the n × n Vandermonde matrix over α, i.e.
zero for u` = v` = 0. Continuing with the remaining ηi , we
V := [αij−1 ]i=1,...,n .
finally conclude that det Ĝ = 0 is only possible if a set of
j=1,...,k
linear expressions of the form η1 u1 + v1 with u1 , v1 ∈ Fs0
are all identically 0 – which none of them can be. Thus Ĝ is Since the entries of α form a multiplicative group, we have
n
invertible, and since Ĝ was chosen arbitrarily, this finishes αi = 1 for all i and by [18], we obtain
−1
the proof.
VT
= J · V · diag(α/n)
Note that this construction produces quite short codes: if
2`
we use ` twists, then the field size q has q ≥ n , where n Similar to Section II-A, a generator matrix of C n,k (α, t, h, η)
is the length.
is given by G = [I | L] · V , where
(
C. Decoding by brute-forcing the twists
ηµ , if (i, j) = (hµ + 1, tµ )
n,k
Lij =
A simple decoding strategy for C = C (α, t, h, η) with
0,
else.
` twists is to guess ` coefficients g , . . . , g ∈ F and then
A (t, h, η)-twisted Reed–Solomon code is given by α ∈ Fnq
n,k
with distinct entries and twisted polynomials Pt,h,η
as:

1

`

q

We claim that a parity check matrix for C n,k (α, t, h, η) is:
H = [I | −J LT J ] · V · diag(α/n) .
H has rank n − k so left is to show G · H T = 0. Note that
T

T

−1 T

H = J [−L | I]J V diag(α/n) = J [−L | I](V ) .


−L T
T
Therefore, G · H = [I | L]
J = 0 and the entries
I
T
of −J L J are of the form
(
−ηµ , (i, j) = (n − k − tµ + 1, k − hµ )
(−J LT J )[i, j] =
0,
else.
hµ

Proof: This follows from {d ∈ D | d < n} ⊂ D.
This corollary is usually easy to apply: let S be the degrees
n,k
occurring in the usual monomial-like basis of Pt,h,η
, i.e.:
S = ({0, . . . , k − 1} \ {hi }i=1,...,` ) ∪ {ti + k − 1}i=1,...,` .
Then D = {d1 + d2 | d1 , d2 ∈ S} ∩ {0, . . . , n − 1}.
C. Separation from GRS codes
Consider a twisted RS code C. Since twisted RS codes are
close kin to GRS codes, one can consider the question of
finding GRS codes D I N N , D O U T such that
DI N N ⊂ C ⊂ DO U T ,

k−1+tµ

In other words, a twist x + ηµ x
becomes the twist
xn−k−tµ + (−ηµ )x(n−k−1)+(k−hµ ) in the dual code. This
proves the claim.
Note that Theorem 2 implies that the dual of a (∗)-twisted
code from [1] is equivalent to a (∗)-twisted code as long as
0 is not a coordinate of α.

while maximising dim D I N N and minimising dim D O U T ,
i.e. the “separation” of C from GRS codes. Note that
C ⊂ D O U T ⇐⇒ (D O U T )⊥ ⊂ C ⊥ and that (D O U T )⊥ is a
GRS code itself where we now try to maximise dim(D O U T )⊥ .
When applying the codes to cryptography, we will motivate
further why we consider these questions.
The following three statements separate any code C from
B. Schur Squares
GRS
codes from above and below based entirely on the
There has been a rising interest in the Schur product of
dimension
of C 2 . Since we saw in the preceding section that
codes both as an independent object of study, but also due
to its occurrence in applications of codes, see e.g. [19], [20] many twisted RS codes have large Schur square, this provides
codes.
and references therein. In particular, it is key in the structural separation from GRS
n,k
Lemma
5:
Let
C
(α,
t, h, η) be a twisted RS code. Then
attacks on the McEliece cryptosystem using certain Goppa
n,k
C
(α,
t,
h,
η)
contains
an
RS code of dimension mini {hi }
codes or other RS-like codes [9].
and
is
contained
in
an
RS
code
of dimension k + maxi ti .
Definition 2: The Schur product, or component-wise prodProof:
This
follows
from
the
observations that
n
uct, of two vectors x, y ∈ F is
q

x ? y := [x1 · y1 , . . . , xn · yn ] .
The Schur product of two linear codes C1 , C2 ⊆ Fnq is the set
C1 ? C2 := hc1 ? c2 | c1 ∈ C1 , c2 ∈ C2 iFq .
We write C 2 := C ? C for the Schur square code.
It is easy to see that for an [n, k] code C, then dim C 2 ≤
min{n, 12 k(k−1)}. Furthermore, if C is MDS then dim C 2 ≥
min{2k−1, n} [20, p.31]. GRS codes attain this lower bound
with equality.
Since twisted RS codes are obtained by evaluating specific
polynomials, we show below how to obtain a lower bound
for the dimension of its Schur square. For a given evaluation
vector α, we denote for a polynomial
Qn f ∈ Fq [X] by f the
polynomial remainder of f modulo i=1 (X − αi ). Then we
obtain the following:
n,k
Theorem 3: Let D = {deg(f · g) | f, g ∈ Pt,h,η
}. Then
dim C n,k (α, t, h, η)2 ≥ #D.
Proof: First of all note that evα (f ) = evα (f ), since
the
evaluation
map evα (·) vanishes on any multiple of
Qn
(X
−
α
).
Further, the evaluation map evα (·) is an
i
i=1
injective homomorphism on Fq [X]<n , the space of polynomials of degree at most n − 1. This implies that
n,k
dim C n,k (α, t, h, η)2 = dimhf · g | f, g ∈ Pt,h,η
i ≥ #D.

n,k
{xj | 0 ≤ j ≤ min{hi } − 1} ⊂ Pt,h,η
⊂
i

j

{x | 0 ≤ j ≤ k − 1 + max{ti }} .
i

The description in the preceding section on the Schur square
dim C 2 of a twisted RS code C gives a way to prove C is
non-GRS: if dim C 2 > 2k−1, or if dim(C ⊥ )2 > 2(n−k)−1,
then it must be non-GRS. This can be strengthened to bound
the dimension of the smallest GRS code which contains C
or C ⊥ supplementing the observation from Lemma 5.
Proposition 6: Let C be an [n, k] code with k < n/2 and
such that dim C 2 = 2k − 1 + δ for δ > 0. Then if D O U T is
a GRS code with C ⊆ D O U T , then dim D O U T ≥ k + δ/2.
Proof: Since C 2 ⊆ D2O U T then dim(D2O U T ) ≥ 2k − 1 + δ
i.e. dim(D O U T ) ≥ k + δ/2.
Proposition 7: Let C be an [n, k] code with k < n/2 and
such that dim C 2 = 2k − 1 + δ for δ > 0. If D I N N is a GRS
code with D I N N ⊆ C, then
q
2
k − 52 − 2δ + 52 .
dim D I N N ≤
Proof: Let K = dim D I N N . Pick a basis c1 , . . . , cK of
D I N N and extend this basis with k − K vectors cK+1 , . . . , ck
to form a basis for C. Then C 2 must be spanned by a basis
of D2I N N together with all Schur products ci ? cj with 1 ≤
i ≤ K < j ≤ k, together with all Schur products ci ? cj with
K < i, j ≤ k. In total

Especially if the evaluation vector consists of elements of a
multiplicative subgroup of F∗q , theQ
bound in the theorem is dim C 2 ≤ (2K − 1) + K(k − K) + 21 (k − K)(k − K − 1) .
n
easy to compute, since in that case i=1 (X − αi ) = X n − 1.


5 2
5 2
Alternatively, the bound implies the following simpler This implies K − 2 ≤ k − 2 − 2δ.
Remark 8: A simpler question than separation from GRS
formulation for which no remainders need be computed:
n,k
codes
is simply inequivalence to GRS codes. We considered
Corollary 4: Let D = {deg(f · g) | f, g ∈ Pt,h,η }. Then,
this question for single-twisted RS codes in [1], using different
dim C n,k (α, t, h, η)2 ≥ #{d ∈ D | d < n}.
tools; unfortunately the proof of [1, Theorem 18] contains a

mistake and its statement is not true in general. However, the
Schur square arguments above show that still most twisted
RS codes are not GRS codes.

Remark 11: It is not hard to come up with more twisted RS
codes of Schur square dimension n. The crucial ingredient
n,k
of the proof of Theorem 10 is that x0 , . . . , xr−1 ∈ Pt,h,η
.
As long as all hooks hi are at least r, then the argument
I V. A P P L I E D T O T H E M C E L I E C E C R Y P T O S Y S T E M
will work. The reason for setting h1 as small as possible
In this section, we present a subfamily of twisted RS codes is discussed in the following section, but the remaining hi
which provably resist the known structural attacks on RS-like could be chosen as any subset of {r + 1, . . . , k − 1}. Further,
codes by Sidelnikov–Shestakov [6] and Couvreur et al. [9]. whenever (` + 2)r is much bigger than n − 1, the choice of ti
Wieschebrink’s attack [7], [8] is inefficient when applied to can be perturbed in many ways; this will e.g. always be the
the code itself, and not obviously efficient on the dual code. case if ` is chosen above the minimal possible value. Lastly,
Definition 3: Choose
√ positive integers k < n ≤ q0 with q0 we can allow independent permutations of the ti and the ηi .
a prime power and 2 n + 4 < k ≤ n2 . Furthermore, choose
√
n+1
√ −2 < ` < min{k+1; 2n −2;
` ∈ Z≥0 such that k−
n− B. Resistance to Sidelnikov–Shestakov & Wieschebrink attack
k
n
n+1
2`
The Sidelnikov–Shestakov (SiS) attack [6] completely
2}. Let r := d `+2 e, let q = q0 , and for i = 1, . . . , `, let
breaks McEliece with GRS codes; we use the description
ti = (i + 1)r − k and hi = r − 1 + i.
from [8]. Let [I | A] be the systematic generator matrix
n,k
evaluation points α ∈ Fnq and column
Then the family of codes F`
is the set of all codes of a GRS code with
? n
C n,k (α, t, h, η), where α ∈ Fnq0 with distinct elements, and multipliers v ∈ (Fq ) . Using the automorphisms of a GRS
code, the attacker can assume α1 = 0 and α1 = 1. Row i of
where ηi ∈ Fq2i \ Fq2i−1 . Further, we let F̃`n,k ⊂ F`n,k
the matrix is the evaluation of the polynomial
0
0
be those codes which furthermore satisfy that α form a
Qk
fi = ci µ=1,µ6=i (x − αµ ),
multiplicative subgroup of Fq0 .
Note that if n = q0 − 1 then F̃`n,k = F`n,k , while if
where ci is a suitably chosen constant in Fq . It is well known
n - (q0 − 1) then F̃`n,k = ∅.
[22], [23] that the matrix A is a Cauchy matrix
Qkexactly when
It is technical but easy to show that for any n > 67 and any
the code is GRS. This means that for dj = ν=1 (αj − αν )
k satisfying the restrictions, then there is always a valid choice
for j = k + 1, . . . , n, we have the simple expression
for `. For triples (n, k, `) satisfying the restrictions, however,
c ·d
n,k
Ai j = αji−αj i .
(1)
it is not immediate that F` is well-defined, i.e. 0 < hi < k
and 0 < ti ≤ n − k for all i. Clearly h1 = r > 0. Then t1 =
 Due to this compact formula, after guessing the values
2(n+1)
.
2r − k > 0 since ` < 2n
− 2 i.e. k < 2 n+1
k −2 <
k
`+2
√
c1 , c2 ∈ Fq , the remaining secret values α3 , . . . , αn and
Then, since n+1 < (`+2)(k− n) ≤ (`+2)(k−(`+1)) then
v1 , . . . , vn can be computed by solving simple linear equak > n+1
`+2 + ` + 1 > r + ` = h` . Lastly, t` ≤ n − k simplifies
tions.
n−(`+1)
n
n
to r ≤ `+1
, but this is true since `+1
− n+1
`+2 = (`+1)(`+2)
Since Theorem 10 shows that the codes of F`n,k have
which is greater than 1 since n > (` + 2)2 .
large Schur square, then none of these codes can be GRS.
By Theorem 1 all codes in F`n,k are MDS. It is clear Therefore, a systematic generator matrix for these codes will
that for a fixed rate R = k/n, the lower bound for ` in have [I | A] where A will not be Cauchy. Since the SiS
Theorem 10 converges to R1 − 1 for n → ∞, so for large attack rested on the simple Cauchy structure, it will not work
enough n, it suffices to choose ` = b R1 c.
for these codes.
Remark 9: If one desires a code rate greater than 12 , one
Wieschebrink [7] generalised the SiS to apply for subcan use the dual of a code in F̃`n,k , for values of n for which codes of RS codes of small codimension. Assume that we
F̃`n,k is not empty. These will be twisted RS codes with ` have given a k × n generator matrix [I | A] of a subcode of
twists, by Theorem 2, and will resist the attacks since the an (n, k + δ) RS code. Then, the i-th row of the matrix A
primal codes do.
is obtained from a polynomial
Qk
A. Resistance to Schur Square Distinguishing
fi = ci (x) µ=1,µ6=i (x − αµ ),
Couvreur et. al [9] built a structural attack on McEliece where c (x) ∈ F [X] is a polynomial of degree deg c (x) ≤ δ.
i
q
i
with RS codes using the fact that the square code of a k- One now needs to guess the polynomials c (x) and c (x)
1
2
dimensional RS code D has abnormally low dimension when instead of only scalars, which will succeed after at most
k < n/2: dim(D2 ) = min{2k − 1, n}. By comparison, a ≈ q 2δ iterations. For large enough values of δ, this becomes
random linear code achieves dim(C 2 ) = min{ 12 k(k + 1), n} infeasible.
with high probability [21]. In this section we show that the
For C ∈ F`n,k , since dim C 2 = n, then Proposition 6
codes of F`n,k are impervious to this attack.
implies that any GRS code D O U T with C ⊂ D O U T must have
Theorem 10: Let n, k, ` be as in Definition 3, and let dim D
O U T ≥ k + (n − 2k + 1)/2. This very quickly makes
C ∈ F`n,k . Then dim C 2 = n and dim((C ⊥ )2 ) = n.
Wieschebrink’s attack infeasible for C.
Proof: Let r, t, h be as in Definition 3. We will use
Wieschebrink’s attack can also be carried out on the
n,k
Corollary 4, so let D = {deg(f · g) | f, g ∈ Pt,h,η
}. Since dual code, so that one seeks a GRS code D⊥ such that
INN
n,k
x0 , . . . , xr−1 ∈ Pt,h,η
then 0, . . . , 2r − 2 ∈ D. For each i, C ⊥ ⊂ D⊥
I N N , i.e. D I N N ⊂ C. If dim D I N N is close to dim C,
n,k
there is a polynomial of degree ti + k − 1 in Pt,h,η
, so also this is a bad sign: it may reveal structural information on C
(i + 1)r − 1, (i + 1)r, . . . , (i + 1)r + r − 2 ∈ D. Summing or may drastically reduce the cost of brute-force decoding
up we have all 0, 1, . . . , (` + 2)r − 2 ∈ D. By definition of the encrypted message. We are at this point unable to
r, we have (` + 2)r − 2 ≥ n − 1, so Corollary 4 implies the categorically refute this attack. Proposition 7 provides only
claim for C. The dual code has Schur square dimension n a small separation between D I N N and C, and it is not hard
since it is MDS and has dimension > n/2 [20, p.31].
to realise that this separation can never be greater than the

number of twists `, which we wish to keep fairly small for
V. C O N C L U S I O N
decoding purposes. As per Lemma 5, the obvious GRS code
We have presented a natural generalisation of twisted RS
contained in C is the one with the same evaluation points codes, pointed out a large subfamily of MDS codes, and
α and dimension min{h1 } = r. If C contains a larger GRS presented a decoder that is feasible for ` = 1, 2 twists. Those
code, it seems it would have to be a surprising, or spurious, codes whose evaluation points form a multiplicative group
code with other evaluation points and column multipliers.
are closed under duality with explicit duals. We also showed
If we choose n such that F̃`n,k is non-empty and C ∈ that the Schur square of a twisted RS code is usually large,
F̃`n,k , then C ⊥ is itself a twisted RS code by Section II-C. which shows that they are in a sense “far” from GRS codes,
Now the obvious GRS code D I N N such that C ⊥ ⊂ D⊥
I N N is
cf. Lemma 5. Furthermore, we identified a subfamily of
the one having the same evaluation points and dimension twisted RS codes that resist the relevant known structural
max{t̃i + n − k} = n − r, where t̃ = k − h is the twist attacks on the McEliece cryptosystem: Sidenlikov–Shestakov
vector of C ⊥ . Perhaps this strengthens the belief that it is not [6], Wieschebrink [8] and Schur square-distinguishing [9].
likely that C contains another, surprisingly large GRS code. For Wieschebrink’s attack on the dual code we could say
Summarising, assuming that C ∈ F`n,k contains no surpris- only that the attack does not apply in an obvious way. We
ingly large GRS code, then Wieschebrink’s attack on C or gave example parameters that achieve lower key sizes than
C ⊥ will have work factor roughly q 2δ if
the original McEliece cryptosystem for the same security
level.
k ∈ [r + δ, n+1 − δ] ≈ [ n − δ, n − δ] .
2

`+1

2

C. Example Code Parameters
We consider the following example parameters: Let
(n, k) = (255, 117), ` = 1, q0 = 28 and pick a code over
Fq , q = 216 , with these parameters as in Definition 3. The
number of such codes is upper-bounded by the number of
permutations on an n-dimensional set (here, n! > 22038 )
√
times the number of choices for η1 (= q − q ≈ 216 ). The
actual number of inequivalent codes is presumably much
smaller, but seems to suffice for avoiding exhaustive search
attack. Twisted RS codes also seem to have much smaller
automorphism groups than RS codes, though this is still to be
investigated further. Under the assumptions of the previous
subsection, the work factor of Wieschebrink’s attack is 2336 .
As for generic decoding attacks, we consider classical
information
[3], [24]2 with work factor WI =
 n−τ  3set decoding
n
2
k / k k log2 (q) , where τ is the number of errors
inserted by the sender. Since the example codes can correct
up to τunique = 69 errors uniquely and τlist = 83 using a
list decoder, we obtain the following work factors for unique
and list decoding, respectively:
WI,unique ≥ 2105 ,

WI,list ≥ 2126 .

In both cases, the key size is
Ksys = k(n − k) log2 (q)/8192 = 31.5 KB,
using a systematic generator matrix for the public key.3
The security level of the two variants above is ≥ 2100
respectively ≈ 2128 . We compare the key size to the originally
proposed parameters based on binary Goppa codes of similar
security level (both using systematic key):
Security level 2100 [10]: (n, k) = (2048, 1608), τ = 40,
K = 86.4 KB
Security level 2128 [11]: (n, k) = (3262, 2482), τ = 66,
K = 236.3 KB
In this example, using twisted RS codes reduce the key size
by a factor 2.7 and 7.4 at security levels ≈ 2100 respectively
≈ 2128 .
2 The improvements for non-binary information-set decoding considered
in [4] seem to be not more efficient since, unlike the original algorithm [3],
the cost of an iteration strongly depends on the field size, which is large
for our codes: q = 216 . However, this should be more carefully studied by
e.g. by estimating the number of iterations using a Markov chain simulation
as in [4].
3 Systematic generator matrices might decrease semantic security if they
are not carefully used, cf. [5, Section 5.1].

REFERENCES
[1] P. Beelen, S. Puchinger, and J. Rosenkilde né Nielsen, “Twisted ReedSolomon Codes,” in IEEE ISIT, 2017.
[2] S. Puchinger, J. Rosenkilde né Nielsen, and J. Sheekey, “Further
Generalisations of Twisted Gabidulin Codes,” in WCC, 2017.
[3] R. J. McEliece, “A Public-Key Cryptosystem Based On Algebraic
Coding Theory,” DSN Progress Report, vol. 42, no. 44, pp. 114–116,
1978.
[4] C. Peters, “Information-Set Decoding for Linear Codes over Fq.”
PQCrypto, vol. 2010, pp. 81–94, 2010.
[5] R. Overbeck and N. Sendrier, “Code-Based Cryptography,” in PostQuantum Cryptography. Springer, 2009, pp. 95–145.
[6] V. M. Sidelnikov and S. O. Shestakov, “On Insecurity of Cryptosystems
Based on Generalized Reed–Solomon Codes,” Discrete Math. Appl.,
vol. 2, no. 4, pp. 439–444, 1992.
[7] C. Wieschebrink, “An Attack on a Modified Niederreiter Encryption
Scheme,” in PKC, vol. 3958. Springer, 2006, pp. 14–26.
[8] ——, “Cryptanalysis of the Niederreiter Public Key Scheme Based on
GRS Subcodes,” in PQCrypto. Springer, 2010, pp. 61–72.
[9] A. Couvreur, P. Gaborit, V. Gauthier-Umaña, A. Otmani, and J.-P.
Tillich, “Distinguisher-based Attacks on Public-key Cryptosystems
Using Reed–Solomon Codes,” Des. Codes Cryptogr., vol. 73, no. 2,
pp. 641–666, 2014.
[10] A. Canteaut and N. Sendrier, “Cryptanalysis of the Original McEliece
Cryptosystem,” in Asiacrypt, vol. 1514. Springer, 1998, pp. 187–199.
[11] M. Barbier and P. S. L. M. Barreto, “Key Reduction of McEliece’s
Cryptosystem Using List Decoding,” in IEEE ISIT, July 2011.
[12] V. Guruswami and M. Sudan, “Improved Decoding of Reed–Solomon
Codes and Algebraic-Geometric Codes,” IEEE Trans. Inf. Theory,
vol. 45, no. 6, pp. 1757–1767, 1999.
[13] S. M. Johnson, “A New Upper Bound for Error-Correcting Codes,”
IEEE Trans. Inf. Theory, vol. 46, pp. 203–207, 1962.
[14] Y. Cassuto and J. Bruck, “A Combinatorial Bound on the List Size,”
California Institute of Technology, Tech. Rep., 2004.
[15] J. Justesen, “On the complexity of decoding Reed-Solomon codes
(Corresp.),” IEEE Trans. Inf. Theory, vol. 22, no. 2, pp. 237–238, Mar.
1976.
[16] M. Chowdhury, C.-P. Jeannerod, V. Neiger, E. Schost, and G. Villard,
“Faster Algorithms for Multivariate Interpolation With Multiplicities and
Simultaneous Polynomial Approximations,” IEEE Trans. Inf. Theory,
vol. 61, no. 5, pp. 2370–2387, May 2015.
[17] V. Neiger, J. Rosenkilde, and E. Schost, “Fast Computation of the
Roots of Polynomials Over the Ring of Power Series,” in ISSAC, 2017.
[18] H. Althaus and R. Leake, “Inverse of a Finite-Field Vandermonde
Matrix (Corresp.),” IEEE Trans. Inf. Theory, vol. 15, no. 1, pp. 173–
173, 1969.
[19] R. Cramer, I. B. Damgård, and J. B. Nielsen, Secure Multiparty
Computation and Secret Sharing. Cambridge University Press, 2015.
[20] H. Randriambololona, “On Products and Powers of Linear Codes Under
Componentwise Multiplication,” in AGCT, 2015.
[21] I. Cascudo, R. Cramer, D. Mirandola, and G. Zémor, “Squares of
Random Linear Codes,” IEEE Transactions on Information Theory,
vol. 61, no. 3, pp. 1159–1173, Mar. 2015.
[22] R. M. Roth and G. Seroussi, “On Generator Matrices of MDS Codes
(Corresp.),” IEEE Trans. Inf. Theory, vol. 31, no. 6, pp. 826–830, 1985.
[23] R. M. Roth and A. Lempel, “On MDS Codes via Cauchy Matrices,”
IEEE Trans. Inf. Theory, vol. 35, no. 6, pp. 1314–1319, 1989.
[24] E. Prange, “The Use of Information Sets in Decoding Cyclic Codes,”
IRE Trans. Inf. Theory, vol. 8, no. 5, pp. 5–9, 1962.

