Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem

Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem
Title:
Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem
Other Titles:
Theoretical Computer Science
Publication Date:
23 November 2018
Citation:
Khin Mi Mi Aung, Hyung Tae Lee, Benjamin Hong Meng Tan, Huaxiong Wang, Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem, Theoretical Computer Science, Volume 771, 2019, Pages 49-70, ISSN 0304-3975, https://doi.org/10.1016/j.tcs.2018.11.014.
Abstract:
In this work, we solve the open problem of designing a fully homomorphic encryption scheme over the integers for non-binary plaintexts in for prime Q (Q-FHE-OI) without the hardness of the sparse subset sum problem (SSSP). Furthermore, we show that our Q-FHE-OI scheme is a useful optimization for evaluating arithmetic circuits on encrypted data for some primes. To that end, we provide a natural extension of the somewhat homomorphic encryption (SHE) scheme over the integers proposed by Cheon and Stehlé (Eurocrypt 2015) to support non-binary plaintexts. Then, a novel bootstrapping algorithm is proposed for this extended SHE scheme by introducing generalizations of several functions in binary arithmetic. As a result, we obtain a Q-FHE-OI scheme for any constant-sized prime without the hardness of the SSSP, whose bootstrapping algorithm is asymptotically as efficient as previous best results. Beyond that, we compare the efficiency of our scheme against a Q-FHE-OI scheme obtained by emulating mod-Q gates with boolean circuits as proposed by Kim and Tibouchi (CANS 2016). Our analysis indicates our proposed scheme performs better for prime Q up to 11287, which improves on the result of Kim and Tibouchi, who showed there is at most one prime, where the Q-FHE-OI scheme by Nuida and Kurosawa (Eurocrypt 2015) is a better approach. This overturns our previous understanding that Q-FHE-OI schemes do not provide significant benefit
License type:
http://creativecommons.org/licenses/by-nc-nd/4.0/
Funding Info:
Research Grant TL-9014101684-01; National Research Foundation of Korea NRF- 2018R1C1B6008476; Singapore Ministry of Education MOE2016-T2-2-014(S) and RG133/17 (S)
Description:
ISSN:
0304-3975
Files uploaded:
File Size Format Action
There are no attached files.