针对全同态加密体制的反馈攻击

Feedback Attack Against Fully Homomorphic Encryption System

全同态加密体制能够在不解密的条件下对密文进行任意的函数运算,是解决云计算中数据隐私保护难题的关键技术。构造全同态加密方案的核心是有效控制密文同态运算中的噪声增长,稀疏子集和问题是实现该目标所需的基本困难性问题。针对基于该问题困难性的全同态加密方案,提出一种改进的反馈攻击方法,使攻击者可以对公钥中的部分数据进行特定计算,通过访问解密谕示得到完整的私钥。分析结果表明,该方法能够充分利用预计算提高攻击效率,对基于稀疏子集和问题的全同态加密方案具有良好的适用性。

Fully Homomorphic Encryption（FHE） allows one to compute arbitrary functions over encrypted data without the decryption key. It is an important technology for private data protection in cloud computing. The highlight of constructing a FHE scheme is to successfully control the noise produced during the homomorphic operations ofciphertexts. The Sparse Subset Sum Problem（SSSP） is one of the basic hard problems used for the noise control. An improved reaction attack against FHE schemes based on the hardness of SSSP is proposed. The adversary can take special computation for the public key, and get the whole decryption key through access to the decryption oracle. Analysis result shows that compared with the known similar attacks, the advantage of the attack is the full use of pre-computing, which improves the efficiency and gains better applicability.