Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based.

*(English)*Zbl 1310.94148
Canetti, Ran (ed.) et al., Advances in cryptology – CRYPTO 2013. 33rd annual cryptology conference, Santa Barbara, CA, USA, August 18–22, 2013. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-40040-7/pbk). Lecture Notes in Computer Science 8042, 75-92 (2013).

Summary: We describe a comparatively simple fully homomorphic encryption (FHE) scheme based on the learning with errors (LWE) problem. In previous LWE-based FHE schemes, multiplication is a complicated and expensive step involving “relinearization”. In this work, we propose a new technique for building FHE schemes that we call the approximate eigenvector method. In our scheme, for the most part, homomorphic addition and multiplication are just matrix addition and multiplication. This makes our scheme both asymptotically faster and (we believe) easier to understand.

In previous schemes, the homomorphic evaluator needs to obtain the user’s “evaluation key”, which consists of a chain of encrypted secret keys. Our scheme has no evaluation key. The evaluator can do homomorphic operations without knowing the user’s public key at all, except for some basic parameters. This fact helps us construct the first identity-based FHE scheme. Using similar techniques, we show how to compile a recent attribute-based encryption scheme for circuits by Gorbunov et al. into an attribute-based FHE scheme that permits data encrypted under the same index to be processed homomorphically.

For the entire collection see [Zbl 1270.94007].

In previous schemes, the homomorphic evaluator needs to obtain the user’s “evaluation key”, which consists of a chain of encrypted secret keys. Our scheme has no evaluation key. The evaluator can do homomorphic operations without knowing the user’s public key at all, except for some basic parameters. This fact helps us construct the first identity-based FHE scheme. Using similar techniques, we show how to compile a recent attribute-based encryption scheme for circuits by Gorbunov et al. into an attribute-based FHE scheme that permits data encrypted under the same index to be processed homomorphically.

For the entire collection see [Zbl 1270.94007].

##### MSC:

94A60 | Cryptography |