Research On Threshold Fully Homomorphic Encryption Scheme Based On AGCD Problem

Fully homomorphic encryption(FHE)is one of the most advanced privacy-protection technologies.It allows direct operation on ciphertexts which is equivalent to the same operation on original data.It can realize infinite homomorphic operations in theory.These features make fully homomorphic encryption widely used in many fields,such as cloud computing,secure multi-party computing,threshold signature,electronic voting and so on.Especially in the cloud computing scenario,resource-constrained client devices can use fully homomorphic encryption to securely outsource computing intensive tasks to a semi-honest server.In this process,no original data set will be disclosed to the server,which plays an important role in the development of cloud computing.However,for highly sensitive application scenarios such as medical treatment and finance,it may be necessary to achieve higher security,such as threshold decryption.In the development of fully homomorphic encryption,it can be divided into two lines,namely,FHE schemes on lattice based on LWE problem and FHE schemes on integers based on AGCD problem.These two types of schemes are competitive.When one type proposes a new function,the other will realize the same function soon.These studies are very meaningful because they are based on different difficult assumptions.However,due to different structures,the same function cannot be directly extended to another type of scheme,and generally it will be realized based on completely different technical routes.The threshold functionality can be added to a fully homomorphic encryption scheme based on the learning with errors(LWE)problem by BGG+[1](CRYPTO 2018).In addition,BGG+[1]proposed the concept of universal thresholdizer,which can adjoin threshold functionality to many cryptographic schemes,such as threshold signatures.However,BGG+[1]only support FHE schemes with a linear relationship between the secret key and the decryption function,which means that AGCD-based FHE schemes can not use the methods in BGG+[1]directly.Up to now,FHE schemes over integers still has no accessto threshold decryption.BGG+[1]raised a challenging public problem: can threshold fully homomorphic encryption be realized from other standard assumptions?In order to solve the problem,we construct two threshold fully homomorphic encryption schemes based on AGCD problem.It is proved that a universal thresholdizer can be constructed based on these two schemes.In cryptographic theory,this paper promotes the development of FHE over integers.At the application level,this paper implements a more flexible and practical ciphertext access control structure for FHE schemes over integers.Based on different difficult assumptions and different technologies,it is very meaningful to obtain FHE schemes with similar properties.The main contributions of this paper include the following:1.Threshold FHE based on Asmuth-Bloom’s secret sharing.This scheme is based on the Batch FHE scheme over integers.It makes full use of the construction of the original FHE scheme,and produces almost no additional overhead compared with the original FHE scheme.Our method produces a lower overhead of O(t)in recovery process compared with O(t log2(t))in BGG+.[1]We prove that this scheme satisfies evaluation correctness,compactness,semantic security,simulation security and IND-CPA security,and can be used to construct universal thresholdizers.2.Threshold FHE based on Shamir’s secret sharing.We also put forward a Th FHE scheme from Shamir’s secret sharing,which has a compatible structure to suit any FHE scheme based on AGCD assumption or its variants.The time complexity of secret recovery in this scheme is O(t log2(t)),which is slightly higher than that in the first scheme.However,this scheme provides a general framework,and its advantages are flexibility and expansibility.It can be used in different FHE schemes.We prove that this scheme satisfies evaluation correctness,compactness,semantic security,simulation security and IND-CPA security,and can be used to construct universal thresholdizers.3.Simulation experiments and efficiency analysis.For the two threshold FHEschemes,this paper designs simulation experiments to analyze the efficiency of the schemes,and compares them with BGG+’s threshold FHE scheme.[1]Experiments show that the two threshold FHE schemes proposed in this paper will not affect the efficiency of the original schemes under any security level,and the overhead of the key distribution and secret recovery is also very small.At the same time,the additional overhead generated by the threshold FHE schemes proposed in this paper is roughly the same as that generated by BGG+’s.[1]...