Fully-Homomorphic Encryption from Lattice Isomorphism

This chapter delves into the fascinating world of lattice-based cryptography, focusing on the lattice isomorphism problem (LIP) and its potential applications in constructing fully-homomorphic encryption (FHE) schemes. The text begins by defining rank-n lattices and discussing the historical context of lattice-based cryptography, including the celebrated LLL algorithm and Ajtai's connection with cryptography. The chapter then explores the significance of lattices in post-quantum and quantum cryptography, highlighting their role in the first construction of FHE. The authors present their main result, which constructs a fully-homomorphic encryption scheme with a reduction to a circular variant of LIP. They also discuss the hardness of the distinguish-LIP problem and its implications for the security of their scheme. The chapter concludes with a technical outline of their base encryption scheme and a discussion of why known techniques fail to apply in their context. Throughout the text, the authors emphasize the importance of expanding the technical toolkit available for LIP-based cryptosystems and the potential of LIP to serve as a candidate FHE construction even in the event of a cryptanalytic breakthrough against LWE. The chapter also highlights the possibility of designing more efficient FHE schemes and kickstarting new techniques in computation on encrypted data. The authors present a detailed analysis of their scheme, including its correctness, security, and homomorphic operations. They also discuss the parameters of their scheme and the constraints imposed by their basic encryption scheme. Finally, the chapter concludes with a discussion of bootstrapping and the potential of their scheme to evaluate its own decryption circuit, following Gentry's bootstrapping theorem.