Zero-knowledge proof systems for lattice-based cryptography
Lattice-based cryptography is one of the most active research topics in cryptography in recent years. In many cryptographic constructions based on lattice assumptions, the building block is a proof of knowledge of a solution to an instance of the Inhomogeneous Small Integer Solution (ISIS) problem....
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2014
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/55283 |
| _version_ | 1811694490330595328 |
|---|---|
| author | Nguyen, Ta Toan Khoa |
| author2 | Wang Huaxiong |
| author_facet | Wang Huaxiong Nguyen, Ta Toan Khoa |
| author_sort | Nguyen, Ta Toan Khoa |
| collection | NTU |
| description | Lattice-based cryptography is one of the most active research topics in cryptography in recent years. In many cryptographic constructions based on lattice assumptions, the building block is a proof of knowledge of a solution to an instance of the Inhomogeneous Small Integer Solution (ISIS) problem. However, all known such proof
systems have relatively weak security guarantees: Breaking each of these protocols is potentially easier than solving the underlying instance of the ISIS problem. As a consequence, cryptographic constructions relying on these proof systems typically inherit the sub-optimal security guarantees. Therefore, proof systems with stronger security guarantees are highly desirable. Such protocols are not only interesting from a theoretical point of view, but they also lead to lattice-based cryptographic constructions relying on weaker hardness assumptions than the contemporary schemes.
In this thesis, we construct a series of zero-knowledge proofs of knowledge with strong security guarantees and reasonable communication costs, that can find various applications in lattice-based cryptography. Our constructions rely on a simple, yet versatile and effective technique, called Decomposition-Extension. When adapting this technique to the Stern-KTX proof system (Stern ‘96 - Kawachi, Tanaka, Xagawa ‘08), we obtain a zero-knowledge proof of knowledge for the ISIS problem (in the infinity norm) with a very strong security guarantee: Breaking the protocol is as least as hard as solving the underlying ISIS instance. We then develop our technique to design the following lattice-based cryptographic constructions:
- Efficient zero-knowledge proofs of plaintext knowledge with strong security guarantees
for 4 encryption schemes based on the Learning with Errors problem: Regev’s scheme (Regev ‘05); the Dual-Regev scheme (Gentry, Peikert, Vaikuntanathan ‘08); the PVW scheme (Peikert, Vaikuntanathan, Waters ‘08); and the GHV scheme (Gentry, Halevi, Vaikuntanathan ‘10). Our results immediately yield 4 lattice-based interactive encryption protocols that are secure under chosen ciphertext attacks. Previously, only zero-knowledge proofs of plaintext knowledge for Regev’s scheme were known, and they are relatively inefficient with rather weak security guarantees.
- A lattice-based identity-based identification scheme relying on a weaker hardness assumption than in the previous works. Furthermore, we introduce an identity-based ring identification scheme based on the worst-case hardness of lattice problems. To the best of our knowledge, this is the first such scheme.
- An improved lattice-based group signature scheme relying on relatively weak hardness assumptions, in which the signature size is logarithmic in the number of group users. Earlier lattice-based group signature schemes, which were published before 2013, rely on relatively weak hardness assumptions but have the undesirable property that the size of the signature is linear in the number of group users. A recent scheme (Laguillaumie, Langlois, Libert, Stehlé ‘13) achieves logarithmic signature size but it has to rely on relatively strong hardness assumptions. Our construction, thus, simultaneously achieves the good features of the existing schemes. |
| first_indexed | 2024-10-01T07:08:24Z |
| format | Thesis |
| id | ntu-10356/55283 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T07:08:24Z |
| publishDate | 2014 |
| record_format | dspace |
| spelling | ntu-10356/552832023-02-28T23:52:47Z Zero-knowledge proof systems for lattice-based cryptography Nguyen, Ta Toan Khoa Wang Huaxiong Xing Chaoping School of Physical and Mathematical Sciences DRNTU::Science::Mathematics::Discrete mathematics::Cryptography Lattice-based cryptography is one of the most active research topics in cryptography in recent years. In many cryptographic constructions based on lattice assumptions, the building block is a proof of knowledge of a solution to an instance of the Inhomogeneous Small Integer Solution (ISIS) problem. However, all known such proof systems have relatively weak security guarantees: Breaking each of these protocols is potentially easier than solving the underlying instance of the ISIS problem. As a consequence, cryptographic constructions relying on these proof systems typically inherit the sub-optimal security guarantees. Therefore, proof systems with stronger security guarantees are highly desirable. Such protocols are not only interesting from a theoretical point of view, but they also lead to lattice-based cryptographic constructions relying on weaker hardness assumptions than the contemporary schemes. In this thesis, we construct a series of zero-knowledge proofs of knowledge with strong security guarantees and reasonable communication costs, that can find various applications in lattice-based cryptography. Our constructions rely on a simple, yet versatile and effective technique, called Decomposition-Extension. When adapting this technique to the Stern-KTX proof system (Stern ‘96 - Kawachi, Tanaka, Xagawa ‘08), we obtain a zero-knowledge proof of knowledge for the ISIS problem (in the infinity norm) with a very strong security guarantee: Breaking the protocol is as least as hard as solving the underlying ISIS instance. We then develop our technique to design the following lattice-based cryptographic constructions: - Efficient zero-knowledge proofs of plaintext knowledge with strong security guarantees for 4 encryption schemes based on the Learning with Errors problem: Regev’s scheme (Regev ‘05); the Dual-Regev scheme (Gentry, Peikert, Vaikuntanathan ‘08); the PVW scheme (Peikert, Vaikuntanathan, Waters ‘08); and the GHV scheme (Gentry, Halevi, Vaikuntanathan ‘10). Our results immediately yield 4 lattice-based interactive encryption protocols that are secure under chosen ciphertext attacks. Previously, only zero-knowledge proofs of plaintext knowledge for Regev’s scheme were known, and they are relatively inefficient with rather weak security guarantees. - A lattice-based identity-based identification scheme relying on a weaker hardness assumption than in the previous works. Furthermore, we introduce an identity-based ring identification scheme based on the worst-case hardness of lattice problems. To the best of our knowledge, this is the first such scheme. - An improved lattice-based group signature scheme relying on relatively weak hardness assumptions, in which the signature size is logarithmic in the number of group users. Earlier lattice-based group signature schemes, which were published before 2013, rely on relatively weak hardness assumptions but have the undesirable property that the size of the signature is linear in the number of group users. A recent scheme (Laguillaumie, Langlois, Libert, Stehlé ‘13) achieves logarithmic signature size but it has to rely on relatively strong hardness assumptions. Our construction, thus, simultaneously achieves the good features of the existing schemes. Doctor of Philosophy (SPMS) 2014-01-07T09:11:19Z 2014-01-07T09:11:19Z 2013 2013 Thesis Nguyen, T. T. K. (2013). Zero-knowledge proof systems for lattice-based cryptography. Doctoral thesis, Nanyang Technological University, Singapore. http://hdl.handle.net/10356/55283 en 207 p. application/pdf |
| spellingShingle | DRNTU::Science::Mathematics::Discrete mathematics::Cryptography Nguyen, Ta Toan Khoa Zero-knowledge proof systems for lattice-based cryptography |
| title | Zero-knowledge proof systems for lattice-based cryptography |
| title_full | Zero-knowledge proof systems for lattice-based cryptography |
| title_fullStr | Zero-knowledge proof systems for lattice-based cryptography |
| title_full_unstemmed | Zero-knowledge proof systems for lattice-based cryptography |
| title_short | Zero-knowledge proof systems for lattice-based cryptography |
| title_sort | zero knowledge proof systems for lattice based cryptography |
| topic | DRNTU::Science::Mathematics::Discrete mathematics::Cryptography |
| url | http://hdl.handle.net/10356/55283 |
| work_keys_str_mv | AT nguyentatoankhoa zeroknowledgeproofsystemsforlatticebasedcryptography |