# zbMATH — the first resource for mathematics

Fully homomorphic encryption without modulus switching from classical GapSVP. (English) Zbl 1296.94091
Safavi-Naini, Reihaneh (ed.) et al., Advances in cryptology – CRYPTO 2012. 32nd annual cryptology conference, Santa Barbara, CA, USA, August 19–23, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32008-8/pbk). Lecture Notes in Computer Science 7417, 868-886 (2012).
Summary: We present a new tensoring technique for LWE-based fully homomorphic encryption. While in all previous works, the ciphertext noise grows quadratically $$(B \rightarrow B ^{2}\cdot \text{poly}(n))$$ with every multiplication (before “refreshing”), our noise only grows linearly $$(B \rightarrow B\cdot \text{poly}(n))$$.
We use this technique to construct a scale-invariant fully homomorphic encryption scheme, whose properties only depend on the ratio between the modulus $$q$$ and the initial noise level $$B$$, and not on their absolute values.
Our scheme has a number of advantages over previous candidates: It uses the same modulus throughout the evaluation process (no need for “modulus switching”), and this modulus can take arbitrary form. In addition, security can be classically reduced from the worst-case hardness of the GapSVP problem (with quasi-polynomial approximation factor), whereas previous constructions could only exhibit a quantum reduction from GapSVP.
For the entire collection see [Zbl 1246.94010].

##### MSC:
 94A60 Cryptography
Full Text: