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].

94A60 Cryptography
Full Text: DOI