Bibliography on Lattice-based Cryptosystems

Maintained by Keita Xagawa

Last updated: 2008/11/08

Surveys and Lectures

Daniel J. Bernstein and Tanja Lange. Bernstein. Post-quantum cryptography - Code-based public-key cryptography

R.J. McEliece. “A public-key cryptosystem based on algebraic coding theory.” (DSN Progress Report, 1978)
H. Niederreiter. “Error-correcting codes and cryptography.“ (Public-Key Cryptosystem and Computational Number Theory 2001)?
Y.X. Li, R.H. Deng, X.M. Wang. “ON the equivalence of McEliece's and Niederreiter's public-key cryptosystems.” (IEEE Transactions on Information Theory 40 1994)

[AFS03] D. Augot, M. Finiasz, N. Sendrier. “A fast provably secure cryptographic hash function.” (ePrint 2003/230): A proposal of hash functions based on the Syndrome Decoding Problem, which called FSB.
[AFS05] D. Augot, M. Finiasz, N. Sendrier. “A family of fast syndrome based cryptographic hash functions.” (Mycrypt 2005): A proposal of hash functions based on the Syndrome Decoding Problem, which called FSB.
[FGS07] M. Finiasz, P. Gaborit, N. Sendrier. “Improved fast syndrome based cryptographic hash functions..” (ECRYPTO Hash Workshop 2007): A proposal of efficient hash functions based on the quasi-cyclic version of Syndrome Decoding Problem, which called IFSB.

[CJ04] J.S. Coron, A. Joux. “Cryptanalysis of a provably secure cryptographic hash functions.” (ePrint 2004/013): A variant of Wagner's generalized birthday attack for proposed parameter sets [AFS03].
[Saa07] M.-J. O. Saarinen. “Linearization Attacks Against Syndrome Based Hashes.” (INDOCRYPTO 2007, ePrint 2007/295): Efficient attack against FSB for proposed parameter sets [AFS05].
[FL08] P.-A. Fouque, G. Leurent. “Cryptanalysis of a hash function based on quasi-cyclic codes.” (CT-RSA 2008): Efficient attack against IFSB for proposed parameter sets [FGS07].

[Ste96] J. Stern. “A new paradigm for public key identification.” (CRYPTO 1993, IEEE Transactions on Information Theory 42 (6) 1996): (In CRYPTO 1993 entitled with "A New Identification Scheme Based on Syndrome Decoding")
[Ve97] P. Véron. “Improved Identification Schemes Based on Error-Correcting Codes.” (Applicable Algebra in Engineering, Communication and Computing, vol.8, no.1, 1997): Use generating matrices instead of parity-check matrices in Stern's ID scheme [Ste96].
[GG07] P. Gaborit, M. Girault. “Lightweight code-based identification and signature.” (ISIT 2007): Use parity-check matrices of double cyclic codes in Stern's ID scheme [Ste96].

[CGG07] P.-L. Cayrel, P. Gaborit, M. Girault. “Identity-based identification and signature schemes using correcting codes. ” (WCC 2007): They obtained IBI and IBS by combining the CFS signature and Stern's ID scheme [Ste96].

[ACG08] C. Aguilar Melchor, P.-L. Cayrel, P. Gaborit “A New Efficient Threshold Ring Signature Scheme based on Coding Theory” (PQCrypto 2008): By doubling Stern's ID scheme [Ste96], they obtained a threshold ad hoc anonymous identification scheme. Applying the Fiat--Shamir transformation, they had a threshold ring signature in ROM.

K. Kobara, K. Morozov, R. Overbeck. “Oblivious Transfer via McEliece's PKC and Permuted Kernels.” (ePrint 2007/382)
R. Dowsley, J. van de Graaf, J. Müller-Quade, A.C.A. Nascimento. “Oblivious Transfer based on the McEliece Assumptions.“ (ePrint 2008/138)