with average-case/worst-case reductions

• [GPV08-STOC] C. Gentry, C. Peikert, and V. Vaikuntanathan. “Trapdoors for hard lattices and new cryptographic constructions.” (STOC 2008, http://eprint.iacr.org/2007/432 )
  • sEUF-CMA secure signature in ROM based on GapSVP with approximation factor O~(n^2) or O~(n^3)
• [LM08-TCC] 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-STACS] J. Alwen and C. Peikert. “Generating Shorter Bases for Hard Random Lattices.” (STACS 2009, TCS 2010, http://eprint.iacr.org/2008/521 )
  • Improving [[[Ajt99].
• [SSTX09-AC] D. Stehlé, R. Steinfeld, K. Tanaka, and K. Xagawa. “Efficient public key encryption based on ideal lattices.” (ASIACRYPT 2009, http://eprint.iacr.org/2009/285 )
  • Ideal-lattice versions of the Alwen * Peikert constructions.
• [Boy10-PKC] X. Boyen. “Of lettuces of lattices : a framework for short signatures and IBE with full security.” (PKC 2010)
  • Merged. See the full version of [[[ABB10-EC].
• [Ruc10-PQCrypto] M. Rückert. “Strongly Unforgeable Signatures and Hierarchical Identity-based Signatures from Lattices without Random Oracles.” (PQCrypto 2010, http://eprint.iacr.org/2010/070 )
  • An improvement of [[[CHKP10-?]
• [BF11-PKC] D. Boneh and D. Mandell Freeman. “Linearly Homomorphic Signatures over Binary Fields and New Tools for Lattice-Based Signatures.” (PKC 2011, http://eprint.iacr.org/2010/453 )
• [MP12-EC] Micciancio and Peikert.
  • As an applicaiton, they proposed a wCMA-secure signature scheme. A proof is based on the argument similar to Hohenberger and Waters, and CHKP10.

For signature schemes based on the Fiat-Shamir transformations, see [[Identification]].

• [GCZ12-WISM] Chunxiang Gu, Li Chen, and Yonghui Zheng. “ID-Based Signatures from Lattices in the Random Oracle Model.” (WISM 2012)
  • Combining [[[ABB10-C] + [[[GPV08-STOC]

Implementations

• [GOPS13-PQC] Tim Guneysu and Tobias Oder and Thomas Poppelmann and Peter Schwabe: Software Speed Records for Lattice-Based Signatures. PQCrypto 2013.

Extensions

Ring Signatures

• [KTX08-AC]
  • Ring Sig. from the KTX ad-hoc ID.
• [BK10-eP] Z. Brakerski and Y. Tauman Kalai. “A Framework for Efficient Signatures, Ring Signatures and Identity Based Encryption in the Standard Model.” (http://eprint.iacr.org/2010/086 )
  • Based on the CHKP sig.
• [CLRS10-Latincrypt] P.-L. Cayrel, R. Lindner, M. Rückert, and R. Silva. “A Lattice-Based Threshold Ring Signature Scheme.” (LATINCRYPT 2010)
  • Another twist of ...
• [Wang10-eP] J. Wang. “Ring Signature and Identity-Based Ring Signature from Lattice Basis Delegation.” (http://eprint.iacr.org/2010/378 )
  • ???
• [WS11-ICICS] Jin Wang and Bo Sun: Ring Signature Schemes from Lattice Basis Delegation. ICICS 2011
  • (1) Based on the GPV Sig in the ROM. (2) Based on the Boyen Sig in the StdM.
• [JS13-PQC] Schrek Julien and Bettaieb Slim: Improved Lattice-Based Threshold Ring Signature Scheme. PQCrypto 2013.
• [AMBBFG13-Africacrypt] Carlos Aguilar Melchor, Slim Bettaieb, Xavier Boyen, Laurent Fousse, and Philippe Gaborit: Adapting Lyubashevsky’s Signature Schemes to the Ring Signature Setting. Africacrypt 2013

Blind Signature

• [Ruc10-AC] M. Rückert: Lattice-based Blind Signatures. ASIACRYPT 2010, [[ePrint 2008/322:http://eprint.iacr.org/2008/322]]
  • See the version 2010/02/26.
• [GCZ12-WISM] Chunxiang Gu, Li Chen, and Yonghui Zheng. “ID-Based Signatures from Lattices in the Random Oracle Model.” (WISM 2012)
  • Combining [[[ABB10-C] + [[[GPV08-STOC]. They also proposed ID-based blind sig. in the ROM.

Group Signature and more

• [GKV10-AC] D. Gordon, J. Katz, and V. Vaikuntanathan. “A group singnature scheme from lattice assumptions.” (ASIACRYPT 2010, http://eprint.iacr.org/2011/060 )
  • A (static) group signature scheme from LWE and SIS in the ROM.
• [CNR12-SCN] Jan Camenisch, Gregory Neven, and Markus Ruckert “Fully Anonymous Attribute Tokens from Lattices.” (SCN 2012)
  • ... from LWE and SIS in the ROM.

GGH

Proposal

• [GGH97-C] O. Goldreich, S. Goldwasser, and S. Halevi. “Public-key cryptosystem from lattice reduction problems.” (CRYPTO 1997, ECCC 1997)
  • ...
• [PSW08-PKC] 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-IJAC] 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-PKC]

Attacks

• [NR06-EC] 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)

Proposal

• Pre-NSS (The rump session of CRYPTO 2000)
• [HPS01-EC] 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-CTRSA] J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman, and W. Whyte. “NTRUSign: Digital signatures using the NTRU lattice.” (CT-RSA 2003)
• [HWH08-IEEEIT] Y. Hu, B. Wan, and W. He. “NTRUSign with a new perturbation.” (IEEE Transactions on Information Theory, vol.54, 2008)
• [MA09-eP] Chunbo Ma and Jun Ao. “NTRU based group oriented signature.” http://eprint.iacr.org/2009/498
• [MA10-ETCS] Chunbo Ma and Jun Ao. “NTRU Based Group Oriented Signature and its Applications in RFID.” (ETCS 2010)

Attacks

• [Mir01-eP] I. Mironov “A note on cryptanalysis of the preliminary version of the NTRU Signature Scheme.” (ePrint 2001/005)
  • Attack on Pre-NSS
• [GJSS01-AC] 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-EC] C. Gentry and M. Szydlo. “Cryptanalysis of the revised NTRU signature scheme.” (EUROCRYPT 2002)
  • Attacks on R-NSS
• [Szy03-EC] M. Szydlo. “Hypercubic lattice reduction and analysis of GGH and NTRU signatures.” (EUROCRYPT 2003)
  • ...
• [MYK04-ACISP] S. J. Min, G. Yamamoto, and K. Kim. “Weak property of malleability in NTRUSign.” (ACISP 2004)
  • Proposal of strongly existential forgery against NTRUSign.
• [NR06-EC] P. Q. Nguyen and O. Regev. “Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures.” (EUROCRYPT 2006)
  • Attacks on NTRUSign without perturbations.
• [DN12-AC] Leo Ducas and Phong Q. Nguyen “Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures.” (ASIACRYPT 2012)
  • Attacks on NTRU with pertuabations (or deformations [[[HWH08-IEEEIT]).