Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/140697
Title: Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem
Authors: Aung, Khin Mi Mi
Lee, Hyung Tae
Tan, Benjamin Hong Meng
Wang, Huaxiong
Keywords: Science::Mathematics
Issue Date: 2018
Source: Aung, K. M. M., Lee, H. T., Tan, B. H. M., & Wang, H. (2019). Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem. Theoretical Computer Science, 771, 49-70. doi:10.1016/j.tcs.2018.11.014
Journal: Theoretical Computer Science
Abstract: In this work, we solve the open problem of designing a fully homomorphic encryption scheme over the integers for non-binary plaintexts in Z Q 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 Q≥3 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, Q=3 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 benefits.
URI: https://hdl.handle.net/10356/140697
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2018.11.014
Rights: © 2018 Elsevier B.V. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SPMS Journal Articles

SCOPUSTM   
Citations 50

6
Updated on Jan 21, 2023

Web of ScienceTM
Citations 50

4
Updated on Jan 26, 2023

Page view(s)

186
Updated on Jan 29, 2023

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.