一种可对无法直接读取数据信息进行计算的新颖密码术,全同态加密(FHE)技术,即对加密数据进行处理得到的一个加密输出结果,解密后其结果与用同一计算方式处理未加密原始数据得到的输出结果一样――就好像不知道问题也能给出问题的答案一样……

 

  艾丽丝递给鲍勃一个锁着的手提箱请他数数里面的钱有多少。“没问题,”鲍勃说道,“请把钥匙给我。”艾丽丝说没钥匙。鲍勃拎起手提箱,估量着它的重量,再来回摇晃了几下,然而,这些努力并不能让他知道手提箱里究竟有多少现金。
 
  艾丽丝和鲍勃有着多年的合作关系,也都是密码学专家,他俩真正感兴趣的是手提箱里的“计算问题”,而不是东西本身。假设,艾丽丝给鲍勃一个安全加密的文件,然后请他计算出文件中数字列表的总和,如果没有解密钥匙,这样的任务似乎无法完成。加密文件就像锁着的手提箱一样难以渗透,鲍勃对此也可能无能为力。
 

艾丽丝想要在鲍勃提供“云服务”的计算机上处理机密资料,但她需要确保没有其他人能够了解到具体的数据资料,甚至包括鲍勃也不能看到。图中以不同的字体形式来表示加密与未加密数据(即密文与明文)

 

  不同的是,艾丽丝已经掌握了一种非同寻常的加密技术,她的要求鲍勃可以做到,即他可以计算这些见不到的数据资料。文件里的数字列表依然是加密的,虽然鲍勃无法获知里面的信息。然而,他可以运行计算机程序加密数据计算进行某些运算,比如说求和运算。输出的结果尽管也是加密的,鲍勃仍然无法解读,但他只要将输出结果反馈给艾丽丝即可,她的解密钥匙可以获取答案。
 
  令这一“魔术”成为可能的是一种称做“全同态加密”(fully homomorphic encryption,FHE)的新颖加密技术。严格地说,这一理论并不是新提出的,只是多年来一直被视为一种难以实现的理想而已。2009年,当时还是斯坦福大学研究生的克雷格·金特里(Craig Gentry)在密码学上有了一项新的突破,他发现,对加密数据进行处理得到一个加密的输出结果,解密后的结果与用同一计算方式处理未加密原始数据得到的输出结果是一样的――就好像不知道问题也能给出问题的答案一样。从那时开始,对这一理论的进一步完善和各种新的“同态加密”方案层出不穷。
 

将窃听者拒之在外

  在早期的合作过程中,艾丽丝和鲍勃互相之间没有秘密,他们探讨的主要问题是如何通过公共渠道进行隐秘的通信交流,而“好管闲事”的“第三者”――如暗中的窃听者――有可能正在偷听。为解决这个问题,艾丽丝和鲍勃设计了一系列密码方案,比如,在将某条信息发送给鲍勃之前,艾丽丝会用某种“密钥”将明文文本变成加密文本,即使窃听者截获了这条信息,没有密钥也毫无意义。而鲍勃手中有密钥,他可以将加密文件解密,将其恢复为明文文本。
 
  对于某些密码系统来说,艾丽丝和鲍勃分别持有一份相同的“钥匙”,包括加密和解密的“钥匙”。然而,他们还要面对一个如何安全传送密钥而不致落入偷窥者手中的棘手问题。一个特别聪明的解决方案称为“公钥加密”,即将“钥匙”分割为两部分,艾丽丝和鲍勃分别发布一个公开的加密密钥,任何人都可以利用这种密钥向他们发送加密信息,但解密密钥却是保密的,只有他们才能阅读收到的信息。
 
  另一项保护私人谈话隐秘性的是概率密码术。概率密码学理论是20世纪80年代初由麻省理工学院的密码学家沙菲·戈德瓦塞尔(Shafi Goldwasser)和西尔维奥·米卡利(Silvio Micali)提出的。早期的系统是确定性的:即相同的明文产生相同的密文。但是,这种确定性在公钥密码系统中是很危险的,窃听者可以尝试猜测信息内容,然后用公共密钥加密并查验,看是否与被截获的密文相符。概率加密方案可令一段明文信息拥有多种可能的编码,并由系统随机选择。即使你能猜中明文,但几乎没有任何机会与随机加密的密文匹配。
 
  这种加密技术已成为互联网程序的一部分,通常不为人们所关注。当你在网络上查阅银行帐户余额或在网上购物时,你依靠的是超文本传输协议,它在幕后为你提供了一层加密保护。即便谷歌搜索也是加密的,这些措施旨在传输过程中保护你的信息。加密通信挡住了网络上的窃听者和偷窥者,在你发送信息的时候,这些窃听者或偷窥者也许正坐在星巴克咖啡店里侵入你的无线连接中。另一方面,加密协议对信息的接收者是不保密的,他们手中有解密文件的密钥。通常来说,这没有什么问题,因为预期的收件人是值得信赖的一方。
 

明文空间和密码空间

  近些年来,艾丽丝和鲍勃已经分道扬镳。艾丽丝如今在一个加密软件公司任主管,鲍勃则从事云计算服务工作,他们之间通信的安全和隐私需求也相应有所改变。当艾丽丝与鲍勃交流时,除了需要防范偷听和偷窥之外,艾丽丝的公司有一些不适合透露的专有信息,令她的困境变得更加复杂――有时她还得利用鲍勃的服务器处理一些涉及机密的数据。
 
  普通的加密技术对于这种情况是没有任何帮助的。艾丽丝可以将信息加密后发送给鲍勃,除非他可以对这些信息解密但无法处理,而信息被破译正是艾丽丝力求避免的。为此他们陷入了僵局,而同态加密的目的就是为了破解这样的僵局。
 
  在解释同态加密原理之前,有必要解释一下同态(homomorphic)这个词。这一希腊语词根意指相同的形状或相同的形式,其内涵是转换形式前后的两组对象,但它们却有殊途同归的效果。这一概念来自抽象代数的深奥世界,可以列举一个简单的例子,两组对象分别为正实数和对数,实数的相乘运算和对数的相加运算就属于同态运算。也就是说,对于任何正实数x,y和z来说,如果xy = z,那么log(x)+log(y)=log(z)。正是这种同态性提供了以不同方式达到相同目的的两种选择,如果给出x和y,我们可以直接将它们相乘,也可以取它们的对数相加,最后得到的结果是相同的,都是z。
 
  同态加密技术提供了类似的双途径,我们可以直接明文输入x和y,我们也可以加密输入x和y,对密文数值进行一系列操作,最后解密得到与明文相同的最终答案。这两个途径通过两个平行的宇宙:明文空间和密码空间。
 
  明文空间的算法为人们所熟悉,以字节序列(0和1)可以很方便地表示某个数字,并根据逻辑和算法对字节进行运算处理。在众多操作中,计算机真正需要做的就是加与乘,其他计算都是以这两种基础运算为基础的。
 
  而对密文进行运算却要奇怪得多,事实上,完成这个任务几乎是不可能的。加密过程彻底打乱了代表数字的所有字节,而数学运算是一个精确的过程,只有当所有的字节都在正确位置上时,才能得出正确的结果。然而,并非没有办法。
 
  为了证明这一概念,可提供一个非常简单的同态加密例子。假设明文是由整数组成的,加密一个数字,乘以2,解密时除以2。根据这个方案,我们可以用相加来加密数据,也可以稍作改变的相乘加密方案,假如明文输入为x和y,我们可以对它们分别加密,将密文相加,然后解密得到结果。这种迂回计算方法同样能够得出正确的答案,因为2X +2 Y = 2(X + Y)。
 

随机产生的“数字噪声”是保证数据安全的同态密码系统运行的一个主要障碍。加密后的数据可以想象为一些网格点(深色的点),与原数据设定的网格点(浅色的点)的位置有些较小幅度的随机位移。解密时,每一个深色点都被吸引到最近的浅色点周围。同态加密操作加大了随机位移的幅度,即“数字噪声”,如果这种噪声水平超过阈值,一些点就会被吸引到错误的网格点,从而导致解密出错(箭头表示)

 

  为了得到正确的相乘结果,我们必须将密文的乘积定义为(XY)/ 2,而明文则按常用公式XY相乘。根据这条规则,很容易验证加密―相乘―解密三个步骤产生的结果与明文相乘所得到的结果是相同的。
 
  这个加密系统的例子很简单,并且是完全同态的。我们可以对密文做所有的算术运算,但如果你真想保密的话,不建议使用该系统。因为一个数字乘以2并不会彻底打乱字节,而只是向左移动一位而已。
 
  设计一个安全的全同态加密方案显然不会这么简单,而要令这种加密系统达到实际应用的效率,是另一个挑战,目前仍是密码学家努力攻克的难关。
 

同态加密的“数字噪声”

  对加密数据进行计算的想法,最早是1978年由麻省理工学院的罗恩·李维斯特(Ron Rivest)、莱恩·阿德尔曼(Len Adleman)和迈克尔·德图佐斯(Michael L. Dertouzos)提出的,在此之前的几个月,李维斯特和阿德尔曼以及阿迪·沙米尔(Adi Shamir)推出了以他们姓氏首字母命名的最早的公钥密码体系RSA。
 
  RSA的方案只是部分同态:它允许密文相乘但不相加。李维斯特、阿德尔曼和德图佐斯指出这一点的同时,还提到实现部分“加密同态”的其他一些途径,并探讨了实现可对密文进行常规计算的安全方案的可能性。
 
  在接下来的30年里,断断续续取得了一些进展。2005年,丹·勃尼(Dan Boneh)和科比·尼西姆(Kobbi Nissim)等人设计了一个可允许对密文进行无限次数相加运算,然后进行一次性相乘运算的同态加密系统(勃尼是金特里的论文指导老师),直至2009年金特里宣布的完全同态加密方案。
 
  金特里创建的加密和解密功能的同态系统,可以将明文转换为密文,然后再恢复到原来的明文。他同时还设立了一个评价函数,用来接受密文计算的描述。这种计算不再是一种序列程序,而是一种电路或电路网络:输入的信号通过一层一层的逻辑门。这样的电路通常是由布尔数学体系的各个“门”构成的(“与”门、“或”门和“非”门等),但它们也可以规定为相加和相乘的步骤。
 
  评价函数相当于嵌入密码系统中的一个完整的计算机,原则上它可以计算出任何可计算的函数,前提是代表函数的电路允许延伸到任意深度(电路的深度是指从输入到输出最长路径上门的数量)。一个全速运转的计算机必须能够处理任意深度的电路,同态系统在这里却遇到了一个障碍,密文数据被“数字噪声”污染。
 
  “数字噪声”源自于概率加密过程。我们将每个密文值假设为空间中的一个点,概率加密给每个点坐标注入一点点的随机性,使得它在确定性密码系统中所占据的位置稍有偏移。解密时按照这样稍有偏移的规律,通过对每个点进行处理来过滤掉“数字噪声”。而在同态计算中,这样的“数字噪声”被“增强”了,每个点偏离它的正确位置更远,直到最后解密时出错,将它与一个不正确的明文值联系在一起。
 
  大致来说,每一次同态相加都会令数字“噪声”翻倍,而每次同态相乘都会令“数字噪声”自乘。所以,这种操作的次数必须加以限制,否则误差就会累积起来。由于电路深度的限制,这种密码系统不能称之为完全同态,只能算是“准同态。”
 
  以下方式可以避免深度限制的问题:每当“数字噪声”开始接近临界阈值时,对数据进行解密,然后重新加密,从而复位到原来的低“噪声”水平。麻烦的是,解密需要密钥,而FHE密码体制的关键之点就是不提供密钥,而是对加密文本进行计算。
 
  事情至此变得古怪而美妙起来,只要不超过电路深度的噪声限制,密码系统内置的评估函数可完成任何计算。因此,我们可以要求评估函数运行解密功能,并将其设定为对加密数据起作用,在这种情况下,提供给它的密钥是正常密钥的加密版本。具体地说,所提供的在评估函数内运行的密钥是对密钥明文加密产生的密文。以此密钥解密的结果并非明文,而是重新加密后降低了“数字噪声”的新的密文。
 

探索更多的完善方案

  艾丽丝给了鲍勃用来解锁数据所需密钥的副本,关键是,密钥被放置在“锁”着的箱子内,也只能在那个锁着的箱子里使用。事实上,用来锁箱子的密钥就在被锁住的箱子里(金特里将这种令人眼花缭乱的密码术形容为:艾丽丝在锁着的箱子中加工珠宝)。
 
  根据需要,可以暂停运算重新加密,以此来“刷新”噪声过多的密文,以这种方式,计算机可以处理任何深度有限的电路,“准同态”系统也将变成完全同态系统,可以对加密数据进行任意复杂的计算。
 
  这个方案的一个基本的假设是,解密电路本身较浅,以在不超过噪声阈值的情况下运行。事实上,它的深度需要比限度略浅,否则电脑会不断刷新数据,永远无法完成任何有用的工作。当金特里最初形成他的FHE方案时,他发现评价函数在运行解密步骤时总是会积累起过多的“数字噪声”,补救的办法是“挤压”解密,其代价是密钥更大更复杂,但暂停以刷新的创新思路,使问题得到了解决。
 
  2009年,金特里的博士论文描述了他的FHE系统。其后的三年,数十种更详尽的替代方案相继出台,其中至少有三个方案进行了计算机程序实现同态加密的尝试。
 
  2010年,麻省理工学院的马蒂恩·范迪克(Marten van Dijk )、金特里、IBM(美国商用机器公司)的谢伊·哈勒维(Shai Halevi)和多伦多大学的维诺德·韦昆塔纳(Vinod Vaikuntanathan)发明了另一种形式的同态加密,他们的加密方式来自数论,大约相当于最大公约数(GCD),而准确的GCD是很容易计算的,但其“噪声”版本却似乎很难破解。如果两个较大数字的GCD为 p,通过加减一个很小的随机数字改变原来的数字,是很难再求出p的。在密码系统中,这个p就是密钥。
 
  斯坦福大学的兹维卡·布雷克斯基(Zvika Brakerski)和韦昆塔纳推出的第三种FHE系统的基础是“学习纠错法”,这个加密解密系统的任务是解一组联立方程组,其中每个方程式都有小概率出错的可能。就像GCD方案一样,准确的GCD没有出错的可能,是一个易解的数学问题,但要寻找正确等式的子集却很难。
 
  最近,布雷克斯基、韦昆塔纳和金特里已开发出“学习纠错法”的新版本系统,这个系统采用了不同的方法进行“数字噪声”管理。不是相隔一定时间暂停计算对数据重新加密,而是在每一个计算步骤之后调整系统参数,以防止噪声水平接近极限。
 

在密码空间里运算

  在密码空间里进行计算是一种非常新颖的理论,但它是否能够可以成为一种实用的技术呢?FHE在计算效率和管理成本方面比其他类型的加密技术更具挑战性。加密的目的是要创造一个安全的通信信道,对通信两端的计算效率不应产生直接的影响。而同态加密有所不同的是,密码系统成为了计算平台,任何效率的降低都会影响整个过程。
 
  减轻这些影响是目前的研究方向。例如,不是单独加密每个明文字节,多个字节可“打包”在一起,然后“分期清偿”以降低“管理开销”。
 
  实用性的最终检验标准是创建一个可实施的方案。布里斯托大学的奈杰尔·P.·斯玛特(Nigel P. Smart)和鲁汶天主教大学的弗雷德里克·维科特兰(Frederik Vercauteren)是最早进行这方面尝试的。他们建立了一个准同态系统,但目前无法扩展为全同态系统,瓶颈就是产生庞大加密密钥的繁冗过程。
 
  金特里和哈勒维研究的是与基于网格的算法略有不同的方案,并运行了整个系统。但他们并不需要像最初所打算的那样,将这个系统建立在IBM的蓝色基因(Blue Gene)超级计算机上,因为桌面型电脑工作站足以完成这个任务。尽管如此,产生激增至2.3千兆字节的公钥用了两个小时,噪声消减重新加密花了30分钟。
 

克雷格·金特里于2009年发明了一种数字噪声消减机制。金特里发现,如果将嘈杂的密文解密后重新加密进行“刷新”可降低噪声。但是同态加密系统并不提供解密需要的密钥。解决方案是通过解密运算运行密文,但用的是加密版本的解密密钥。结果获得一个新的密文,噪声问题得以解决,安全性仍与原来的密文一样(图中刷新后的密文以另一种字母表示)

 

  在另一项完善方案中,微软研究所的克里斯汀·劳特(Kristin Lauter)和埃因霍芬理工大学的迈克尔·内赫里格(Michael Naehrig)的研究表明,如果能牺牲一些全同态的要求,获得较高的效率提升是可能的。他们不能允诺评估电路无限制的深度,而只是将希望放在一些较小固定数字的相乘以及不加限制的相加之上。他们的工作代码也是基于“学习纠错”的范例,所不同的是拥有最高的安全级别――密钥大小约有一兆字节,同态相加只需几毫秒时间,相乘一般不到一秒钟。与之前的一些研究成果相比,在运算时间上取得了巨大的进步,但我们仍然需要清醒地看到,与1946年电子数字积分计算机(ENIAC)的性能相比,仍是慢了一个数量级。
 

同态加密的实际应用

  劳特、内赫里格和韦昆塔纳对同态计算可能的应用前景进行了探讨,确保网上医疗记录隐私就是实际应用的一个例子――患者通过与医生共享某个密钥,医生可以查看选定的病史记录。
 
  华尔街是同态加密服务的另一个潜在客户,对于通过分析计算决定投资意向的投资管理和股票交易专家们来说,重要的不仅是数据,还有算法――FHE可通过同一机制来保证数据和算法的安全。
 
  第三种应用是在网络广告商和消费者之间建立一个隐私加密“栅栏”。广告商急切想要联系上有特殊兴趣或购物习惯的个人,收集人们在互联网上和其他地方的动向。基于同态加密的广告服务,既能让广告商寻找到目标消费者,同时又确保广告商不会侵犯到目标消费者的个人隐私。
 
  韦昆塔纳建议最先投入应用的是垃圾邮件过滤。假如你发布了公用密钥,并邀请记者向你发送加密电子邮件,垃圾邮件发送者也可以利用公开的密钥加密广告和其他垃圾邮件,来填塞我们的邮箱。除非你愿意分享你的解密密钥,垃圾邮件过滤服务不能读取也不能拒绝加密的垃圾邮件,而同态加密就可以解决这个问题。
 
  另外还有一项实际应用是一种称为同态信托投资公司的银行,在线界面看上去可能与任何其他网上银行没什么不同,都拥有防止入侵者的通常的加密保障措施。但是与普通网上银行不同的是,甚至这家银行的负责人和工作人员也无法知道你交易的细节。
 
  艾丽丝对这样的银行可能很感兴趣,这就好像不需要打开被锁着的手提箱,也有办法数清里面的现金究竟有多少一样。
 
 

资料来源 American Scientist

责任编辑 则 鸣