Privacy-preserving protocols from lattice cryptography
Data privacy is a major challenge that is not easy to solve. More and more attacks are happening and 2017 was another record year for data breaches and cyber incidents. On top of that, recent advances in quantum computers show how vulnerable the foundations of a secure Internet is today. Most pub...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2019
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/88691 http://hdl.handle.net/10220/48357 |
| _version_ | 1811686118425362432 |
|---|---|
| author | Tan, Benjamin Hong Meng |
| author2 | Wang Huaxiong |
| author_facet | Wang Huaxiong Tan, Benjamin Hong Meng |
| author_sort | Tan, Benjamin Hong Meng |
| collection | NTU |
| description | Data privacy is a major challenge that is not easy to solve. More and more attacks are
happening and 2017 was another record year for data breaches and cyber incidents. On
top of that, recent advances in quantum computers show how vulnerable the foundations
of a secure Internet is today. Most public-key cryptography in use today will be completely
broken once large-scale quantum computers are available.
Over the last decade, lattice cryptography received a lot of attention and is now one
of the prime candidates for NIST’s post-quantum standardization efforts. Besides its
conjectured resistance against quantum attacks, the main average-case problems, short
integer solution and learning with errors, enjoy reductions to worst-case hardness of lattice
problems. Lattice cryptography is also very versatile, having been used to construct many
advanced cryptographic schemes like fully homomorphic encryption (FHE), which is seen
as the “holy grail” of cryptography by some.
In this thesis, we use lattices to address these concerns and propose several privacy-
preserving protocols from lattices. Our contributions can be grouped into two categories:
(i) private database queries on outsourced database and (ii) zero-knowledge protocols for
database queries and password policy check.
In the first scenario, we use fully homomorphic encryption for finite extension fields
and design a wildcard pattern matching algorithm on encrypted strings and patterns.
Our algorithm is the first to support an exclusion wildcard !(c), which demands that
a non-empty character that is not c be in its position. The algorithm’s usefulness is
highlighted by combining it with exact matching in two protocols, evaluating conjunctive
and disjunctive queries, in contrast to the similar schemes from FHE that cannot do so
without expensive modifications (Yasuda et al. ’14 and Saha, Koshiba ’16). Experimental
results show that it is highly parallelizable and especially efficient when combined with
multi-threading.
Besides that, we present a private order comparison algorithm for encrypted integers
by exploiting the structure of finite extension fields. Our algorithm is comparable in per-
formance to Boolean circuit-based methods (Cheon, Kim, and Kim ’15, ’16) and improves
the ciphertext expansion factor by at an order of magnitude. We obtain a private database
query protocol for range conditions as well as a conjunctive query with multiple order
and equality conditions, showcasing the versatility of the algorithm. The protocols do
not reveal intermediate results, such as whether individual conditions are satisfied unlike
some protocols based on order-preserving/revealing and partial homomorphic encryption.
7
In the domain of zero-knowledge protocols, we show that zero-knowledge elementary
databases (ZK-EDB), which is used to prove statements of the form “x has a non-empty
value D(x) = y in the database D” or “x does not have a corresponding value in the
database D” without revealing any additional information about the database, can sup-
port a much richer class of queries. We dub such schemes, zero-knowledge expressive
elementary databases (ZK-EEDB), and prove range queries over keys, values and records
of a database modulo a new security requirement that is satisfied by all previously known
constructions. Moreover, we give the first quantum-resistant construction of trapdoor
mercurial commitments from lattices, shown to imply ZK-EDB (Chase et al. ’05).
Finally, we introduce a lattice-based zero-knowledge password policy check protocol,
the first of its kind that can potentially resist quantum adversaries. This is the first piece
of a quantum-resistant privacy-preserving password registration, authentication and key
exchange suite that allows users to register and use for authentication and key exchange
passwords without ever revealing them to servers; thereby protecting this highly sensitive
piece of data. We apply the KTX commitment scheme (Kawachi, Tanaka, Xagawa ’09) to
construct a randomized password hashing scheme. Then, we employ an abstract Stern-
like protocol (Libert et al. ’16) to prove that a password hashed with the randomized
password hashing scheme we built satisfies the mandated password policy from the server
in zero-knowledge. Notably, our techniques, adapted to the challenges of a lattice-based
instantiation, do not follow the KM framework (Kiefer and Manulis ’14), using binary
strings to encode passwords and relying only on standard commitments. |
| first_indexed | 2024-10-01T04:55:20Z |
| format | Thesis |
| id | ntu-10356/88691 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:55:20Z |
| publishDate | 2019 |
| record_format | dspace |
| spelling | ntu-10356/886912023-02-28T23:42:49Z Privacy-preserving protocols from lattice cryptography Tan, Benjamin Hong Meng Wang Huaxiong School of Physical and Mathematical Sciences DRNTU::Science::Mathematics::Discrete mathematics::Cryptography Data privacy is a major challenge that is not easy to solve. More and more attacks are happening and 2017 was another record year for data breaches and cyber incidents. On top of that, recent advances in quantum computers show how vulnerable the foundations of a secure Internet is today. Most public-key cryptography in use today will be completely broken once large-scale quantum computers are available. Over the last decade, lattice cryptography received a lot of attention and is now one of the prime candidates for NIST’s post-quantum standardization efforts. Besides its conjectured resistance against quantum attacks, the main average-case problems, short integer solution and learning with errors, enjoy reductions to worst-case hardness of lattice problems. Lattice cryptography is also very versatile, having been used to construct many advanced cryptographic schemes like fully homomorphic encryption (FHE), which is seen as the “holy grail” of cryptography by some. In this thesis, we use lattices to address these concerns and propose several privacy- preserving protocols from lattices. Our contributions can be grouped into two categories: (i) private database queries on outsourced database and (ii) zero-knowledge protocols for database queries and password policy check. In the first scenario, we use fully homomorphic encryption for finite extension fields and design a wildcard pattern matching algorithm on encrypted strings and patterns. Our algorithm is the first to support an exclusion wildcard !(c), which demands that a non-empty character that is not c be in its position. The algorithm’s usefulness is highlighted by combining it with exact matching in two protocols, evaluating conjunctive and disjunctive queries, in contrast to the similar schemes from FHE that cannot do so without expensive modifications (Yasuda et al. ’14 and Saha, Koshiba ’16). Experimental results show that it is highly parallelizable and especially efficient when combined with multi-threading. Besides that, we present a private order comparison algorithm for encrypted integers by exploiting the structure of finite extension fields. Our algorithm is comparable in per- formance to Boolean circuit-based methods (Cheon, Kim, and Kim ’15, ’16) and improves the ciphertext expansion factor by at an order of magnitude. We obtain a private database query protocol for range conditions as well as a conjunctive query with multiple order and equality conditions, showcasing the versatility of the algorithm. The protocols do not reveal intermediate results, such as whether individual conditions are satisfied unlike some protocols based on order-preserving/revealing and partial homomorphic encryption. 7 In the domain of zero-knowledge protocols, we show that zero-knowledge elementary databases (ZK-EDB), which is used to prove statements of the form “x has a non-empty value D(x) = y in the database D” or “x does not have a corresponding value in the database D” without revealing any additional information about the database, can sup- port a much richer class of queries. We dub such schemes, zero-knowledge expressive elementary databases (ZK-EEDB), and prove range queries over keys, values and records of a database modulo a new security requirement that is satisfied by all previously known constructions. Moreover, we give the first quantum-resistant construction of trapdoor mercurial commitments from lattices, shown to imply ZK-EDB (Chase et al. ’05). Finally, we introduce a lattice-based zero-knowledge password policy check protocol, the first of its kind that can potentially resist quantum adversaries. This is the first piece of a quantum-resistant privacy-preserving password registration, authentication and key exchange suite that allows users to register and use for authentication and key exchange passwords without ever revealing them to servers; thereby protecting this highly sensitive piece of data. We apply the KTX commitment scheme (Kawachi, Tanaka, Xagawa ’09) to construct a randomized password hashing scheme. Then, we employ an abstract Stern- like protocol (Libert et al. ’16) to prove that a password hashed with the randomized password hashing scheme we built satisfies the mandated password policy from the server in zero-knowledge. Notably, our techniques, adapted to the challenges of a lattice-based instantiation, do not follow the KM framework (Kiefer and Manulis ’14), using binary strings to encode passwords and relying only on standard commitments. Doctor of Philosophy 2019-05-24T05:38:17Z 2019-12-06T17:08:56Z 2019-05-24T05:38:17Z 2019-12-06T17:08:56Z 2019 Thesis Tan, B. H. M. (2019). Privacy-preserving protocols from lattice cryptography. Doctoral thesis, Nanyang Technological University, Singapore. https://hdl.handle.net/10356/88691 http://hdl.handle.net/10220/48357 10.32657/10220/48357 en 185 p. application/pdf |
| spellingShingle | DRNTU::Science::Mathematics::Discrete mathematics::Cryptography Tan, Benjamin Hong Meng Privacy-preserving protocols from lattice cryptography |
| title | Privacy-preserving protocols from lattice cryptography |
| title_full | Privacy-preserving protocols from lattice cryptography |
| title_fullStr | Privacy-preserving protocols from lattice cryptography |
| title_full_unstemmed | Privacy-preserving protocols from lattice cryptography |
| title_short | Privacy-preserving protocols from lattice cryptography |
| title_sort | privacy preserving protocols from lattice cryptography |
| topic | DRNTU::Science::Mathematics::Discrete mathematics::Cryptography |
| url | https://hdl.handle.net/10356/88691 http://hdl.handle.net/10220/48357 |
| work_keys_str_mv | AT tanbenjaminhongmeng privacypreservingprotocolsfromlatticecryptography |