Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based

Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based

2013 | Craig Gentry, Amit Sahai, and Brent Waters
This paper presents a new fully homomorphic encryption (FHE) scheme based on the Learning with Errors (LWE) problem. The scheme is conceptually simpler and asymptotically faster than previous LWE-based FHE schemes. The key innovation is the use of an "approximate eigenvector" method, which allows homomorphic addition and multiplication to be performed as simple matrix operations. This eliminates the need for relinearization, which was a complex and expensive step in previous schemes. The new scheme also supports identity-based FHE and attribute-based FHE, enabling homomorphic processing of data encrypted under the same index. The scheme is based on the LWE problem and is secure under the assumption that solving LWE is computationally hard. The scheme is efficient and can evaluate circuits of polynomial depth without bootstrapping. The paper also provides a detailed analysis of the scheme's performance and security.This paper presents a new fully homomorphic encryption (FHE) scheme based on the Learning with Errors (LWE) problem. The scheme is conceptually simpler and asymptotically faster than previous LWE-based FHE schemes. The key innovation is the use of an "approximate eigenvector" method, which allows homomorphic addition and multiplication to be performed as simple matrix operations. This eliminates the need for relinearization, which was a complex and expensive step in previous schemes. The new scheme also supports identity-based FHE and attribute-based FHE, enabling homomorphic processing of data encrypted under the same index. The scheme is based on the LWE problem and is secure under the assumption that solving LWE is computationally hard. The scheme is efficient and can evaluate circuits of polynomial depth without bootstrapping. The paper also provides a detailed analysis of the scheme's performance and security.
Reach us at info@study.space
[slides and audio] Homomorphic Encryption from Learning with Errors%3A Conceptually-Simpler%2C Asymptotically-Faster%2C Attribute-Based