Bibliography on Lattice-based Cryptosystems

Maintained by Keita Xagawa

Last updated: 2010/03/09

• Surveys
• PKEs and IBEs
• Hash functions
• Signatures
• Identifications
• Others

Surveys and Lectures

J.-Y. Cai. “Some recent progress on the complexity of lattice problems.” (ECCC TR99-006)

NTRU Cryptosystems. “Peer Review and Independent Scrutiny of the NTRUEncrypt Public Key Cryptosystem [pdf]

O. Regev. 0368.4282 Lattices in computer science (Fall 2004)

O. Regev. “Lattice-based cryptography” (CRYPTO 2006)

D. Micciancio. CSE206A: Lattices algorithms and applications (Spring 2007)

D. Micciancio and O. Regev. “Lattice-based cryptography.” (In Post-Quantum Crypoology)

D. Stehlé. Algorithmics and Lattices, some references

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

J. Buchmann, R. Lindner, M. Rückert, and M. Schneider. “Post-Quantum Cryptography: Lattice Signatures.” (CECC 2008)

See Lindner's web site.

C. Peikert. “Some Recent Progress in Lattice-Based Cryptography .” (TCC 2009)

Slides are available at Peikert's web site.

Lattice Crypto Day (LCD) (2010/05/29)

PKEs and IBEs

With average-case/worst-case reductions

Proposals

[AD97] M. Ajtai and C. Dwork. “A public-key cryptosystem with worst-case/average-case equivalence.” (STOC 1997, ECCC TR96-065)

1-bit PKE based on O(n^12)-uSVP (I think the approximation factor is O(n^11))

[GGH97Eli] O. Goldreich, S. Goldwasser, and S. Halevi. “Eliminating decryption errors in the Ajtai-Dwork cryptosystem.” (CRYPTO 1997, ECCC TR97-018)

Errorless version of the Ajtai-Dwork cryptosystem.

[Reg03,Reg04] O. Regev. “New lattice based cryptographic constructions.” (STOC 2003, J. ACM 2004)

1-bit PKE based on O(n^1.5)-uSVP

[Reg05,Reg09] O. Regev. “On lattices, learning with errors, random linear codes, and cryptography.” (STOC 2005, J. ACM 2009)

1-bit PKE based on SVP with approximation factor O~(n^1.5) (under quantum reduction).

[KTX07] A. Kawachi, K. Tanaka, and K. Xagawa. “Multi-bit public-key cryptosystem based on lattice problems.” (PKC 2007, SCIS 2006)

O(log n)-bit versions of the Ajtai-Dwork, Regev03, Regev05, and Ajtai05 cryptosystems.

[AD07] M. Ajtai and C. Dwork. “The first and fourth public-key cryptosystems with worst-case/average-case equivalence.” (ECCC TR07-097)

Improved version? A miss causes decryption errors...

[PW08] C. Peikert and B. Waters. “Lossy trapdoor functions and their applications.” (ePrint 2007/348, STOC 2008)

LWE-based O(n)-bit PKE secure in the sense of IND-CCA2 w/o RO

[PVW08] C. Peikert, V. Vaikuntanathan, and B. Waters. “A framework for efficient and composable oblivious transfer.” (ePrint 2007/348, CRYPTO 2008)

O(n)-bit version of the Regev05 cryptosystem

[GPV08] C. Gentry, C. Peikert, and V. Vaikuntanathan. “Trapdoors for hard lattices and new cryptographic constructions.” (STOC 2008)

Including LWE-based O(n)-bit IBE.

[Pei09] C. Peikert. “Public-key cryptosystems from the worst-case shortest vector problem.” (STOC 2009)

LWE-based IND-CCA2 PKE. If q > 2^{n/2}, LWE > GapSVP. This construction employs [AP09]

[GV09] Goldwasser and Vaikuntanathan. “.” ()

According to [Pei09], Goldwasser and Vaikuntanathan prepared a manuscript on a CCA2-secure PKE from lattices.

[AGV09] Akavia, Goldwasser, and Vaikuntanathan. “Simultaneous hardcore bits and cryptography against freezing attacks.” (TCC 2009)

On the security of Regev's encryption scheme against leakage of secret key. In addition, they proposed a simultaneous hardcore function for LWE.

[LM09] V. Lyubashevsky and D. Micciancio. “On bounded distance decoding, unique shortest vectors, and the minimum distance problem.” (CRYPTO 2009)

A reduction from uSVP to GapSVP using Peikert's idea. This shows that the AD PKE and the Regev 03 PKE is based on the worst-case hardness of GapSVP_{O(n^{2.5})} and GapSVP_{O(n^2)}. (Why O(n^{2.5})?)

[ACPS09] B. Applebaum, D. Cash, C. Peikert, and A. Sahai. “Fast cryptographic primitives and circular-secure encryption based on hard learning problems.” (CRYPTO 2009)

KDM-CPA secure PKEs for any affine function from GapSVP.

[BB09] D. Boneh and X. Boyen. “Efficient lattice (H)IBE in the standard model from the BB-1 framework.” (CRYPTO 2009 Rump Session)

Yet Another ID-based Encryption. But it seems to fail to simulate the extract oracle...

[SSTX09] D. Stehlé, R. Steinfeld, K. Tanaka, and K. Xagawa. “Efficient public key encryption based on ideal lattices.” (ASIACRYPT 2009, ePrint 2009/285)

IND-CPA secure PKE, DS w/ RO, IBI w/ RO, etc. from Ideal-SVP

[BGK09] Z. Brakerski, S. Goldwasser, and Y. Kalai. “Circular-secure encryption beyond Affine functions.” (ePrint 2009/485)

...

[DGKPV10] Y. Dodis, S. Goldwasser, Y. Kalai, C. Peikert and V. Vaikuntanathan. “Public-key Encryption Schemes with Auxiliary Inputs.” (TCC 2010)

It shows the dual encryption scheme in [GPV08] has the key-leakage security.

[BD10] B. Bendlin and I. Damgård. “Threshold decryption and zero-knowledge proofs for lattice-based cryptosystems.” (TCC 2010, ePrint 2009/391)

A threshold PKE with distributed key-generation protocol based on the Regev 05 PKE. A plaintext proof-of-knowledge protocol is more efficient than the one by Xagawa, Kawachi, and Tanaka.

[Boy10] X. Boeyn. “Of lettuces of lattices : a framework for short signatures and IBE with full security.” (PKC 2010)

[GHV10] C. Gentry, S. Halevi, V. Vaikuntanathan. “A simple BGN-type cryptosystem from LWE.&rduoq; (EUROCRYPT 2010)

...

[ABB10] S. Agrawal, D. Boneh, X. Boeyn. “Efficient lattice (H)IBE in the standard model.” (EUROCRYPT 2010)

...

[CHKP10] D. Cash, D. Hofheinz, E. Kiltz, C. Peikert. “Bonsai trees, or how to delegate a lattice basis.” (EUROCRYPT 2010, ePrint 2009/351, ePrint 2009/359)

Merged. DS from SIS and HIBE from LWE.

[LPR10] V. Lyubashevsky, C. Peikert, O. Regev. “On ideal lattices and learning with errors over rings.” (EUORCRYPT 2010)

...

[BHHI10] B. Barak, I. Haitner, D. Hofheinz, and Y. Ishai. “Bounded Key-Dependent Message Security.” (EUROCRYPT 2010, ePrint 2009/511)

An improved version of [ACPS09]

[CL10] Huiyan Chen and Zichen Li. “Lattice-based public key cryptosystem provably secure against adaptive chosen ciphertext attack.” (ePrint 2010/121)

I found a simple CCA2 attack against thier PKE...

[Che10] Huiyan Chen. “CCA-secure cryptosystem from lattice.” (ePrint 2010/127)

Again, I found a simple CCA2 attack against his/her PKE...

Attacks

[NS98] P. Q. Nguyen and J. Stern. “Cryptanalysis of the Ajtai-Dwork cryptosystem.” (CRYPTO 1998, ECCC TR98-010)

Up to n=32 in experimental manner.

[HGS99] C. Hall, I. Goldberg, and B. Schneier. “Reaction attacks against several public-key cryptosystems.” (ICICS 1999)

A CCA1 universal-break attack against the Ajtai-Dwork cryptosystem.

[PS09] T. Plantard and W. Susilo. “Broadcast attacks against lattice-based cryptosystems.” (ACNS 2009)

A heuristic attacks against several lattice-based PKEs.

Others

[GK05] S. Goldwasser and D. Kharchenko. “Proof of plaintext knowledge for the Ajtai-Dwork cryptosystem.” (TCC 2005)

A variant of the AD PKE with proof of plaintext knowledge.

[XKT07] K. Xagawa, A. Kawachi, K. Tanaka. “Proof of plaintext knowledge for the Ajtai-Dwork cryptosystem.” (TR C-236, 2007)

Two variants of the Regev 03 and the Regev 05 PKEs with proofs of plaintext knowledge.

GGH and its variants

Proposals

[GGH97Pub] O. Goldreich, S. Goldwasser, and S. Halevi. “Public-key cryptosystem from lattice reduction problems.” (CRYPTO 1997, ECCC 1997)

...

[Mic01] D. Micciancio. “Improving lattice based cryptosystems using the Hermite normal form.” (CaLC 2001)

Reducing the size of pk in [GGH97Pub] by using HNF.

[SCM01] P. Solé, C. Charnes, and B. Martin. “A lattice-based McEliece scheme for encryption and signature.” (Electronic Notes in Discrete Mathematics, vol. 6, 2001)

Rediscovery of [GGH97Pub].

[PJH03] S.-H. Paeng, B. E. Jung, and K.-C. Ha. “A lattice based public key cryptosystem using polynomial representations.” (PKC 2003)

Reducing the size of keys in [GGH97Pub] using circulant matrices.

[PRS09] T. Plantard, M. Rose, W. Susilo. “Improvement of lattice-based cryptography using CRT.” (QuantumComm 2009)

Improved versions of GGH and [Mic01].

Attacks

[Ngu97] P. Q. Nguyen. “Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from CRYPTO '97.” (CRYPTO 1999)

Attacks succeed up to n=350 for challenges in [GGH97Pub]

[HKY07] D. Han, M.-H. Kim, and Y. Yeom. “Cryptanalysis of the Paeng-Jung-Ha cryptosystem from PKC 2003.” (PKC 2007)

Attacks succeed up to n=1000 for [PJH03].

[LH08] M.S. Lee and S.G. Hahn. “Analysis of the GGH cryptosystem.” (SCC 2008)

Attack with partially known plaintext. They solved the 400-dimensional challenge in [GGH97Pub] with help of Nguyen's results [Ngu97].

NTRU and its variants

Proposals

J. Hoffstein? Proposal of NTRU (The rump session in CRYPTO 1996)

[HPS98] J. Hoffstein, J. Pipher, J. H. Silverman. “NTRU: A ring-based public key cryptosystem.” (ANTS 1998)

In Z[x]/(q,X^N-1).

[BS02] W. D. Banks and I. Shparlinski. “A variant of NTRU with non-invertible polynomials.” (INDOCRYPT 2002)

A generalization of NTRU.

[GOS02] P. Gaborit, J. Ohler, and P. Solé. “CTRU, a polynomial analogue of NTRU.” (rapport de recherche INRIA RR-4621, Nov., 2002)

A variant in (F_2[T])[X]/(Q[X],X^N-1). See RR-4621.

[CG05] M. Coglianese and B.-M. Goi. “MaTRU: A new NTRU-based cryptosystem.” (INDOCRYPT 2005)

A variant in M_{k,k}(R)[X]/(q,X^n-1), where R=Z[X]/(X^n-1).

[Kou06] R. Kouzmenko “Generalizations of the NTRU cryptosystem.” (Diploma Project, Winter semester 2005-2006)

A variant in ((Z[i])[X])/(q,X^N-1). It is called NTRU using Gaussian integers. See ALGO+LMA - Output - MSc Theses. He/She also cryptanalyzed CTRU [GOS02]

[YZ06] J. Yao, G. Zeng “Enhanced NTRU cryptosystem eliminating decryption failures.” (Journal of Systems Engineering and Electronics, vol. 17, No. 4, 2006)

The main motivation is eliminating wrap faileurs. In order to resist the CCA atatcks, the authors set pk=(h=f^{-1}*g_1, l=p*f^{-1}*g_2). Encryption is obtained as e=m*h+l*r. They insisted that the scheme without padding can resist the CCA attacks.

[Tru07] K. R. Truman. “Analysis and extension of non-commutative NTRU.” (Ph.D Thesis, University of Maryland)

...

[Vat09] N. Vats. “NNRU, a noncommutative analogue of NTRU.” ([arXiv:0902.1891v1])

A variant in M_{k,k}(Z)[X]/(q,X^n-I_{k,k}).

[MZM09] E. Malekian, A. Zakerolhosseini, A. Mashatan. “QTRU: A lattice attack resistant version of NTRU.” (ePrint 2009/386)

A variant in R+Ri+Rj+Rk, where R = Z_q[X]/(X^N-1).

[MZ09] E. Malekian, A. Zakerolhosseini. “NTRU-like public key cryptosystems beyond dedekind domain up to alternative algebra.” (ePrint 2009/446)

A variant employing octonions.

Parameter Settings

[HHHW09] P. Hirschhorn, J. Hoffstein, N. Howgrave-Graham and W. Whyte. “Choosing NTRU Parameters in Light of Combined Lattice.” (ACNS 2009)

A proposal of parameter setting algorithm considering the meet-in-the-middle attack.

Attacks

[CS07] D. Coppersmith and A. Shamir. “Lattice attacks on NTRU” (EUROCRYPT 1997)

[Sil99] J. H. Silverman. “A meet-in-the-middle attack on an NTRU private key.” (NTRU Tech. Rep. #004-ver.2, 1999.)

Odlyzko's meet-in-the-middle attack and its improvement.

[JJ00] É Jaulmes and A. Joux. “A chosen-ciphertext attack against NTRU.” (CRYPTO 2000)

[Gen01] C. Gentry. “Key recovery and message attacks on NTRU-Composite.” (EUROCRYPT 2001)

A 3-minute attack on NTRU-256 using a folding lattice technique.

[NP02] P. Q. Nguyen and D. Pointcheval. “Analysis and improvements of NTRU encryption paddings.” (CRYPTO 2002)

[Arn02] F. Arnault. “Cryptanalyse de CTRU.” (Talk, Dec., 2002)

An attack on CTRU [GOS02]. See Programme du groupe de travail "Arithmétique-Cryptographie-Codage 2002-2003"

[HNP+03] N. Howgrave-Graham, P. Q. Nguyen, D. Pointcheval, J. Proos, J. H. Silverman, A. Singer, and W. Whyte. “The impact of decryption failures on the security of NTRU encryption.” (CRYPTO 2003)

[HHHK03] D. Han, J. Hon, J. W. Han, and D. Kwon. “Key recovery attacks on NTRU without ciphertext validation routine.” (ACISP 2003)

[SSV04] J. H. Silverman, N. P. Smart, and F. Vercauteren. “An algebraic approach to NTRU (q=2n) via Witt vectors and overdetermined systems of nonlinear equations.” (SCN 2004)

[SSS04] T. E. Seidel, D. Socek, and M. Sramka. “Parallel symmetric attack on NTRU using non-deterministic lattice reduction.” (Designs, Codes and Cryptography, 32 (1-3), 2004)

[GHN06] N. Gama, N. Howgrave-Graham, and P. Q. Nguyen. “Symplectic lattice reduction and NTRU.” (EUROCRYPT 2006)

Speeding up lattice reduction algorithms (?)

[MR06] T. Meskanen and A. Renvall. “A wrap error attack against NTRUEncrypt.” (Discrete Applied Mathematics 154(2), 2006)

[GN07] N. Gama and P. Q. Nguyen. “New Chosen-Ciphertext Attacks on NTRU.” (PKC 2007)

[SW07] J. H. Silverman and W. Whyte. “Timing attacks on NTRUEncrypt via variation in the number of hash calls.“ (CT-RSA 2007)

[How07] N. Howgrave-Graham. “A hybrid lattice-reduction and meet-in-the-middle attack against NTRU.” (CRYPTO 2007)

[MY08] P. Mol and M. Yung. “Recovering NTRU secret key from inversion oracles.“ (PKC 2008)

[Vat08] N. Vats. “Algebraic cryptanalysis of CTRU cryptosystem.” (COCOON 2008)

Third attack against CTRU [GOS02].

Others

[NSW03] M. Naslund, I. Shparlinski, and W. Whyte. “On the bit security of NTRUEncrypt.” (PKC 2003)

[LYP05] X. Lv, B. Yang, and C. Pei. “Efficient Traitor Tracing Scheme Based On NTRU.” (PDCAT 2005)

[YHZ05] W. Yu, D. He, and S. Zhu. “Study on NTRU decryption failures.” (ICITA 2005)

[Sta05] M. Stam. “A key encapsulation mechanism for NTRU.” (IMA Int. Conf. 2005)

[LKSP07] M.-K. Lee, J. W. Kim, J. E. Song, and K. Park. “Sliding window method for NTRU.” (ACNS 2007)

[BDL08] J. Buchmann, M. Döring, and R. Lindner. “Efficiency improvement for NTRU.” (Sicherheit 2008)

I found the paper. See Lindner's website

[WZ08] S. Wei and Z. Zhuo. “Research on PKI model based on NTRU.” (ISECS 2008)

Fully Homomorphich Ones

[Gen09] C. Gentry. “Fully homomorphic encryption using ideal lattices.” (STOC 2009)

Based on ideal lattices. KDM-CPA security serves fully homomorphic encrptyion by simulating the decryption circuit. The descriptions and several proofs appeared in his thesis.

[SV10] N. P. Smart and F. Vercauteren. “Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes.” (PKC 2010, ePrint 2009/571)

The ciphertext is an element in Z_p by bsing the special ideal lattice.

[vDGHV10] M. van Dijk, C. Gentry, S. Halevi, and Vinod Vaikuntanathan. “Fully Homomorphic Encryption over the Integers.” (EUROCRYPT 2010, ePrint 2009/616)

This variant is not based on the lattice but has a similar strucutre to the Regev03 encryption scheme [Reg04].

Others

Proposals

[CC99] J.-Y. Cai and T. Cusick. “A lattice-based public-key cryptosystem.” (SAC 1998, Inf. Comput. 1999)

Knapsack-based cryptosystem using the idea from the Ajtai-Dwork cryptosystem.

[FS99] R. Fischlin and J.-P. Seifert. “Tensor-based trapdoors for CVP and their application to public key cryptography.” (WCC 1999)

...

Attacks

[PD08] Y. Pan and Y. Deng. “Cryptanalysis of the Cai-Cusick lattice-based public-key cryptosystem.” (ePrint 2008/204)

Attack against the Cai-Cusick cryptosystem [CC99].

One-Way/Collision-Resistant Hash Functions

Based on General Lattices

[Ajt96] M. Ajtai. “Generating hard instances of lattice problems.” (STOC 1996, ECCC TR96-007)

One-way functions based on the worst-case hardness of SVP_{poly(n)}, poly(n)-uSVP, and SIVP_{poly(n)}.

[GGH96] O. Goldreich, S. Goldwasser, and S. Halevi. “Collision-free hashing from lattice problems.” (ECCC TR96-042)

The Ajtai function is collision resistant under the same assumption.

[CN97] J.-Y. Cai and A. Nerurkar. “An improved worst-case to average-case connection for lattice problems.” (FOCS 1997)

Improving the approximation factor up to O~(n^{4+\epsilon})

[Cai03] J.-Y. Cai. “A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor.” (CCC 1999, Discrete Applied Mathematics 2003)

Improving the approximation factor of the assumption.

[Mic02] D. Micciancio. “Improved cryptographic hash functions with worst-case/average-case connection.” (STOC 2002, CCC 2002)

[Mic04] D. Micciancio. “Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor.” (SIAM J. on Comp. 2004)

Improving the approximation factor up to O~(n^3).

[MR07] D. Micciancio and O. Regev. “Worst-case to average-case reduction based on Gaussian measures.” (FOCS 2004, SIAM J. on Comp. 2007)

Based on GapSVP, SIVP, CRP, or GDD with approximation factor O~(n).

[Pei07] C. Peikert. “Limits on the hardness of lattice problems in l_{p} norms.” (CCC 2007, ECCC 2007)

Based on GapSVP, SIVP, CRP, or GDD with approximation factor O~(n) in l_p norm.

C. Gentry, C. Peikert, and V. Vaikuntanathan. “Trapdoors for hard lattices and new cryptographic constructions.” (STOC 2008, ePrint 2007/432)

Slightly tighter reduction. The parameter q can be set to O~(n).

Based on Cyclic/Ideal Lattices

[Mic07] D. Micciancio. “Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions.” (FOCS 2002, Computational Complexity, Vol. 16, No. 4, 2007)

One-way functions based on Cyclic-SVP with approximation factor O~(n^3). In the newer version, with approximation factor O~(n)

[PR06] C. Peikert and A. Rosen. “Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices” (TCC 2006)

The variants of M02 is collision resistant under almost same assumption.

[LM06] V. Lyubashevsky and D. Micciancio. “Generalized compact knapsacks are collision resistant.” (ICALP 2006, ECCC 2005)

Collision-resistant functions based on Ideal-SVP with approximation factor O~(n)

[LMPR08] V. Lyubashevsky, D. Micciancio, C. Peikert, and A. Rosen. “SWIFFT: a modest proposal for FFT hashing.” (NIST 2nd Hash Workshop, FSE 2008)

[ADL+08] Y. Arbitman, G. Dogon, V. Lyubashevsky, D. Micciancio, C. Peikert, and A. Rosen “SWIFFTX: A Proposal for the SHA-3 Standard.”

[BL09] J. Buchmann and R. Lindner. “Secure Parameters for SWIFFT.” (INDOCRYPT 2009, ePrint 2008/493)

Signatures

with average-case/worst-case reductions

C. Gentry, C. Peikert, and V. Vaikuntanathan. “Trapdoors for hard lattices and new cryptographic constructions.” (STOC 2008, ePrint 2007/432)

sEUF-CMA secure signature in ROM based on GapSVP with approximation factor O~(n^2) or O~(n^3)

[LM08] V. Lyubashevsky and D. Micciancio. “Asymptotically efficient lattice-based digital signatures.” (TCC 2008)

One-time signature based on Ideal-SVP with approximation factor O~(n^2).

[AP09] J. Alwen and C. Peikert. “Generating Shorter Bases for Hard Random Lattices.” (STACS 2009, ePrint 2009/521)

Improving [Ajt99].

D. Stehlé, R. Steinfeld, K. Tanaka, and K. Xagawa. “Efficient public key encryption based on ideal lattices.” (ASIACRYPT 2009, ePrint 2009/285)

Ideal-lattice versions of the Alwen--Peikert constructions.

[Ruc10a] M. Rückert. “Strongly Unforgeable Signatures and Hierarchical Identity-based Signatures from Lattices without Random Oracles.” (PQCrypto 2010, ePrint 2010/070)

An improvement of [CHKP10].

[Ruc10b] M. Rückert. “Lattice-based Blind Signatures” (ePrint 2008/322)

See the version 2010/02/26.

GGH

Proposals

O. Goldreich, S. Goldwasser, and S. Halevi. “Public-key cryptosystem from lattice reduction problems.” (CRYPTO 1997, ECCC 1997)

...

[PSW08] T. Plantard, W. Susilo, and K. T. Win. “A digital signature scheme based on CVP_{\infty}.” (PKC 2008)

A variant of the GGH signature scheme based on CVP_{\infty}. It seems resist the Nguyen--Regev attack.

[PSWH08] T. Plantard, W. Susilo, K. T. Win, Q. Huang. “Efficient lattice-based signature scheme.” (International Journal of Applied Cryptography 2008)

The journal version of [PSW08]

Attacks

[NR06] P. Q. Nguyen and O. Regev. “Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures.” (EUROCRYPT 2006)

Attacks on GGH and NTRU with about 90000 signatures

NTRU (NSS, R-NSS, NTRUSign)

Proposals

Pre-NSS (The rump session of CRYPTO 2000)

[HPS01] J. Hoffstein, J. Pipher, and J. H. Silverman. “NSS: An NTRU lattice-based signature scheme.” (EUROCRYPT 2001)

R-NSS (The rump session of EUROCRYPT 2001, Draft 2.0 of EESS#1)

[HHPSW03] J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman, and W. Whyte. “NTRUSign: Digital signatures using the NTRU lattice.” (CT-RSA 2003)

[HWH08] Y. Hu, B. Wan, and W. He. “NTRUSign with a new perturbation.” (IEEE Transactions on Information Theory, vol.54, 2008)

[MA09] C. Ma, J. Ao. “NTRU based group oriented signature.” (ePrint 2009/498)

Attacks

[Mir01] I. Mironov “A note on cryptanalysis of the preliminary version of the NTRU Signature Scheme.” (ePrint 2001/005)

Attack on Pre-NSS

[GJSS01] C. Gentry, J. Jonsson, J. Stern, and M. Szydlo “Cryptanalysis of the NTRU Signature Scheme (NSS) from EUROCRYPT 2001” (The rump session of EUROCRYPT 2001, ASIACRYPT 2001)

Attacks on NSS

[GS02] C. Gentry and M. Szydlo. “Cryptanalysis of the revised NTRU signature scheme.” (EUROCRYPT 2002)

Attacks on R-NSS

[Szy03] M. Szydlo. “Hypercubic lattice reduction and analysis of GGH and NTRU signatures.” (EUROCRYPT 2003)

[MYK04] S. J. Min, G. Yamamoto, and K. Kim. “Weak property of malleability in NTRUSign.” (ACISP 2004)

Proposal of strongly existential forgery against NTRUSign.

[NR06] P. Q. Nguyen and O. Regev. “Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures.” (EUROCRYPT 2006)

Attacks on NTRUSign without perturbations.

Identifications

With average-case/worst-case reductions

[MV03] D. Micciancio and S. Vadhan. “Statistical zero-knowledge proofs with efficient provers: lattice problems and more.” (CRYPTO 2003)

Combining with MR07, we have ID schemes based on GapSVP with approximation factor O~(n^{1.5})

[Lyu08a] V. Lyubashevsky. “Lattice-based identification schemes secure under active attacks.” (PKC 2008)

Concurrently-secure ID schemes based on GapSVP or Ideal-SVP with approximation factor O~(n^2)

[Lyu08b] V. Lyubashevsky. “” (Ph.D Thesis)

Concurrently-secure ID schemes based on Ideal-SVP with approximation factor O~(n^3)

[KTX08] A. Kawachi, K. Tanaka, and K. Xagawa. “Concurrently secure identification schemes based on the worst-case hardness of lattice problems.” (ASIACRYPT 2008, SCIS 2008)

ID schemes based on GapSVP or Ideal-SVP with approximation factor O~(n). Using Stern's scheme (CRYPTO 1993).

[Lyu09] V. Lyubashevsky. “Fiat-Shamir With Aborts: Applications to Lattice and Factoring-Based Signatures.” (ASIACRYPT 2009)

Concurrently-secure ID schemes based on Ideal-SVP with approximation factor O~(n^2)

Without average-case/worst-case reductions

[HT08] S. Hayashi and M. Tada. “A digital signature scheme based on NP-complete lattice problems.” (IEICE Transactions 91-A, 2008)

ID scheme based on Non-negative Binary Exact Length Vector Problem (NBELVP) in the l_{1} norm.

[XT09] K. Xagawa and K. Tanaka. “Zero-Knowledge Protocols for NTRU: Application to Identification and Proof of Plaintext Knowledge.” (ProvSec 2009)

SZKPOK for NTRU.

Others

OT

C. Peikert, V. Vaikuntanathan, and B. Waters. “A framework for efficient and composable oblivious transfer” (CRYPTO 2008)

Based on LWE.

PIR

NISZK

[PV08] C. Peikert and V. Vaikuntanathan. “Noninteractive statistical zero-knowledge proofs for lattice problems.” (CRYPTO 2008)

NISZK for SIVP, GapCRP, GapGSMP, and coGapSVP with approximation factors O~(\sqrt{n}).

PAKE

[KV09] J. Katz and V. Vaikuntanathan. “Password-based authenticated key exchange based on lattices.” (ASIACRYPT 2009)

On the assumptions

[BLRS08] J. Buchmann, R. Lindner, M. Rückert, and M. Schneider. “Explicit hard instances of the shortest vector problem.” (PQCrypto 2008)

See www.latticechallenge.org.

[GKPV10] S. Goldwasser, Y. Kalai, C. Peikert and V. Vaikuntanathan. “Robustness of the Learning with Errors Assumption.” (ICS 2010)