同态加密背景及其应用

全同态加密技术的研究与应用在当今数字化的时代，信息安全成为了至关重要的问题。

随着云计算、大数据等技术的迅速发展，数据的处理和存储越来越多地依赖于第三方平台。

然而，在将数据交给第三方时，如何保证数据的机密性和隐私性成为了一个巨大的挑战。

全同态加密技术的出现，为解决这一问题提供了一种有效的途径。

全同态加密是一种特殊的加密形式，它允许在密文上进行任意的计算操作，而无需对数据进行解密，最终得到的结果与在明文上进行相同计算操作得到的结果一致。

这一特性使得数据在加密状态下仍然能够被处理和分析，极大地保护了数据的隐私。

全同态加密技术的发展历程并非一帆风顺。

早期的研究主要集中在理论层面，由于计算复杂度高、效率低下等问题，实际应用受到了很大的限制。

但随着密码学和计算机技术的不断进步，全同态加密技术逐渐取得了重要的突破。

从原理上讲，全同态加密通常基于数学难题，如整数分解、离散对数等。

通过复杂的数学运算和密钥管理，实现对数据的加密和解密。

在加密过程中，明文被转换为看似随机的密文，而解密则是通过特定的密钥将密文还原为明文。

在实际应用方面，全同态加密技术具有广泛的前景。

首先，在云计算领域，用户可以将敏感数据加密后上传至云端，云服务提供商能够在不获取明文的情况下对数据进行处理和分析，例如进行数据挖掘、机器学习等任务。

这既保护了用户的数据隐私，又充分利用了云计算的强大计算能力。

其次，在医疗健康领域，患者的医疗记录往往包含大量的个人隐私信息。

通过全同态加密技术，医疗机构可以在加密状态下对医疗数据进行统计分析，为疾病研究和医疗决策提供支持，同时避免患者隐私的泄露。

再者，金融行业对数据的安全性要求极高。

全同态加密可以用于加密交易数据、客户信息等，使得金融机构在进行风险评估、市场分析等操作时，无需担心数据被窃取或篡改。

然而，全同态加密技术目前还面临一些挑战。

一方面，其计算效率仍然有待提高。

复杂的加密和解密过程需要消耗大量的计算资源和时间，这在一定程度上限制了其在大规模数据处理中的应用。

同态学习的加密算法介绍在当今信息时代，数据安全成为了一个越来越重要的问题。

随着云计算、大数据等新兴技术的发展，我们需要一种更加高效、安全的方式来处理数据。

同态加密算法作为一种新型的加密技术，正在逐渐受到人们的重视。

本文将介绍同态学习的加密算法，包括其基本概念、应用场景以及发展前景。

一、基本概念同态加密是指对加密数据进行计算，得到的结果可以在解密后和在未加密前的数据相同。

简单来说，就是能够在加密状态下进行一些特定的运算，然后得到加密后的结果，再进行解密后得到正确的结果。

这种加密技术可以在不暴露数据的情况下进行计算，增强了数据的安全性。

同态加密算法包括完全同态加密（Fully Homomorphic Encryption, FHE）和部分同态加密（Partially Homomorphic Encryption, PHE）两种类型。

FHE可以进行任意多次的加法和乘法操作，而PHE只能进行一种运算（加法或者乘法）。

二、应用场景同态加密算法在实际应用中有着广泛的应用场景。

首先，它可以应用于云计算领域。

在云计算中，用户可以将数据加密后上传到云服务器上进行计算，然后再将结果解密得到正确的结果。

这样可以保护用户的隐私数据，同时又能够享受云计算带来的便利。

其次，同态加密算法也可以用于安全计算。

比如，在医疗健康领域，医院可以对患者的健康数据进行同态加密后上传到云服务器上进行分析，而不必担心数据泄露问题。

此外，金融领域、物联网领域等都可以应用同态加密算法来保护数据的安全性。

三、发展前景同态加密算法的出现为数据安全提供了全新的解决方案，其发展前景十分广阔。

目前，同态加密算法还存在一些问题，比如性能低下、运算速度慢等，但随着技术的不断进步，这些问题有望得到解决。

未来，同态加密算法有望在各个领域得到更加广泛的应用。

总的来说，同态加密算法是一种非常有潜力的加密技术，可以保护用户的隐私数据，同时又能够在加密状态下进行计算。

它在云计算、安全计算等领域有着广泛的应用前景，将为数据安全带来全新的解决方案。

同态加密——云计算时代的信息安全意义与价值基本概念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表示密文空间。

同态加密技术及其应用同态化（Homomorphic）是指从一种形态转变到另一种形态，同时在第二种形态中保留与第一种形态相关联的元素。

同态加密技术比较公认的是可以在云计算环境下，为了保护用户隐私及数据安全，需要先对数据加密，再把加密后的数据放在云服务端。

使用全同态加密，可以在不暴露明文数据的情况下，由数据使用者对密文数据进行计算，而数据拥有者可以解密得到明文结果，该结果同样是对明文做此运算而得到的结果。

标签：同态加密技术应用数据同态加密是一种加密形式，它允许人们对密文进行特定的代数运算得到仍然是加密的结果，与对明文进行同样的运算，再将结果加密一样。

通俗的讲，这项技术令人们可以在加密的数据中进行诸如检索、比较等操作，得出正确的结果，而在整个处理过程中无需对数据进行解密。

以往加密手段的弊端在于它通常是将数据保存在盒子内而不让外界使用或者分析数据，只有使用解密密钥将盒子打开，才能对数据进行分析和计算。

在同态加密环境下，敏感数据一直处于加密状态，而应用系统无需解密可以用加密的数据按照正常的业务逻辑处理业务，这样公司将敏感的信息储存在远程服务器里，既避免从当地的主机端发生泄密，又保证了信息的使用和搜索，解决了云计算发展面临的客户对数据云端存储安全担忧的难题。

一、同态加密原理同态加密技术，就是将数据加密成难以破译的数字字符串，能对这些加密后的字符串进行数学处理，然后解密结果。

如果用数学方法表述，假设加密操作为E，明文为m，加密得e，即e = E（m），m = E’（e）。

已知针对明文有操作f，针对 E 可构造F，使得F（e）= E（f（m）），这样 E 就是一个针对 f 的同态加密算法。

我们举一个简单的例子，看看同态加密是如何处理2+3这样的问题：假设数据已经在本地被加密了，2加密后变为22，3加密后变为33。

加密后的数据被发送到服务器，在进行相加运算。

然后服务器将加密后的结果55发送回来。

然后本地解密为5。

同态加密在云计算安全中的应用一、引言随着云计算应用的不断普及和数据处理的不断增大，数据安全问题也变得愈发重要。

传统的加密方式，如对称加密和非对称加密，在保障数据安全性方面存在不少缺陷，如密钥管理难、数据完整性未得到保证等问题。

近年来，同态加密技术的出现为云计算的数据安全性问题提供了一种新的解决方案。

本文将介绍同态加密的概念、原理及其在云计算安全中的应用。

二、同态加密的概念和原理1. 同态加密的概念同态加密是一种特殊的加密算法。

它可以在密文状态下执行运算，并且得出的结果仍然是密文。

因此，同态加密能够保护隐私数据，使云服务器在不知晓数据内容的情况下对其进行加工，并返回运算结果。

这种技术有助于维护云环境中的数据隐私，因此是一种非常有前途的加密方法。

2. 同态加密的原理同态加密中的加密函数具有以下两个性质：- 加密函数是针对明文运算的，即运用函数后结果与明文相同- 加密函数支持同态性，指的是进行某种形式的密文操作后，得到的结果是等效的。

具有这些性质的加密算法被称为全同态加密算法。

由于全同态加密算法计算复杂度高，发展尚未完全成熟。

因此，还有一种部分同态加密算法，只支持加法或乘法计算。

三、同态加密在云计算安全中的应用1. 隐私保护同态加密可在云计算环境中保护用户数据的隐私，这是其最显著的优势之一。

用户可以以密文的方式将数据上传到云中，服务提供方不会知道这些数据的内容，还可以在不知道这些数据内容的情况下对其进行运算，然后将结果返回给用户。

这使得云计算环境中的数据更加安全，同时保护了用户的隐私。

2. 数据可搜索同态加密技术使得在云计算环境中进行数据检索成为可能，而且保护了用户的敏感信息不被泄漏。

该技术可以让用户通过云提供商的服务器查找自己的信息，而服务器不会获得这些信息，还允许服务器增加额外的计算，以满足其操作需求。

3. 访问控制在云计算环境中，企业需要确保数据只能被授权的用户访问。

同态加密技术可以实现这一点，因为用户上传的数据始终以密文形式存储。

同态学习的加密算法介绍同态加密是一种特殊的加密技术，允许对加密数据进行计算，而无需先解密数据。

这种技术对于保护隐私和数据安全非常重要，因为它允许在加密的数据上进行计算，而不会泄露数据内容。

在本文中，我们将介绍同态学习的加密算法及其应用。

1. 同态加密的基本概念同态加密是一种特殊的加密技术，它允许在加密状态下对数据进行计算。

这意味着即使在加密状态下，也可以对数据进行加法、乘法等运算，并在解密后获得正确的结果。

这种特性使得同态加密在保护数据隐私和安全方面具有重要意义。

2. 同态加密的分类同态加密可以分为完全同态加密（Fully Homomorphic Encryption，FHE）和部分同态加密（Partially Homomorphic Encryption，PHE）两种类型。

完全同态加密允许对加密数据进行任意次数的加法和乘法运算，而部分同态加密只允许进行一种运算（通常是加法或乘法）。

3. 同态加密的应用同态加密在隐私保护和数据安全方面具有广泛的应用。

例如，在云计算中，用户可以使用同态加密将数据上传到云端，而无需担心数据被篡改或泄露。

在医疗保健领域，同态加密可以用于保护患者的隐私数据，同时允许医生对加密数据进行分析和计算。

此外，同态加密还可以应用于金融领域、物联网等各个领域。

4. 同态加密的算法目前，有许多同态加密算法被提出，其中最著名的是RSA同态加密算法、Paillier同态加密算法和Gentry同态加密算法。

这些算法各自有其特点和适用场景，可以根据具体的需求选择合适的算法。

RSA同态加密算法是一种非对称加密算法，基于大整数分解难题。

该算法具有较高的安全性，但在进行加法和乘法运算时性能较差。

Paillier同态加密算法是基于RSA算法的改进，具有更好的性能和安全性。

Gentry同态加密算法是第一个实现了完全同态加密的算法，但由于其性能较差，目前尚未在实际应用中得到广泛采用。

5. 同态加密的挑战和未来发展尽管同态加密具有重要的应用价值，但目前仍然面临着一些挑战。

同态加密技术在密码学中的应用在现代信息社会中，保护个人隐私和保护敏感数据的安全性成为了重要的问题。

密码学作为一门研究如何保障信息安全的学科，同态加密技术作为其中一个重要的分支，在实际应用中发挥着重要的作用。

本文将探讨同态加密技术在密码学领域的应用，并介绍其原理及优势。

一、同态加密技术简介同态加密技术是一种特殊的加密机制，其具备一定的运算性质，可以在加密状态下进行计算，同时保持密文的可操作性。

通常的加密算法在密文状态下是不可操作的，需要解密密文后才能进行计算。

而同态加密技术可以在密文状态下进行加法和乘法等基本运算，而不需要解密密文。

这种特殊属性使得同态加密技术在许多领域具备广泛的应用前景。

二、同态加密技术的应用1. 数据隐私保护同态加密技术可以应用于个人隐私数据的保护上。

在云计算和大数据环境下，个人的敏感数据往往需要存储在云端或者其他数据中心中。

而同态加密技术可以保证个人数据在云端进行相关计算时的安全性，避免了用户数据泄露的风险。

2. 安全计算外包同态加密技术可以应用于安全计算外包场景。

在云计算中，用户可以将部分计算任务外包给云服务提供商进行计算，以降低自身计算压力。

然而，用户的数据在云端进行计算时面临着安全性的问题。

通过使用同态加密技术，用户可以将数据加密后传输给云服务提供商，并在密文状态下进行计算，最终获得加密结果。

这样可以保证用户数据的隐私性和安全性。

3. 数据共享与联合计算同态加密技术在数据共享和联合计算场景中也发挥着重要作用。

在一些跨机构合作的场景中，各方需要共享敏感数据进行计算，但又不希望泄露自身的数据。

同态加密技术可以实现在密文状态下进行计算和数据共享，保证了数据的隐私性和合作计算的可行性。

三、同态加密技术的优势同态加密技术相较于传统的加密算法具备许多优势。

首先，同态加密技术可以在不解密的情况下对密文进行计算，保证了计算过程中数据的安全性。

其次，同态加密技术可以在多方进行的计算中保持数据的隐私性，避免了数据泄露问题。

同态加密的发展及应用同态加密是一种重要的加密技术，其可以在不解密的情况下对加密数据进行计算，从而保护数据的隐私性。

本文将从同态加密的发展历程和应用方面进行探讨。

同态加密的发展历程可以追溯到20世纪70年代。

最初，同态加密被用于验证密码学理论，但由于其计算量巨大且实用性较低，其应用一直局限于学术研究中。

然而，随着计算机处理能力和算法的发展，同态加密逐渐成为加密领域的研究热点。

在同态加密的发展过程中，提出了多种类型的同态加密方案。

最早提出的是完全同态加密(Fully Homomorphic Encryption，FHE)方案，其能对加密数据进行任意复杂的计算。

然而，FHE方案的计算代价非常高，难以在实际应用中得到广泛应用。

后来，部分同态加密方案(Partially Homomorphic Encryption，PHE)被提出，其可以进行特定类型的计算，如加法或乘法运算。

PHE方案的优势在于计算复杂度相对较低，适用于一些特定的应用场景。

随着同态加密技术的进一步发展，其应用也得到了广泛拓展。

同态加密在云计算、多方计算、数据隐私保护等领域具有重要意义。

首先，同态加密技术在云计算中发挥着重要作用。

由于云计算服务提供商可以访问用户的敏感数据，数据隐私成为云计算的一个关键问题。

同态加密技术可以在不暴露用户数据的情况下进行计算，从而保护数据隐私。

例如，在云计算中可以使用同态加密对用户的数据进行加密，然后将加密后的数据上传到云端进行计算，最后将结果返回给用户。

在此过程中，云服务提供商无法解密用户的数据，保证了用户数据的隐私性。

其次，同态加密在多方计算中也具有重要应用。

在多方计算中，多个参与方通过共享计算任务的结果，但又希望保护各自的输入数据。

同态加密技术可以在保护数据隐私的同时进行计算，从而实现多方计算的功能。

例如，在医疗领域中，不同医院可以通过同态加密技术共享患者的数据，进行疾病诊断和治疗方案的制定，而无需暴露患者的个人隐私信息。

全同态加密研究动态及其应用概述刘明洁;王安【摘要】随着互联网的发展,尤其是云计算概念的诞生,人们在加密数据搜索与处理等方面的需求日益增加,使得全同态加密变得愈加重要.全同态加密的思想是20世纪70年代Rivest等人首次提出的,如何构造满足全同态性质的体制一直是困扰密码学家的难题,直到2009年Gentry基于理想格提出了第1个全同态加密体制使得该方面的研究取得突破性进展.随后许多密码学家在全同态加密方案的研究上作出了有意义的工作,促进了全同态加密向实用化的发展.对全同态加密的研究动态进行了概要的介绍,包括Gentry提出的第1个全同态加密方案及其优化;基于整数的全同态加密方案;基于LWE问题的全同态加密方案等.随后探讨了全同态加密的一般性应用框架,并以云计算、电子投票、数字水印3个应用为例,介绍了全同态加密的重要应用价值.【期刊名称】《计算机研究与发展》【年(卷),期】2014(051)012【总页数】11页(P2593-2603)【关键词】密码学;公钥密码学;全同态加密;云计算;信息安全【作者】刘明洁;王安【作者单位】北京大学北京国际数学研究中心北京 100871;清华大学微电子学研究所北京 100084【正文语种】中文【中图分类】TP309.71 全同态加密的研究现状利用同态加密来保护数据的私密性，这个概念最早由Rivest等人［1］于1978年提出．该想法的来源是通过加密函数的同态性质，实现对加密后的数据作运算的同时保护数据的私密性．这个概念被提出之后，密码学家设计出了很多具有同态性质的加密方案，如实现电子投票的体制［2－4］、保密信息检索协议［5－6］等．近几年，云计算受到广泛关注，而它在实现中遇到的问题之一即是如何保证数据的私密性，全同态加密可以在一定程度上解决这个技术难题．具体地说同态加密指这样一种加密函数，对明文进行环上的加法和乘法运算再加密，与加密后对密文进行相应的运算，结果是等价的．由于这个良好的性质，人们可以委托不信任的第三方对数据进行处理，而不泄露信息．因此，同态加密在云计算、电子政务等方面有重要应用．具有同态性质的加密函数是指2个明文a，b满足Dec（En（a）⊗En（b））＝a⊕b的加密函数，其中En是加密运算，Dec是解密运算，⊕，⊗分别对应明文和密文域上的运算．当⊕代表加法时，称该加密为加同态加密．密码学家设计出很多具有加同态性质的加密体制包括文献［3，7－10］．当⊗代表乘法时，称该加密为乘同态加密［11］．2005年在理论密码学会议（TCC）上，Boneh等人［12］给出了第1个可以同时实现加法和乘法同态的密码体制，该体制可以允许进行任意次的加法运算和一次乘法运算仍然保持同态．全同态加密指同时满足加同态和乘同态性质，可以进行任意多次加和乘运算的加密函数．用数学公式来表达，即或者写成：如果f是任意函数，称为全同态加密．直到2009年，IBM的研究人员Gentry ［13］第1次设计出一个真正的全同态加密体制，即可以在不解密的条件下对加密数据进行任何可以在明文上进行的运算．使得对加密信息仍能进行深入和无限的分析，而不会影响其保密性．经过这一突破，存储他人机密电子数据的电脑销售商就能受用户委托来充分分析数据，不用频繁与用户交互，也不必看到任何隐私数据．同态加密技术将允许公司将敏感的信息储存在远程服务器里，既避免从当地的主机端发生泄密，又依然保证了信息的使用和搜索．用户也得以使用搜索引擎进行查询并获取结果，而不用担心搜索引擎会留下自己的查询记录．Gentry［13］的同态加密体制是基于理想格设计的，我们将在下面的章节中对该体制作详细的介绍．其主要思想是先构造了一个部分同态加密的体制，该体制仅能保证对明文进行较低次数的多项式运算时的同态性，然后利用Squash技术降低解密函数的多项式次数，实现Bootstrapping，通过在不知道密钥的情况下更新密文，从而减少扰动，实现全同态加密．但该体制在期望的安全强度上远达不到实用的程度．随后很多密码学家在全同态加密体制的研究方面取得进展．2010年Dijk等人［14］利用Gentry的技术提出了基于整数的全同态加密体制．该体制比Gentry 的体制更简洁，但仍不实用．2010年Smart等人［15］在PKC上简化了Gentry09体制的实现，但仍然无法实现Bootstrapping的步骤．2011年Gentry等人［16］利用一些技术对Gentry09体制的实现作进一步的简化，包括提出了部分同态加密方案的新的密钥生成算法，不需要对整个多项式求逆的优化实现方法、时间空间部分平衡等，减少密钥和密文长度，使得部分参数的实现成为可能．为了提高全同态加密的效率，2011年之后密码学家又先后提出了不用Squash和Bootstrapping的体制［17－18］，使得全同态加密继续向实用化靠近．2 Gentry基于理想格的全同态加密体制2．1 Gentry全同态加密的基本思想2009年Gentry［13］给出了第1个全同态加密体制，该体制的构造分为如下3步：1）构造一个部分同态加密体制，对加密数据进行次数比较低的多项式的运算时可以保持同态性，即式（2）成立；2）降低解密多项式的次数；3）利用Bootstrapping实现全同态加密．该构造过程的核心是找到一个体制，使得式（2）成立的函数f的次数尽量高，而其加密函数的次数尽量低，一旦式（2）中的f对解密函数成立，该体制即被称为Bootstrapping的，即可以转化成一个全同态加密体制．Gentry构造的部分同态加密体制是一个类GGH［19］的基于理想格的体制，并且证明了在密钥生成算法恰当的情况下，这个体制的安全性可以归约到理想格上最坏情况的某些困难问题．但这个部分同态加密体制不是Bootstrapping的，Gentry经过在公钥中加一部分秘密密钥的暗示信息，降低解密函数的次数．在稀疏背包问题困难的假设下，这些信息不会影响体制的安全性．2．2 理想格基础n维格是Rn中的离散子集，具体地说是n个线性无关向量的整系数线性组合，这n个向量称为格的一组基．一个格有很多不同的格基，格基的性质对求解格中困难问题的难度有很大的影响．格的行列式定义为格基｛b1，b2，…，bn｝组成的基本体P（B）＝的体积，记det（L）＝vol（P（B）），行列式是对格基的不变量．f（x）是一个n次整系数不可约多项式，通常取f（x）＝xn＋1，n是2的方幂．R 是整系数多项式模多项式f（x）得到的环，R＝Z［x］/（f（x））．每个环里的元素是次数不超过n－1的多项式，因此可以表示成Zn中的一个向量．I是R中的一个理想即对R中元素加法和乘法有封闭性．因此I中的元素构成一个格，称为理想格．R中的一个元素v生成的理想对应的格可以由这样一组向量生成：2．3 Gentry的部分同态加密体制Gentry的部分同态加密体制是一种GGH类基于理想格的体制．公钥是一个理想格J的随机的“坏”格基Bpk和一个小的理想I的格基BI（用来将明文转换成扰动变量）．比如I＝（2），即所有系数为偶数的向量集合．通过将明文处理成扰动变量，密文是一个距离理想格J很近的向量．具体地说，明文空间是｛0，1｝，将0编码成0n，1编码成0n1，即将明文嵌入到R/I＝｛0，1｝n 中．对编码后的明文m∈｛0，1｝n，我们选择一个随机的短向量r，计算e ＝2r＋m，输出密文c←e mod Bpk．体制中的私钥（J的好的格基）是一个短向量w∈J－1，解密过程就是计算w×c的分数部分．由于c＝j＋e，其中j∈J，所以有w×c＝w×j＋w×e．而w×j在环R 中，即是一个整向量，因此w×c与w×e有相同的分数部分．如果w和e足够小，特别是如果能保证w×e的所有系数都小于1/2，w×e与w×e的分数部分［w×e］相同．解密者只需对密文c乘上w－1，即可得到e，计算m←e mod 2恢复m．在Gentry的原文中实际解密过程稍有不同．通过计算m←c－［w×c］mod 2解密．这个体制是部分同态的，2个密文c1＝j1＋e1，c2＝j2＋e2，它们的和可以表示成j3＋e3，其中，j3＝j1＋j2∈J，e3＝e1＋e2 是小的扰动向量．2个密文的乘积可以写成：j4＋e4，其中j4＝j1×（j2＋e2）＋e1×j2∈J，e4＝e1×e2，仍然较小．经过若干次乘法和加法在扰动大小还没有超过解密半径之前，该算法是同态的，即这是一个部分同态算法，具体可以进行的运算次数与具体参数选择有关．2．4 Gentry的全同态加密体制Gentry的部分同态加密体制对式（2）只能对低次数的函数f成立，当f的次数过大时，扰动变量超过秘密密钥的解密范围，同态性质就无法保持．为了实现全同态加密Gentry引入了Bootstrapping的思想．他观察到如果f是解密函数时能保证式（2）成立，就可以在不知道密钥的情况下更新密文，把扰动一直控制在较小的范围内，从而实现全同态加密．具体地说，如果满足：即可以用公钥pk2加密的私钥sk1和用公钥pk1加密的明文m作为输入，输出用公钥pk2加密的明文．实现了不知道私钥情况下的明文更新．满足这一条件的体制称作Bootstrapping的．但遗憾的是对2．3节介绍的部分同态加密体制来说，解密函数表示成密钥比特的多项式次数仍然太高，不满足式（2）．为了克服这个问题，Gentry进一步引入了降低解密函数的次数的技巧，在文中称作Squash．将原来的部分同态加密体制转化成一个新的体制，使得解密函数的次数降低，但对其他的性质没有影响．在原来的体制中秘密密钥是向量w，在新的体制中公钥包括一部分对w的提示信息，一个大的集合S＝｛xi，i＝1，2，…，S｝存在一个稀疏的子集T，其中的元素相加是w．用一个0，1比特串σ＝［σ1，σ2，…，σs］表示，即新的体制中秘密密钥是σ．这样在原算法中需要计算m←c－［w×c］mod 2解密，在新的算法中对密文c作一个处理，对所有的xi∈S，计算yi＝xi×c，解密过程转化成计算：再利用一些加法的技巧，该式可以表示成次数大约是集合T的元素数量的σj的多项式．合理地选择参数可以使得这里T足够小，得到一个Bootstrapping的体制．2．5 Smart－Vercauteren对Gentry体制的优化2010年PKC上Smart等人提出了第1个Gentry体制的优化［15］．该体制定义在环R＝Z［x］/（f（x））上，其中fn（x）＝xn＋1，n是2的幂次．在一个n维方体里随机选择向量v，满足v生成的格行列式是一个素数，记J＝（v），这样的J是一个主理想，这样的理想可以用2个参数（d，r）来表示：d＝det（J），r是fn（x）mod d的根．注意到该理想格的 Hermite形式具有如下的特征：这里［r］d 指将r模到（－d/2，d/2］之间．容易看出对一个向量a进行模HNF （J）的运算相当于计算多项式a（x）在点r处模d的取值，得到的向量是（［a （r）］d，0，0，…，0）．因此加密一个向量（m，0，0，…，0），其中m∈｛0，1｝，即选择一个随机小的多项式u（x），计算在点r处的取值，输出密文c←［2u（r）＋m］d．Smart和Vercauteren的体制中，秘密密钥只是一个整数w，计算即可解密．该体制可以实现Gentry的部分同态加密方案，但是Gentry体制的Squash仍因为参数太大无法实现，从而实现不了Bootstrapping，即无法实现全同态加密．Smart－Vercauteren的体制很大的一个局限是生成部分同态体制的密钥非常复杂，由于找到一个行列式是素数的元素需要生成大约n1．5个随机元素．计算秘密密钥的复杂度大约是n2．5．所以生成n＞2 048的密钥已不实际．而它们的解密函数的次数高达几百，需要n达到227才可以进行Squash步骤，而这么大的n对密钥生成又是不可能的．2．6 Gentry－Halevi对Gentry体制的实现Gentry－Halevi第1次完全实现了全同态加密［16］，对维数2 048，8 192，32 768公钥的大小大约为70MB到2．3GB，运行Bootstrpping的时间大约是30s到30min．本文对Gentry体制的优化主要有以下7个方面：1）放松了Smart－Vercauteren体制的对格的行列式是素数的要求，只需要基的HNF形式具有式（3）的特征即可．并且给出了一个非常容易的判别条件，判别这样的格．2）与Smart－Vercauteren体制类似，该体制也是使用一个秘密的逆多项式的一个系数来解密，但是为了简便用模计算代替了有理数的除法．3）在计算解密密钥时需要计算一个给定多项式模x2 m ±1的逆，这在Smart－Vercauteren的体制中是非常费时间的操作．给出了一个优化的算法可以高效地计算结式和逆多项式的一个系数，而不必计算整个多项式．4）使用了批处理技术加速加密，通过一起计算一些小系数的多项式在同一个点的值来有效计算．计算k个多项式只是计算一个多项式复杂度的倍．5）秘密密钥是一个长度为S≈1 000的二元向量，其中只有15个1，其他是0．通过用s个长度为S的（每个向量只有一个1）向量来表示秘密密钥提高算法的效率．6）公钥包含一个稀疏背包问题的实例，将其利用几何级数来表示，从而大大节省存储空间．7）全同态加密体制的公钥包含对秘密密钥比特的加密，利用时间和空间的平衡策略来优化存储空间而不增加过多的时间复杂度．3 基于整数的全同态加密2010年的欧密会上，Dijk等人［14］提出了一种基于整数的全同态加密体制．该体制与Gentry09体制非常类似，首先构造一个部分同态的体制，再利用Squash 降低解密函数次数，实现Bootstrapping．该体制的优势是它不需要理想格上的运算，但是公钥的长度仍然很长．算法安全性基于近似最大公因子问题．随后，在2011年美密会上，Coron等人提出了该体制的一种降低密钥长度的版本［20］，并且借鉴文献［16］的方法进一步作了优化．实现了安全强度分别为42B，52B，62B，72B的几个实例．对安全强度为72B的参数，加密和重加密分别需要3min和12min，解密时间很短，公钥大小是800MB．同时证明了经过这些优化之后算法仍然是语义安全的，安全性基于一个变种的近似最大公因子问题．3．1 DGHV体制利用［z］p 表示z 模p 到（－p/2，p/2］之间．生成一个η比特的奇数p，xi←Dγ，p（p），选其中最大的记为x0，并且保证x0是奇数，［x0］p 是偶数．公钥pk＝（x0，x1，…，xτ），私钥是p．加密1B的明文m，选择一个随机子集S⊆｛1，2，…，τ｝和1个在区间（－2ρ′，2ρ′）中的随机整数r，输出密文．解密计算m←（c mod p）mod 2．由于c mod需计算m在文献［14］中，证明了这是一个部分同态的体制，在近似GCD问题的困难性假设下是语义安全的．近似最大公因子问题，表述如下：参数（ρ，η，γ）近似GCD问题指对一个随机的η比特的奇数p，给定多项式个Dγ，p（p）中的取样，输出p．这个问题目前还没有找到高效的算法解决，被认为是困难的．将这个体制转化成全同态的，使用了与Gentry09类似的办法，通过增加公钥中部分私钥的信息，降低解密函数的系数从而实现Bootstraping．具体地说，是素数，因此只其中，κ＝γη/ρ′，选择一个随机的比特的0，1向量，只有θ比特为1，为了达到2λ的安全强度，对参数有如下要求：抵抗对扰动变量的穷举搜索攻击ρ＝ω（lbλ）；为了Squash技术的实现η≥ρΘ（λlbλ2）；抵抗格攻击γ＝ω（η2 lbλ）；保证安全性证明τ≥γ＋ω（lbλ），ρ′＝ρ＋ω（lbλ）．在文献［14］中，建议参数：ρ＝λ，ρ′＝2λ，η＝O～（λ2），γ＝O～（λ5），τ＝γ＋λ，公钥的长度是O～（λ10）．3．2 优化版本的DGHV体制2011年的美密会上Coron等人提出的减少密钥长度的方案［20］，主要创新点是xi生成的方式为x′i，j＝xi0xi1mod x0，1≤i，j≤β，这样只需要存储2β个整数就可以生成β2个整数x′i，j，公钥的大小从τ个γ比特的数降低到个．另外的不同还有x0是无扰动的变量x0＝pq0，该要求使得体制的安全性基于一个变体的近似最大公因子问题．称为无扰动近似最大公因子问题，具体描述如下：参数（ρ，η，γ）无扰动近似GCD问题指对一个随机的η比特的素数p，给定x0＝pq0，其中q0是一个属于［0，2γ/p］的随机无小于2λ 因子的无平方数，多项式个D′p（p，q0）中的取样输出p．这个问题目前也还没有找到高效的算法解决，被认为是困难的．这里：密钥生成一个η比特的随机素数p，q0是一个属于［0，2γ/p］的随机无小于2λ因子的无平方数，生成xi，b＝pqi，b＋ri，b，1≤i≤β，b∈｛0，1｝，其中qi，b是［0，q）的随机整数，ri，b∈（－2ρ，2ρ）．私钥是p，公钥是（x0，x1，0，x1，1，…，xβ，0，xβ，1）．加密对一个比特的明文m过程如下：生成一个随机大小为τ＝β2的向量b＝（bi，j）元素均在［0，2α）之间，生成一个（－2ρ′，2ρ′）中的随机整数r，输出密文bi，jxi，0xj，1mod x0．解密过程与原算法相同．在Squash的过程中，与原算法的不同之处就是为了节省存储，生成ui∈Z∩［0，2κ＋1］，i＝1，…，Θ时，不再是随机选取而是通过一个伪随机生成函数f和种子e来生成，这样将这部分存储从O～（λ8）降到仅保留0，1表示小数点后的为了达到2λ的安全强度，对参数有如下要求：抵抗对扰动变量的穷举搜索攻击仍有ρ＝ω（lbλ）；抵抗格攻击γ＝ω（η2 lbλ）；为了Squash技术的实现η≥（2ρ＋α）Θ（λlbλ2）；保证安全性证明αβ2≥γ＋ω（lbλ），ρ′＝2ρ＋α＋ω（lbλ）．在文献［20］中，建议参数与原算法相同有），另外还有＝4λ，与原体制需要个xi 不同，这里只需要2β＝O～（λ2）个xi，公钥的长4 全同态加密体制的新进展虽然在全同态体制的实用化方面做了很多工作，但其实现效率还远达不到应用的要求．主要有下面2点原因：1）Bootstrapping的复杂性至少是解密的复杂度乘以用来加密密钥比特的密文的比特长度．这是因为Bootstrapping需要同态计算解密函数，而解密密钥需要经过加密处理．而解密复杂度和密钥长度均为Ω（λ），因此Bootstrapping的复杂度至少是二次的．2）可以计算次数为d的函数部分同态加密体制，需要2d近似最短向量问题在2λ时间内不可解．格的维数需要达到Ω（dλ），向量的系数需要达到Ω（d）（单位B），因此更新后的密文长度至少是Ω（dλ2）．但是部分同态体制要达到Bootstrapping必须可以对自身的解密函数进行同态运算，即d必须大于解密函数的次数Ω（λ），因此更新后密文的长度为Ω～（λ2）．这样即使假设这些更新的密文解密只需要Θ（λ）的时间，总的时间仍然需要Ω～（λ4）．由于全同态加密体制在实际中的重要应用前景，对其研究和优化不断有新的进展，很多文章［21－22］发表在顶级密码学会议上，由于篇幅所限，这里不再做详细介绍．4．1 不带Squash的全同态加密体制最近 Gentry等人［18］和 Brakerski等人［23］分别独立提出了不用Squash步骤的同态加密体制．这样使得体制的安全性不再需要稀疏背包问题的困难性假设．这2个体制仍需要Bootstraping步骤，没有从根本上提高算法的效率．但这2种算法都提出了很有意义的思想．Gentry等人［18］通过将解密函数表示成不同的形式实现了Bootstrapping．他们观察到基于格的密码体制的解密函数可以表示成一种特殊类型的对称多项式，这种多项式可以利用大域上的深度为3的算术电路表示．尽管这个多项式的次数较高，他们证明了可以将其转化成乘同态的体制（如ElGamal）进行同态计算，再将结果转化回去．这里的乘同态体制可以用加同态体制来代替，比如通过加上离散对数．该体制的安全性依赖于最坏情况的理想格上的困难问题．Brakerski等人设计的体制［23］基于LWE问题，该体制的创新性主要有2点：1）基于LWE构造了一个部分同态加密体制，主要的技术是重线性化，突破了之前的体制都基于理想格上的困难问题的缺陷；2）利用维数约化和模约化的技术来减少密文的长度，降低解密复杂度．从而在不用Squash的情况下实现Bootstrapping．在基于LWE的体制中，解密通过计算密文和密钥的内积 m＝（〈c，s〉mod q）mod 2．维数约化技术将明文m在密钥s下的密文c转化成在一个不同的密钥s′加密下的密文c′，m＝（〈c′，s′〉mod q）mod 2．这里c′和s′的维数都比c，s小．为了实现这个步骤需要在公钥中包括s在s′下的加密，但是这里s不是按比特加密的．模约化步骤将m在密钥s下的密文c转化成一个在不同的模下的密钥s′下的密文c′，m＝（〈c′，s′〉mod q）mod 2．在部分同态加密的更新密文过程中，扰动会变得很大，利用维数约化和模约化得到同一个明文的小得多的密文，对这个小的密文执行解密过程，最终实现了不需要Squash的Bootstrapping．4．2 不带Bootstrapping的全同态加密体制Gentry借鉴Brakerski等人的设计中模约化的技术控制扰动变量的大小，提出了不需要Bootstrapping的全同态加密体制［17］．模约化的核心是如下的引理：p，q是2个奇数，c是一个整数向量，c′是一个与（p/q）c接近的向量且．对任意l1（s），有〈c′，s〉mod p＝〈c，s〉mod p mod 2，且，其中，l1（s）是s的l1 范数．该引理表明在不知道密钥s的情况下，只需要知道s长度的界，即可把一个模q 下的密文转化为一个模p的密文仍可以正确解密，即〈c′，s〉mod p＝〈c，s〉mod pmod 2，这个转化只涉及到一个数乘和取整．如果s比较短，p比q小，该转化达到了减小密文中扰动的目的，即〈c′，s〉modp ＜〈c，s〉modp．在不知道密钥的情况下减少扰动是Bootstrapping希望达到的目的，而模约化的步骤显然比Bootstrapping要简洁很多．模约化从表面来看并不是一个好的处理扰动的方法，因为对于比q小的p，模约化虽然降低了扰动变量的绝对值，但也相应减少了模的长度，即扰动和模的比值没有减少．对体制的同态能力来说，扰动的绝对值更重要．特别是对乘法．比如取q≈xk，2个模q的部分同态加密体制的密文如果扰动大小都是x，相乘之后扰动变成x2，经过4轮的乘法，扰动变成x16，即只能进行lb k层的乘法．如果选择一系列递减的模｛qi≈q/xi｝，i＜k．2个模q的密文相乘之后，把密文转化成在一个小的模q1≈q/x下，这样对应的扰动从x2降到x（这里假设l1（s）很小可以忽略）．再在模q1的情况下做2个密文的乘法，扰动仍是x2，再利用模约化技术将模降到q2，扰动仍可保持在x．以此类推，利用这种技术可以进行k层的乘法，大大提高了之前的lbk．这样通过模约化得到了噪声的减少，利用逐渐减少模，可以保持噪声一直比较小．实现了对任意多项式保持同态性质而不需要Bootstrapping，从而提高了算法的效率．关于该体制具体的优化可参见文献［17］，在这里不再详述．5 全同态加密的应用现实生活中的实际应用往往会大幅推动科学理论的发展．随着互联网的发展，尤其是云计算概念的诞生，人们在加密数据搜索与处理等方面的需求日益增加，大大推动了全同态加密方向的科学研究．与此同时，自Gentry的创新性工作发表以来，关于全同态加密的研究工作开始出现了新的高潮，被广泛应用于多种实际环境．本节将对全同态加密的一些典型应用作简要介绍．5．1 全同态加密一般性应用框架密码协议是大多数安全模块中必备的环节，从广义上讲，所有的密码协议都是安全多方计算的一个特例．它们广泛应用于金融交易、社交网络、实时监控、信息管理等多个领域．常见的密码协议中，通常包括多个参与者，他们可能是可信方（例如用户自己、经过认证的参与者）或不可信方（未经认证的参与者）．理论上，凡是存在不可信方的协议都具备全同态加密应用的可能．因此，全同态加密的大部分应用都可视作安全多方计算的范畴．当不可信方需要对敏感数据进行搜索、分析、处理等操作时，协议的其他参与者不希望不可信方掌握明文数据，因此可以采用全同态加密方案，让不可信方直接对密文进行操作，实现等同于对原始数据直接进行处理的效果，从而完成用户的需求．我们给出全同态加密的一般性应用框架，如图1所示：Fig．1 General application framework of fully homomorphic scheme．图1 全同态加密的一般性应用框架加密数据处理方法简述如下：假设存在全同态加密函数Enck（x），首先用户用自己的私钥k对需要处理的数据m进行同态加密c＝Enck（m），然后将加密数据c上传到云端服务器．服务器能够对加密数据c直接进行处理，得到c′＝f（c）＝f （Enck（m）），然后将处理后的密文c′返回给用户．用户收到c′＝f（c）＝f （Enck（m））＝Enck（f（m））后，利用自己的私钥k对其进行同态解密，得到已经处理好的明文数据f（m）．5．2 云计算中的全同态加密云存储安全是云计算领域的重要安全问题之一．为解决数据隐私保护的问题，常见的方法是由用户对数据进行加密，把加密后的密文信息存储在服务端．然而，当用户需要服务器提供数据搜索、分析、处理等功能时，传统加密方案难以实现，但全同态加密为之提供了实现的可能．5．2．1 云计算中的加密数据检索。