* with average-case/worst-case reductions [#u0dda6d9]

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


** Applications [#u83ef400]

*** Ring [#n92f122a]
-[[[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 [#d96a2a9a]
-[[[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 and more [#r7c801fe]
-[[[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 [#l5d4b67a]

** Proposals [#uea3338a]

-[[[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 [#aefa5659]

-[[[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) [#saedd334]

** Proposals [#x1510651]

-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 [#z3bca067]

-[[[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]]]).
Front page   Diff Backup Reload   List of pages Search Recent changes   Help   RSS of recent changes