The paper introduces a new fully homomorphic encryption (FHE) scheme based on the Learning with Errors (LWE) problem. The scheme is conceptually simpler and asymptotically faster compared to previous LWE-based FHE schemes, which often involve complex and expensive multiplication steps. The key innovation is the *approximate eigenvector* method, which allows homomorphic addition and multiplication to be performed as simple matrix operations, eliminating the need for relinearization and evaluation keys. This makes the scheme easier to understand and implement.
The scheme supports identity-based FHE, where the evaluator can perform homomorphic operations without needing the user's specific evaluation key, and attribute-based FHE, where messages encrypted under the same index can be processed homomorphically. The authors also provide a compiler that transforms any LWE-based identity-based encryption scheme into an identity-based FHE scheme, and show how to compile an attribute-based encryption scheme for circuits into an attribute-based FHE scheme.
The paper includes a detailed analysis of the scheme's security, performance, and optimization techniques, demonstrating that it achieves better asymptotic complexity compared to previous LWE-based FHE schemes. The scheme is particularly efficient for evaluating circuits of polynomial depth or log-depth, and it retains the advantages of other LWE-based FHE schemes, such as optional bootstrapping and security based on LWE for quasi-polynomial factors.The paper introduces a new fully homomorphic encryption (FHE) scheme based on the Learning with Errors (LWE) problem. The scheme is conceptually simpler and asymptotically faster compared to previous LWE-based FHE schemes, which often involve complex and expensive multiplication steps. The key innovation is the *approximate eigenvector* method, which allows homomorphic addition and multiplication to be performed as simple matrix operations, eliminating the need for relinearization and evaluation keys. This makes the scheme easier to understand and implement.
The scheme supports identity-based FHE, where the evaluator can perform homomorphic operations without needing the user's specific evaluation key, and attribute-based FHE, where messages encrypted under the same index can be processed homomorphically. The authors also provide a compiler that transforms any LWE-based identity-based encryption scheme into an identity-based FHE scheme, and show how to compile an attribute-based encryption scheme for circuits into an attribute-based FHE scheme.
The paper includes a detailed analysis of the scheme's security, performance, and optimization techniques, demonstrating that it achieves better asymptotic complexity compared to previous LWE-based FHE schemes. The scheme is particularly efficient for evaluating circuits of polynomial depth or log-depth, and it retains the advantages of other LWE-based FHE schemes, such as optional bootstrapping and security based on LWE for quasi-polynomial factors.