Digital signatures

Digital signatures can be obtained from any (lattice based) one-way function using general techniques, but the resulting constructions are very inefficient. So, finding direct constructions of digital signatures based on hard lattice problems is both a theoretically interesting and practically important problem. There are several known direct constructions of lattice based signatures, both in the standard model and in the random oracle model.

Standard model

The first direct construction of lattice based digital signatures in the standard model was given in (1). Technically, (1) constructs one-time signatures, i.e., signature schemes that can be securely used to sign only one message, and then extends them to sign arbitrarily many messages using a standard tree construction. The first direct construction of full fledged signatures (in the standard model, without using trees) is given in (2), with efficiency improvements (4), (5), (7), (8) leading to schemes where both the signature and the public key consists of a single vector. Recent works (9), (@AD18) gives schemes with tight security proof, where security loss is independent of the number of signed messages.

  1. Asymptotically efficient lattice-based digital signatures
    (Lyubashevsky & Micciancio - TCC 2008/J.Cryptology 2018)

  2. Bonsai trees, or how to delegate a lattice basis
    (Cash, Hofheinz, Kiltz & Peikert - Eurocrypt 2010/J. Cryptology 2013)

  3. Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles
    (Ruckert - PQC 2010) Variant of (2) giving strong unforgeability and id-based signatures.

  4. Lattice mixing and vanishing trapdoors: a framework for fully secure short signatures and more
    (Boyen - PKC 2010)

  5. Trapdoors for lattices: simpler, tighter, faster, smaller
    (Micciancio & Peikert - Eurocrypt 2012)

  6. Confined Guessing: New Signatures From Standard Assumptions
    (Bohl, Hofeinz, Jager, Koch, Seo, Striecks - Eurocrypt 2013)/J. Cryptology 2015)

  7. Improved short lattice signatures in the standard model
    (Ducas & Micciancio - Crypto 2014)

  8. Short Signatures with Short Public Keys from Homomorphic Trapdoor Functions
    (Alperin-Sheriff - PKC 2015)

  9. Towards Tightly Secure Lattice Short Signature and Id-Based Encryption
    (Boyen & Li - Asiacrypt 2016)

  10. Weak is Better: Tightly Secure Short Signatures from Weak PRFs
    (Alperin-Sheriff & Apon - IACR ePrint 2017)

Digital signatures can also be obtained from Identity Based Encryption using a generic transformation of Naor described in (25).

Random oracle model

There are two types of lattice signatures in the random oracle model: “Hash and Sign” and “Fiat-Shamir” signatures.

“Hash and Sign” signatures were first proposed in (11), which gives relatively efficient digital signatures based on general lattices in the random oracle model. The efficiency of this scheme is improved in (5). These schemes are implemented in (12), which also presents an efficient variant based on ideal lattices.

  1. Trapdoors for hard lattices and new cryptographic constructions
    (Gentry, Peikert & Vaikuntanathan - STOC 2008

  2. Improvement and efficient implementation of a lattice-based signature scheme
    (ElBansarkhani & Buchmann - SAC 2013)

Lattice based digital signatures in the random oracle model following the “Fiat-Shamir” approach were first proposed in (13), and improved in a sequence of works. Currently, the most efficient lattice based signature scheme (in the random oracle model) is the BLISS scheme of (17).

  1. Fiat-Shamir with aborts: applications to lattice and factoring-based signatures
    (Lyubashevsky - Asiacrypt 2009)

  2. Lattice signatures without trapdoors
    (Lyubashevsky - Eurocrypt 2012)

  3. Tightly-secure signatures from lossy identification schemes
    (Abdalla, Fouque, Lyubashevsky & Tibouchi - Eurocrypt 2012)

  4. [Lattice-Based Signatures: Optimization and Implementation on Reconfigurable Hardware]
    (Guneysu, Lyubashevsky & Poppelmann - IEEE T.Comp 2015/CHES 2012)

  5. Lattice signatures and bimodal Gaussians
    (Ducas, Durmus, Lepoint & Lyubashevsky - Crypto 2013)

  6. An improved compression technique for signatures based on learning with errors
    (Bai & Galbraith - CT-RSA 2014)

  7. Enhanced Lattice-Based Signatures on Reconfigurable Hardware
    (Popplemann, Ducas & Guneysu - CHES 2014)

  8. Digital Signatures Based on the Hardness of Ideal Lattice Problems in All Rings
    (Lyubashevsky - Asiacrypt 2016)

  9. Towards Tightly Secure Lattice Short Signature and Id-Based Encryption
    (Boyen & Li - Asiacrypt 2016)

NTRU Signatures

  1. Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures
    (Nguyen & Regev - EuroCrypt 2006/J. Cryptology 2009)

  2. Making NTRUEncrypt and NTRUSign as secure as standard worst-case problems over ideal lattices
    (Stehle & Steinfeld - Eurocrypt 2011)

Additional References

  1. One-time signatures and chameleon hash functions
    (Mohassel - SAC 2010)

  2. Formal security treatments for signatures from identity-based encryption
    (Cui, Fujisaki, Hanaoka, Imai & Zhang - ProvSec 2007)