同态加密——云计算时代的信息安全.docx

同态加密——云计算时代的信息安全
意义与价值

基本概念
A way to delegate processing of your data, without giving away access to it.（Craig Gentry）即一种不需要访问数据本身就可以加工数据的方法

对比普通加密方式的好处
一般的加密方案关注的都是数据存储安全，即如果需要发送或存储一段数据，那么需要先对这段数据进行加密，然后将加密后的结果发送或者存储，没有密钥的用户，就不能从加密结果中获取原始信息，只有拥有密钥的用户才可以对加密结构进行解密，从而获得原始数据。但是在这个过程中，我们只能对加密数据进行传输和存储，而不能对加密数据本身进行任何操作，否则都会造成加密数据无法解密。

同态加密与一般加密方案的不同就在于，其注重的是数据处理时的安全。同态加密提供了一种对加密数据进行处理的功能。也就是说，其他人可以对加密数据进行处理，但是处理过程不会泄露任何原始内容。同时，拥有密钥的用户对处理过的数据进行解密后，得到的正好是处理后的结果。

概况描述

什么是同态加密？
同态加密是基于数学难题的计算复杂性理论的密码学技术。对经过同态加密的数据进行处理得到一个输出，将这一输出进行解密，其结果与用同一方法处理未加密的原始数据得到的输出结果是一样的。

如何理解同态加密
为了便于理解，我们举一个例子。Alice是一家珠宝店的店主，她打算让员工将一整块黄金加工成首饰，但是却担心工人在加工的过程中偷取黄金。于是她制造了一个有锁的箱子（手套箱）用于存放黄金以及做好的首饰，而钥匙由她随身保管。通过手套箱，工人可以将手深入箱子来加工首饰。但是箱子是锁着的，所以工人无法拿到黄金和加工好的首饰。而Alice则可以通过钥匙向手套箱添加原料，并取出加工好的首饰。

下图是个手套箱示例图。

这个故事和同态加密的对应关系如下：
Ø Alice：最终用户
Ø 黄金：原始数据
Ø 手套箱：加密算法
Ø 钥匙和锁：用户密钥
Ø 通过钥匙向手套箱中添加原料：将数据用同态加密方案进行加密
Ø 员工加工首饰：应用同态特性，在无法取得数据的条件下直接对加密结果进行计算处理
Ø 取出加工好的首饰：对结果进行解密，直接得到处理后的结果

同态加密的具体过程
我们以云应用为背景进行介绍：
用户通过云来处理数据的过程大概如下图所示：

Ø 用户对Data1和Data2进行加密，将加密后的数据CD1和CD2发送到云端
Ø 用户向云端提交数据处理方法f()
Ø 云端使用方法f()对密文数据CD1和CD2进行处理
Ø 云端将处理后的结果发送给用户
Ø 用户对数据进行解密，得到相应原始数据处理后的结果

因此，在同态加密过程中我们具体需要一下几个主要方法
1. GenerateKey方法：用来生成密钥
2. Encrypt方法：用来进行同态加密
3. Evaluate方法：在用户给定的数据处理方法f()下，对密文进行操作
4. Decrypt方法：用来解密密文

同态加密基本原理
设R和S为整数集，用R表示明文空间，用S表示密文空间。a,b∈R,E是R→S上的加密函数。如果存在算法PLUS和MULT，使其满足：
E(a+b)=PLUS(E(a),E(b))
E(a×b)=MULT(E(a),E(b))
这样我们就可以利用E(a)和E(b)的值计算出E(a+b)和E(a×b),而不需要知道a和b的值。我们称其分别满足加法同态和乘法同态。
加密算法：令E(x)=(x+r*p)mod(p*q),这里p和q是两个大的质数，r是一个随机数。
解密算法：x=E-1(y)=y mod p,这里y=E(x)。
例如：x1=2，x2=3，令p=11,q=7,n=p*q=77
则有：E(x1)=(2+10*11)mod77=35
E(x2)=(3+25*11)mod77=47
E(x1+x2)=E(x1)+E(x2)=82
E(x1*x2)=E(x1)*E(x2)=1645
解密：y1=82 mod 11 = 5,y2=1645 mod 11 = 6
同态加密的应用
同态加密技术在分布式计算环境下的密文数据计算方面具有比较广泛的应用领域，比如云计算、多方保密计算 、匿名投票等

l 安全云计算与委托计算。
同态技术在该方面的应用可以使得我们在云环境下，充分利用云服务器的计算能力，实现对明文信息的运算，而不会有损私有数据的私密性。例如医疗机构通常拥有比较弱的数据处理能力，而需要第三方来实现数据处理分析以达到更好的医疗效果或者科研水平，这样他们就需要委托有较强数据处理能力的第三方实现数据处理（云计算中心），但是医院负有保护患者隐私的义务，不能直接将数据交给第三方。在同态加密技术的支持下，医疗机构就可以将加密后的数据发送至第三方，待第三方处理完成后便可返回给医疗结构。整个数据处理过程、数据内容对第三方是完全透明的。

l 文件存储与密文检索。
用户可以将自己的数据加密后存储在一个不信任的远程服务器上，日后可以向远程服务器查询自己所需要的信息，存储与查询都使用密文数据，服务器将检索到的密文数据发回。用户可以解密得到自己需要的信息，而远程服务器却对存储和检索的信息一无所知。此种方法同样适用于搜索引擎的数据检索。

l 安全多方计算协议设计的工具。
所谓安全多方计算就是分别持有私有数据 x1,x2,…,xn 的 n 个人，在分 布 式 环 境 中 协 同 计 算 函 数f (x1,x2,…,xn) 而不泄露各方的私有数据。以同态技术加密的密文数据计算不仅可以满足安全多方计算协议设计中保护各方隐私的需要，还能避开不经意传输协议而大大提升协议效率。

l 电子选举。
基于同态加密技术设计的电子选举方案，统计方可以在不知道投票者投票内容的前提下，对投票结果进行统计，既保证了投票者的隐私安全，有能够保证投票结果的公证。

随着分布式计算的普及，如何保护分布式计算环境下的用户隐私已经成为一个重要问题，同态加密技术可以为分布式计算环境的用户隐私保护提供强有力的技术支撑。