Please use this identifier to cite or link to this item:
https://hdl.handle.net/10356/140697
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Aung, Khin Mi Mi | en_US |
dc.contributor.author | Lee, Hyung Tae | en_US |
dc.contributor.author | Tan, Benjamin Hong Meng | en_US |
dc.contributor.author | Wang, Huaxiong | en_US |
dc.date.accessioned | 2020-06-01T07:50:08Z | - |
dc.date.available | 2020-06-01T07:50:08Z | - |
dc.date.issued | 2018 | - |
dc.identifier.citation | 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 | en_US |
dc.identifier.issn | 0304-3975 | en_US |
dc.identifier.uri | https://hdl.handle.net/10356/140697 | - |
dc.description.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. | en_US |
dc.description.sponsorship | MOE (Min. of Education, S’pore) | en_US |
dc.language.iso | en | en_US |
dc.relation.ispartof | Theoretical Computer Science | en_US |
dc.rights | © 2018 Elsevier B.V. All rights reserved. | en_US |
dc.subject | Science::Mathematics | en_US |
dc.title | Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem | en_US |
dc.type | Journal Article | en |
dc.contributor.school | School of Physical and Mathematical Sciences | en_US |
dc.identifier.doi | 10.1016/j.tcs.2018.11.014 | - |
dc.identifier.scopus | 2-s2.0-85057201635 | - |
dc.identifier.volume | 771 | en_US |
dc.identifier.spage | 49 | en_US |
dc.identifier.epage | 70 | en_US |
dc.subject.keywords | Fully Homomorphic Encryption | en_US |
dc.subject.keywords | Non-binary Plaintexts | en_US |
item.fulltext | No Fulltext | - |
item.grantfulltext | none | - |
Appears in Collections: | SPMS Journal Articles |
SCOPUSTM
Citations
20
11
Updated on Mar 26, 2024
Web of ScienceTM
Citations
20
6
Updated on Oct 27, 2023
Page view(s)
251
Updated on Mar 29, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.