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

PKEs and IBEs

Proposals

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)

Attacks

K. Kobara, H. Imai. “New Chosen-Plaintext Attacks on the One-Wayness of the Modified McEliece PKC Proposed at Asiacrypt 2000.” (PKC 2002)
K. Kobara, H. Imai. “On the one-wayness against chosen-plaintext attacks of the Loidreau's modified McEliece PKC.” (IEEE Transactions on Information Theory 49(12), 2003)

Others

K. Kobara, H. Imai. “Semantically Secure McEliece Public-Key Cryptosystems-Conversions for McEliece PKC.” (PKC 2001)
Yang Cui, Kazukuni Kobara, Hideki Imai: On Achieving Chosen Ciphertext Security with Decryption Errors. AAECC 2006: 173-182
R. Nojima, H. Imai, K. Kobara, K. Morozov. “Semantic security for the McEliece cryptosystem without random oracles.” (Des. Codes Cryptography 49(1-3), 2008)

Hash Functions

Proposals

[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.

Attacks

[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].

Others

Signatures

Proposals

[CFS01] N. Courtois, M. Finiasz, and N. Sendrier. “How to achieve a McEliece-based digital signature scheme.” (ASIACRYPT 2001)

Others

[ZLC07] D. Zheng, X. Li, K. Chen. “Code-based Ring Signature Scheme.” (International Journal of Network Security, Vol.5, No.2, Sept. 2007.)
[Ove08] R. Overbeck. “A Step Towards QC Blind Signatures.” (ePrint 2009/102)

Identifications

Standard Identifications

[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].

Identity-based identifications

[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].

Ad hoc anonymous identifications

[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.

Others

OT

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