刘钦菊,路献辉,李 杰,王鲲鹏

1.中国科学院 信息工程研究所 信息安全国家重点实验室,北京 100093

2.中国科学院大学 网络空间安全学院,北京 100049

1 引言

目前,在大数据和云计算等应用的驱动下,数据的隐私保护问题越来越受到人们的重视.全同态加密(fully homomorphic encryption,FHE)是目前用来解决数据隐私保护的主要技术手段之一.

全同态加密最早可以追溯到1978年,Rivest等人[1]针对“保密数据库”(private data banks)的应用场景提出了全同态加密的概念(当时被称之为“隐私同态,privacy homomorphic”).在此后的三十年里,密码学家们对同态加密进行了非常深入的研究,相继提出了单同态加密方案(partial homomorphic encryption,PHE)和部分同态加密方案(somewhat homomorphic encryption,SHE).单同态加密方案的特点是只能够支持同态加法或者同态乘法中的单一同态运算,代表方案有支持乘法同态的GM82方案[2]和ElGamal[3]方案以及支持加法同态的Paillier[4]方案.部分同态加密方案的特点是能够支持有限次数的同态加法和同态乘法,其代表方案为BGN05[5],该方案是基于双线性映射中的困难问题构造出来的,它除了能够支持任意多次的同态加法之外,还能够支持一次同态乘法,而且不会增加密文的尺寸.第一个可行的全同态加密方案是由Gentry于2009年基于理想格上的困难问题构造出来的[6].具有代表性的单同态加密方案,部分同态加密方案以及全同态加密方案在图1中给出.

图1 同态加密发展的时间线Figure 1 Timeline of homomorphic encryption

2009年,Gentry除了给出第一个可行的全同态加密方案之外,还给出了构造全同态加密方案的理论框架.该理论框架首先构……