Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem
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 fo...
Saved in:
Main Authors: | , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2020
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/140697 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-140697 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-1406972020-06-01T07:50:08Z Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem Aung, Khin Mi Mi Lee, Hyung Tae Tan, Benjamin Hong Meng Wang, Huaxiong School of Physical and Mathematical Sciences Science::Mathematics Fully Homomorphic Encryption Non-binary Plaintexts 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. MOE (Min. of Education, S’pore) 2020-06-01T07:50:08Z 2020-06-01T07:50:08Z 2018 Journal Article 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 0304-3975 https://hdl.handle.net/10356/140697 10.1016/j.tcs.2018.11.014 2-s2.0-85057201635 771 49 70 en Theoretical Computer Science © 2018 Elsevier B.V. All rights reserved. |
institution |
Nanyang Technological University |
building |
NTU Library |
country |
Singapore |
collection |
DR-NTU |
language |
English |
topic |
Science::Mathematics Fully Homomorphic Encryption Non-binary Plaintexts |
spellingShingle |
Science::Mathematics Fully Homomorphic Encryption Non-binary Plaintexts Aung, Khin Mi Mi Lee, Hyung Tae Tan, Benjamin Hong Meng Wang, Huaxiong Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem |
description |
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. |
author2 |
School of Physical and Mathematical Sciences |
author_facet |
School of Physical and Mathematical Sciences Aung, Khin Mi Mi Lee, Hyung Tae Tan, Benjamin Hong Meng Wang, Huaxiong |
format |
Article |
author |
Aung, Khin Mi Mi Lee, Hyung Tae Tan, Benjamin Hong Meng Wang, Huaxiong |
author_sort |
Aung, Khin Mi Mi |
title |
Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem |
title_short |
Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem |
title_full |
Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem |
title_fullStr |
Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem |
title_full_unstemmed |
Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem |
title_sort |
fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem |
publishDate |
2020 |
url |
https://hdl.handle.net/10356/140697 |
_version_ |
1681056682700963840 |