Lattice Cryptography

Lattice Cryptography

(permanently under construction!)

Navigation Bar

• Home

• Cryptography
  • CCA Encrypt
  • Functional Encryption
  • FHE
  • Group Sign
  • Hashing
  • Homomorphic Crypto
  • IBE
  • ZK and Id protocols
  • Key Exchange
  • Encryption
  • Sampling
  • Signatures
  • Foundation
  • Threshold Crypto

• Lattice Algorithms
  • Enumeration
  • Sieving
  • Voronoi
  • Basis Reduction
  • SIS/LWE

Zero Knowledge and Identification Protocols

Zero-Knowledge protocols allow to prove the validity of a statement (or knowledge of some secret) without revealing any other information. There are two broad classes of lattice-based (zero-knowledge) proof systems: protocols to prove the validity of statements related to lattices, and protocols that use hard lattice problems to achieve other security goals (e.g., proving the validity of statements that are not directly related to lattices.)

Zero-Knowledge protcols have many applications in cryptography, from secure multiparty computation, to constructing identification schemes. Indentification schemes are two-party interactive protocols between a prover and a verifier that allow the verifier to identify the prover as the legitimate owner of a public key. Identification schemes can be directly obtained from zero-knowledge proof systems for hard computational problems, and can be used to build digital signatures using the Fiat-Shamir heuristics.

Early work provides statistical zero-knowledge proofs for the Shortest Vector Problem and Closest Vector Problem for arbitrary lattices. All these results are unconditionals, i.e., they do not require any complexity assumption, but can be instantiated with cryptographic (hard-on-average) lattices to obtain cryptographic applications, like indentification schemes and digital signatures, based on the worst-case hardness of lattice problems.

1. On the Limits of Nonapproximability of Lattice Problems
   (Goldreich & Goldwasser - JCSS 2000)

2. Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More
   (Micciancio & Vadhan - Crypto 2003)

3. Concurrent Zero Knowledge without Complexity Assumptions
   (Micciancio, Ong, Sahai & Vadhan - TCC 2006)

4. Noninteractive Statistical Zero-Knowledge Proofs for Lattice Problems
   (Peikert & Vaikuntanathan - Crypto 2008)

Identification schemes

5. Lattice-Based Identification Schemes Secure Under Active Attacks
   (Lyubashevsky - PKC 2008)

6. Zero-Knowledge Protocols for NTRU: Application to Identification and Proof of Plaintext Knowledge
   (Xagawa & Tanaka - ProvSec 2009)

7. Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems
   (Kawachi, Tanaka & Xagawa - AsiaCrypt 2008)

8. Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures
   (Lyubashevsky - Asiacrypt 2009)

9. Improved Zero-Knowledge Identification with Lattices
   (Cayrel, Lindner, Ruckert & Silva - ProvSec 2010)

10. Adaptively Secure Identity-Based Identification from Lattices without Random Oracles
    (Ruckert - SCN 2010)

11. A lattice-based batch identification scheme
    (Silva, Cayrel & Lindner - ITW 2011)

12. LWE-based identification schemes
    (Silva, Campello & Dahab - ITW 2011

13. Tightly-Secure Signatures From Lossy Identification Schemes
    (Abdalla, Fouque, Lyubashevsky & Tibouchi - Eurocrypt 2012)

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

Proofs of plaintext knowledge

15. Proof of Plaintext Knowledge for the Ajtai-Dwork Cryptosystem
    (Goldwasser & Kharchenko - TCC 2005

16. Proof of Plaintext Knowledge for the Regev Cryptosystem (Xagawa, Kawachi & Tanaka - 2007)

17. Threshold Decryption and Zero-Knowledge Proofs for Lattice-Based Cryptosystems
    (Bendlin & Damgard - TCC 2010)

18. Zero-Knowledge Proofs with Low Amortized Communication from Lattice Assumptions
    (Damgard & Lopez-Alt - SCN 2012)

19. Improved Zero-knowledge Proofs of Knowledge for the ISIS Problem, and Applications
    (Ling, Nguyen, Stehle & Wang - PKC 2013)

20. Efficient Zero-Knowledge Proofs for Commitments from Learning with Errors over Rings
    (Benhamouda, Krenn, Lyubashevsky & Pietrzak - ESORICS 2015 / ePrint 2014)

21. Better Zero-Knowledge Proofs for Lattice Encryption and Their Application to Group Signatures
    (Benhamouda, Camenisch, Krenn, Lyubashevsky & Neven - AsiaCrypt 2014)

22. Efficient Commitments and Zero-Knowledge Protocols from Ring-SIS with Applications to Lattice-based Threshold Cryptosystems
    (Baum, Damgard, Oechsner & Peikert - ePrint 2016)

23. Simple Amortized Proofs of Shortness for Linear Relations over Polynomial Rings
    (Baum & Lyubashevsky - ePrint 2017)

24. Amortization with Fewer Equations for Proving Knowledge of Small Secrets
    (del Pino & Lyubashevsky - Crypto 2017)

25. One-Shot Verifiable Encryption from Lattices
    (Lyubashevsky & Neven - Eurocrypt 2017)

26. Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to Lattice-Based Zero-Knowledge Proofs
    (Lyubashevsky & Seiler - Eurocrypt 2018 / ePrint 2017)

27. Lattice-Based Group Signatures and Zero-Knowledge Proofs of Automorphism Stability
    (del Pino, Lyubashevsky & Seiler - CCS 2018)

28. Sub-Linear Lattice-Based Zero-Knowledge Arguments for Arithmetic Circuits
    (Baum, Bootle, Cerulli, del Pino, Groth & Lyubashevsky - Crypto 2018)

29. Lattice-Based Zero-Knowledge Arguments for Integer Relations
    (Libert, Ling, Nguyen & Wang - Crypto 2018)

30. Short Discrete Log Proofs for FHE and Ring-LWE Ciphertexts
    (del Pino, Lyubashevsky & Seiler - PKC 2019)

NIZK for NP

31. Multi-Theorem Preprocessing NIZKs from Lattices
    (Kim & Wu - Crypto 2018)

32. Noninteractive Zero Knowledge for NP from (Plain) Learning With Errors
    (Peikert & Shiehian - ePrint 2019)

Proof systems for other lattice problems

33. New (and Old) Proof Systems for Lattice Problems
    (Alamati, Peikert & Stephens-Davidowitz - PKC 2018)