LWE-based FHE schemes

Learning with Error (LWE) is considered as one of the hardestproblems to solve in practical time for even post-quantum algorithms. First, it was introduced by Oded Regev as an extension of “learning from parity with error” problem [Regev 2009]. Regev reduced the hardness of worst-case lattice problems like SVP to LWE problems, which means that if one can find an algorithm that can solve LWE problem in an efficient time, the same algorithm will also solve the SVP problem in an efficient time. Since then, it is one of the most attractive and promising topics for post-quantum cryptology with its relatively small ciphertext size. Lyubashevsky et al. suggested another significant improvement on the LWE problem which may lead to new applications by introducing ring-LWE (RLWE) problem [Lyubashevsky et al. 2013]. The RLWE problem is an algebraic variant of LWE, which is more efficient for practical applications with strong security proofs. They proved that the RLWE problems are reducible to worst-case problems on ideal lattices, which is hard for polynomial-time quantum algorithms.