Cryptography Reference
In-Depth Information
We propose to compute the polynomial products by means of the several size-
p
fast discrete Fourier transform (DFT). This requires that the ring we work over
has an element
ω
of order
p
and its characteristic is not
p
.Onewaytoachieve
this, is to lift our field
F
q
into a ring
R
of characteristic 0 that has been extended
with a primitive
p
-th root of unity. Now, we can perform the operation in
R
,
and project the results back.
The DFT itself works like the Walsh-Hadamard transform in [MB09], except
that the matrices describing the transformation and its inverse are
H
d
and
H
−
1
,
d
which are recursively defined as
⎛
⎝
⎞
⎠
⎛
⎝
⎞
⎠
11 1
···
1
11 1
···
1
1
ω
1
ω
2
ω
p
−
1
ω
−
1
ω
−
2
ω
−
(
p
−
1)
···
1
···
1
ω
2
ω
4
ω
2(
p
−
1)
=
1
p
ω
−
2
ω
−
4
ω
−
2(
p
−
1)
···
1
···
H
−
1
1
H
1
=
,
,
.
1
ω
p
−
1
ω
2(
p
−
1)
··· ω
(
p
−
1)(
p
−
1)
.
.
.
.
1
ω
−
(
p
−
1)
ω
−
2(
p
−
1)
··· ω
−
(
p
−
1)(
p
−
1)
.
.
.
.
.
.
.
.
.
H
−
1
k
=
H
−
1
⊗ H
−
1
k
−
1
H
k
=
H
1
⊗ H
k
−
1
,
,
where
⊗
is the Kronecker product.
Acknowledgements.
We thank Rafael Dahmen for his invaluable advice; Chris-
tiane Peters for her always patient comments, and the anonymous reviewers for
helping in the improvement of this paper.
References
[BBD08]
Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.): PQCrypto 2008.
LNCS, vol. 5299. Springer, Heidelberg (2008)
[BC07]
Baldi, M., Chiaraluce, F.: Cryptanalysis of a new instance of McEliece
cryptosystem based on QC-LDPC code. In: IEEE International Sympo-
sium on Information Theory - ISIT 2007, pp. 2591-2595. IEEE (2007)
[BCGO09]
Berger, T.P., Cayrel, P.-L., Gaborit, P., Otmani, A.: Reducing
Key Length of the McEliece Cryptosystem. In: Preneel, B. (ed.)
AFRICACRYPT 2009. LNCS, vol. 5580, pp. 77-97. Springer, Heidelberg
(2009)
[BCMN10]
Barreto, P.S.L.M., Cayrel, P.-L., Misoczki, R., Niebuhr, R.: Quasi-Dyadic
CFS Signatures. In: Lai, X., Yung, M., Lin, D. (eds.) Inscrypt 2010.
LNCS, vol. 6584, pp. 336-349. Springer, Heidelberg (2011)
[BLM10]
Barreto, P.S.L.M., Lindner, R., Misoczki, R.: Decoding square-free Goppa
codes over
F
p
. Cryptology ePrint Archive, Report 2010/372 (2010),
http://eprint.iacr.org/2010/372.pdf
[BLP10]
Bernstein, D.J., Lange, T., Peters, C.: Wild McEliece. In: Biryukov, A.,
Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 143-158.
Springer, Heidelberg (2011)
[BLP11]
Bernstein, D.J., Lange, T., Peters, C.: Smaller Decoding Exponents:
Ball-Collision Decoding. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS,
vol. 6841, pp. 743-760. Springer, Heidelberg (2011)
[CFS01]
Courtois, N., Finiasz, M., Sendrier, N.: How to Achieve a McEliece-Based
Digital Signature Scheme. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS,
vol. 2248, pp. 157-174. Springer, Heidelberg (2001)
