Privacy-preserving protocols from lattice cryptography

• Main Author: Tan, Benjamin Hong Meng
• Other Authors: Wang Huaxiong
• Format: Theses and Dissertations
• Language: English
• Published: 2019
• Subjects: DRNTU::Science::Mathematics::Discrete mathematics::Cryptography
• Online Access: https://hdl.handle.net/10356/88691; http://hdl.handle.net/10220/48357
• Institution: Nanyang Technological University

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.