Cryptography Reference
In-Depth Information
A small extra factor f makes the space of polynomials too large to search. Second,
we use subcodes as suggested by Berger and Loidreau in [2]. The combination
of these defenses leads to slightly larger key sizes but requires the attacker to
see simultaneously through subcodes, secret support sets, and a huge set of
polynomials.
This paper also announces a web page of code-based crypto challenges and
presents some sample challenges. The challenges cover finite fields as large as
F
32
and start with training challenges that should be easy to break but still
can show which attacks are faster than others. We originally considered issuing
challenges with several different wildness percentages, ranging from 100% wild
codes (g
q1
) to 50% wild codes (fg
q1
with deg(f) (q1) deg(g)) and beyond,
but we decided to focus on percentages close to 100%, since those are adequate
to prevent polynomial enumeration. For each set of parameters, a public key and
a ciphertext are presented.
Acknowledgement.The authors are grateful to Peter Beelen for interesting
discussions and in particular for allowing us to use his suggestion of the extra
factor f as a way to hide the wildness of g
q1
.
2AnExtraShieldforWildGoppaCodes
Fix a prime power q; a positive integer m; a positive integer n q
m
; an integer
t < n=m; distinct elements a
1
;:::;a
n
inF
q
m
; and a polynomial g(x) inF
q
m
[x]
of degree t such that g(ai)
i
) 6= 0 for all i.
We denote the linear code consisting of all words c = (c
1
;:::;c
n
) inF
n
q
m
satisfying
n
X
c
i
xa
i
0
(mod g(x))
(2.1)
i=1
by
q
m
(a
1
;:::;a
n
;g); this is a special case of a generalized Reed{Solomon code
overF
q
m
having dimension nt.
TheGoppacode
q
(a
1
;:::;a
n
;g) withGoppapolynomial g(x) andsupport
a
1
;:::;a
n
is the restriction of
q
m
(a
1
;:::;a
n
;g) to the eldF
q
, i.e., the set
of elements (c
1
;:::;c
n
) inF
n
q
that satisfy (2.1); this code
q
(a
1
;:::;a
n
;g) has
dimensionat least n mt andminimumdistanceat least t + 1. These codes
were introduced in [11] and [12].
Goppa codes can be decoded by any decoder for generalized Reed{Solomon
codes. For example, Berlekamp's algorithm corrects bt=2c errors; see, e.g., [3].
Note that t+1 is a lower bound for the minimum distance. There are Goppa codes
whose minimum distance is much larger. Binary Goppa codes have minimum
distance at least 2t + 1 as shown in [11], and allow fast decoding of t errors.
The standard t-error decoding algorithm for binary Goppa codes, in the typical
case that g is monic and irreducible, is Patterson's algorithm from [17]. There
are polynomial-time list-decoding algorithms that decode more errors; for more
information and references see, e.g., [4], [1], and [5].
