基于全同态加密与对称加密融合的批处理方案

Batch Scheme Based on Fully Homomorphic Encryption-Symmetric Encryption Framework

摘要:

现有的全同态加密方案都具有很大的密文膨胀问题,该问题是制约实际应用的重要瓶颈.为了提高传输效率,Naehrig等提出了混合加密的想法,即用户使用密钥为k的对称算法E加密明文m,再使用公钥为pk的全同态方案加密密钥k,将缩小尺寸后的密文c′=(HEpk(k),Ek(m))发送给云端,云端可以同态运算解密电路CE-1解压出同态密文HEpk(m).本文将全同态加密与对称加密融合方案推广到批处理形式,利用中国剩余定理将l个密文Ek(m0),…,Ek(ml-1)打包进一个密文C中,将C′=(HEpk(k),C)发送给云端.云端利用C′,只需要同态运算CE-1一次就可以恢复出全部的HEpk(mi),这个过程在原方案中需要进行l次.通过这种方式,极大地缩短了原本需要耗费大量计算的同态运算解密电路过程.文中以批处理GSW13全同态加密与FLIP流密码融合方案为例详细说明了这一过程.与原方案相比,对于安全参数为λ的FLIP流密码方案,批处理方案可以将这个过程的计算复杂性从O~(λ3)缩小到O~(λ2).

Abstract:

All homomorphic encryption schemes proposed so far suffer from a very large ciphertext expansion, which is a very significant bottleneck in practice. In order to improve the transmission efficiency, Naehrig et al. proposed an idea of hybrid encryption, i.e. a user encrypt some plaintext m with a symmetric encryption scheme E under some private key k, and encrypt the private key k with a homomorphic encryption scheme under some public key pk, transmit a much smaller cipertext c′=(HEpk(k),Ek(m)) that cloud decompresses homomorphically into the HEpk(m) through a decryption circuit CE-1. In this paper, we extend the Fully Homomorphic EncryptionSymmetric Encryption framework into a batch one, i.e. we use the Chinese Remainder Theorem to pack l ciphertexts Ek(m0),…,Ek(ml-1) into a single C, send C′=(HEpk(k),C) to the cloud. Given C′, cloud only needs to homomorphically evaluate CE-1 for once to recover all HEpk(mi), rather than l times in original scheme. By this way, we can greatly reduce the times of homomorphically evaluating decryption circuit, which costs a lot of computation. We also give out an instance of batch GSW13FLIP scheme to explain in detail. Comparing to original scheme, our batch scheme can reduce the computational complexity from O~(λ3) to O~(λ2), where λ is security parameter of FLIP.