Ring Learning With Errors assumption has become an important building block in many modern cryptographic applications, such as (fully) homomorphic encryption and post-quantum cryptosystems like the recently announced NIST CRYSTALS-Kyber public key encryption scheme. In this thesis, we provide an enhanced security foundation for Ring-LWE based cryptosystems and demonstrate their practical potential in real world applications.
Enhanced Foundation. We extend the known pseudorandomness of Ring-LWE to be based on ideal lattices of non Dedekind domains. In earlier works of Lyubashevsky, Perkert and Regev (EUROCRYPT 2010), and Peikert, Regev and Stephens-Davidowitz (STOC 2017), the hardness of RLWE was established on ideal lattices of ring of integers of number fields, which are known to be Dedekind domains. These works extended Regev's (STOC 2005) quantum polynomial-time reduction for LWE, thus allowing more efficient and more structured cryptosystems.
However, the additional algebraic structure of ideals of Dedekind domains leaves open the possibility that such ideal lattices are not as hard as general lattices. We show that, the Ring-LWE hardness can be based on the polynomial ring, which is potentially be a strict sub-ring of the ring of integers of a number field, and hence not be a Dedekind domain. We present a novel proof technique that builds an algebraic theory for general such rings that also include cyclotomic rings. We also recommend a ``twisted'' cyclotomic field as an alternative for the cyclotomic field used in CRYSTALS-Kyber, as it leads to a more efficient implementation and is based on hardness of ideals in a non Dedekind domain. We leverages the polynomial nature of Ring-LWE, and introduce XSPIR, a new symmetrically private information retrieval (SPIR) protocol, which provides a stronger security guarantee than existing efficient PIR protocols.
Like other PIR protocol, XSPIR allows a client to retrieve a specific entry from a server's database without revealing which entry is retrieved. Moreover, the semi-honest client learns no additional information about the database except for the retrieved entry. We demonstrate through analyses and experiments that XSPIR has only a slight overhead compared to state-of-the-art PIR protocols, and provides a stronger security guarantee while enabling the client to perform more complicated queries than simple retrievals.
| Identifer | oai:union.ndltd.org:columbia.edu/oai:academiccommons.columbia.edu:10.7916/p8nx-wj85 |
| Date | January 2022 |
| Creators | Lin, Chengyu |
| Source Sets | Columbia University |
| Language | English |
| Detected Language | English |
| Type | Theses |
Page generated in 0.0019 seconds