1、可信计算与信息保障实验室可信计算与信息保障实验室 主任主任同态密码技术发展与应用同态密码技术发展与应用 目录 一、同态加密技术简介 二、同态加密的发展 三、多密钥全同态加密 四、同态加密的实现与应用 一、同态加密技术简介 数据 函数 用户 云服务器 目标 用户希望得到()要求 用户不希望泄露数据，（服务器不希望泄露函数）方案 =加密数据的同态计算（Rivest et al 1978）()()密钥生成()：输入安全参数，产生公钥，私钥和同态计算密钥evk 加密()：输入公钥和消息，输出密文 解密()：输入私钥和密文，输出消息 同态计算Eval()：输入，函数，计算密钥，密文1,2,，输出密文 逐

2、比特同态运算布尔电路，只需构造同态加法门和同态乘法门 一、同态加密技术简介 Public-Key Homomorphic Encryption RAD78 正确性:紧致性：的解密复杂度与无关 安全性：IND-CPA安全性 IND-CCA2不可能！IND-CCA1？FHE:From private-key to public-key.R11,TCC 一、同态加密技术简介 1,kcc*m1,kmm*c,Eval pk evk f(,)Dec sk(,)Dec sk,f 美国“PROCEED”研究项目 2010年DARPA推出“加密数据可编程计算”PROCEED 2012年白宫推出“大数据研发倡议”

3、，PROCEED纳入其中 欧盟2015年启动的“HEAT”研究计划，“同态加密应用与技术”HE设计与实现，HE应用 工业界同态加密标准的制定和推广 一、同态加密技术简介 1978年Rivest等人提出了同态加密的概念 2009年IBM的Craig Gentry在其博士论文中提出了第一个全同态的加密方案 2014全同态加密前沿学术论坛 二、同态加密的发展 Craig Gentry Gentry和Halevi访问TCA实验室 部分同态加密 第一代全同态加密 第二代全同态加密 第三代全同态加密 二、同态加密的发展 RSA公钥加密算法 RSA77 公钥，其中 =,满足,()=1 加密：=乘法同态：1

4、2=(12)=12 Paillier公钥加密算法 P99 公钥,，加密:=2 加法同态：1 2=1+2(12)2 =1+2 二、同态加密的发展：部分同态 密钥生成 选择大的奇数作为私钥 加密操作 选择随机数保证 加密明文比特 0,1，密文为c=+2+解密操作 计算=mod mod 2 同态计算：+=1+2+2 1+2+1+2 =12+21 12+2 12+12+212+12 二、同态加密的发展：FHE一代 Gentrys Somewhat FHE（整数版本）近似同态加密算法在进行同态运算时会使噪音增长，噪音超过上界会导致密文无法正常解密 SFHE可以同态计算深度不超过的电路 当电路深度超过时？

5、自举算法：假设SFHE可以同态计算自己的解密电路,输入()和(c)，同态计算=,，得到密文=(,)=()用来同态计算，不断循环 二、同态加密的发展：FHE一代 Idea of Bootstrapping 第一代全同态加密思想 利用特殊的代数结构多项式环或者整数环的理想 不同理想表示不同的明文消息 理想本身具有加法和乘法的同态性 特点：基于非标准困难假设 噪音指数增长：进行次同态操作，需要模数 代表性工作 Gentry09方案Gentry 发表于 STOC 09 二、同态加密的发展：FHE一代 第二代FHE思想：分层的同态加密每层密文有不同的解密密钥，第层密文经过同态计算得到第+1层密文，引入计

6、算密钥 特点 标准困难假设LWE问题或者ring LWE问题 噪音亚指数增长：进行次同态操作，需要模数 log Overhead=(同态加密计算时间)/(明文计算时间)可达polylog 同态操作需要计算密钥 代表性工作 BV11方案Brakerski 和 Vaikuntanathan，FOCS 2011 BGV12 Brakerski，Gentry，Vaikuntanathan，ITSC12 二、同态加密的发展：FHE二代 密钥生成：加密：选择随机向量 和噪音 对消息 0,1，计算=,+2+，密文=,解密 计算=,mod mod 2 令 =1,，则解密算法满足,=2+同态加法 +=1+2,1

7、+其中 1+2=1+,+2 1+2+1+2 二、同态加密的发展：FHE二代 BV11方案 Brakerski-Vaikuntanathan，FOCS 2011 令计算张量积 3=1 2，=，乘法同态性 3,=21+1 22+2 =2 212+12+21+12 问题：3的维数为 +12，如何避免维数的指数增长？解决方案：使用维数转换 技术将 3转换为+1维密文3 计算密钥：=，=+2+Powerof2 转换后密文3=BitDecomp 3,BitDecomp 3 +1 BitDecomp 3=BitDecomp 3+2+3,=BitDecomp 3+2+12 比特分解：，BitDecomp =0

8、1 0,1 二次幂乘：，Powerof2 =,2,2 1 二、同态加密的发展：FHE二代 BV11方案 乘法同态 模数转换技术 Brakerski-Gentry-Vaikuntanathan 在 ITSC 2012提出的BGV方案 选择 ；当噪音上界由变成2时，将模数1转换成，使得转换后的噪音小于 进行次同态操作，需计算 log 层电路,只要模数 log 基于ring-LWE的全同态加密 明文为一个环元素而非一比特，密文/明文扩展比为(log)公钥大小为()而非(2)同态乘法可以用快速傅里叶变换实现，复杂度为 而非 3 批量密文技术：密文对应于消息向量，一次同态操作对应于向量中所有元素的批量操

9、作，ring-LWE BGV方案=,log,log 二、同态加密的发展：FHE二代 第三代FHE思想：使用近似特征向量的结构 特点 相比于FHE二代，第三代全同态加密在进行同态计算时不需要额外的evk而可以直接进行同态计算 乘法噪音积累为伪线性：进行次同态操作，需要保证模数 即使基于ring-LWE方案，明文空间为一个比特 不支持基于中国剩余定理的批量密文技术 代表工作：GSW13Gentry Sahai 和 Waters 发表于 CRYPTO 2013 二、同态加密的发展：FHE三代 定义：=+性质：1+2=1+2+1+2 1 2=1+1 2=12+12+12 问题：如何保证新噪音12足够小

10、？工具矩阵MP12：存在 二次幂乘矩阵及可计算逆函数1，对任意的 :1=二、同态加密的发展：FHE三代 近似特征向量 噪音 密钥 密文 明文 近似特征向量 近似特征值 密钥生成：1，私钥=1,，1，公钥=+加密：0,1，密文=+解密：=+同态计算：1+2=1+2+1+2 1 12=1+1 12=12+112+12 乘法噪音的积累是非对称的，是（近似）相加而不是相乘；明文空间为1比特，通过NAND门同态实现一般电路 二、同态加密的发展：FHE三代 GSW方案 Gentry-Sahai-Waters，CRYPTO 2013 LWE BGV ring-LWE BGV LWE GSW ring-LWE

11、 GSW 密文/明文比 ()(log)(2)()同态操作 复杂度 (3)()(2.373)()自举噪音 积累()()()()同态计算 代价 (2)()(1.373)()二、同态加密的发展：FHE三代 CZ17：在同态计算一类特殊的电路（如内积函数）时，基于ring-LWE的BGV方案可以同时实现()噪音积累下自举且同态计算代价不超过()L.Chen,Z.Zhang,Bootstrapping Fully Homomorphic Encryption with Ring Plaintexts within Polynomial Noise,PROVSEC 2017 参与方1,2,有其各自的密钥

12、不同公钥 1,2,加密的密文之间可以进行同态运算，得到一个共同公钥下加密的密文 共同公钥加密的密文可以通过共同解密的方式解密 支持门限解密的多密钥全同态加密可以构造对两轮的任意函数的多方安全计算协议 三、多密钥全同态加密 参与方1,2,有各自的GSW密钥 用户拥有私钥 扩展私钥=1,2,密文扩展：参与方的密文 满足 （公开计算）扩展密文 满足，为扩展的工具矩阵 =00 对扩展密文进行GSW形式同态操作 三、多密钥全同态加密 MKFHE-GSW方案 Clear-McGoldrick，CRYPTO 2014 参与方1,2,有各自的BGV密钥 用户拥有私钥+1；扩展私钥=1,2,密文扩展：参与方的密

13、文满足,=+2 扩展密文=0,0 (+1)，满足,=,evk生成：通过GSW密文的前列构造BGV方案的计算密钥！特点 基于ring-LWE时，明文空间为环元素而非一比特 支持基于CRT的批量密文技术，同态计算代价为(,log)密文扩展复杂度与密文个数无关，只与安全参数相关 L.Chen，Z.Zhang,X.Wang,Batched Multi-hop Multi-key FHE from ring-LWE with Compact Ciphertext Extension,TCC 2017 三、多密钥全同态加密 MKFHE-BGV方案Chen-Zhang-Wang，TCC 2017 HElib

14、 SEAL FV-NFLlib HomomorphicEncryption 四、同态加密的实现与应用 全同态加密的开源实现库 四、同态加密的实现与应用 2010 2012 2011 2013 2014 Moores law 加密数据计算的速度：from Gentrys talk HElib实现了基于ring-LWE的BGV方案 同态实现“AES-128”电路：AES 本身大约有 30,000 门，HElib在4-15 分钟内处理100-200 个blocks 不进行自举:245 秒120 blocks 进行自举:1050 秒180 blocks 同态计算集合交：在五分钟内计算两个加密集合的交集

15、，每个集合大约100,000个元素 Chillotti et al.ASIACRYPT 2016:“Faster Fully Homomorphic Encryption:Bootstrapping in less than 0.1 Seconds”.基于GSW方案，明文空间为1比特 四、同态加密的实现与应用 全同态加密效率实例 iDASH：美国国家卫生局发起的基因检测中的隐私与安全挑战 Cheon-Kim-Song:3.9秒从4M数据中定位并提取询问的基因片段 四、同态加密的实现与应用()()：病人的DNA信息：确定潜在致病基因片段 病人得知自己的致病基因片段()医疗机构不知道任何关于的信息 应用实例：iDASH Microsofts CryptoNets（使用SEAL库）实现对加密数据的神经网络学习 应用于MNIST手写字识别训练库 99%准确率，单一PC上每小时51,739次预测，570秒延迟 四、同态加密的实现与应用 应用实例：隐私保护 同态加密标准研讨会在2017年7月13-14日，由Microsoft Research in Redmond举办 白皮书：http:/homomorphicencryption.org/四、同态加密的实现与应用 同态加密标准化 谢 谢