毕业论文（设计）全同态加密技术及其应用.pdf

南京航空航天大学硕士学位论文摘要全同态加密技术的提出对计算机科学与技术的发展具有举足轻重的意义，甚至有人认为全 同态加密技术是云计算的救星。全同态加密具有直接操作密文而不需要解密的优越性质，即对 密文进行任何运算之后，再解密得到的结果与直接对明文进行相应的运算结果相同。全同态加 密技术的密文运算性质使得它在云计算、密文搜索、电子投票和多方计算等领域都有着重要的 应用。然而，目前已经提出的全同态加密方案都是依据Gentry的全同态加密思路构造而成，方 案执行效率非常低，与实际应用还有很大的距离。如何改进全同态加密方案的执行效率与安全 性，已经成为当前全同态加密技术研究的重点与难点。本文首先对全同态加密技术的研究背景、研究现状、应用以及目前研究中存在的主要问 题进行了全面的概述，并对Gentry全同态加密方案的构造思路进行了详细的分析。然后，结合该构造思路，详细讨论了 Dijk和Gentry等人提出的整数上的全同态加密方案，并对方 案的安全性进行了证明与分析。本文在Gentry全同态加密方案构造思路的基础上，提出了一种一次可以加密2 bit明文的 全同态加密方案，使得加密效率提高了一倍；还结合使用了 Jean-Sebastien等人提出的“降低 集合维数”技术将公钥尺寸进一步降低，从而使得本方案的公钥尺寸低于Dijk和Gentry等人 方案；本方案的公钥尺寸为。（力），而后者的为。（才其中2是安全参数。基于Error-free 近似最大公约数问题和稀疏子集和问题这两个难解问题，对本文所提出的一次加密2bit的全同 态加密方案进行了安全性分析。关键词：全同态加密，部分同态加密，近似最大公约数问题，稀疏子集和问题全同态加密技术及其应用ABSTRACTThe appearance of the fully homomorphic encryption(FHE)has significant senses on the development of computer science and technology,and some authoritative scholars even believe that FHE will be the savior of cloud computing.FHE has the advantageous properties of performing complicated processing on ciphertext directly without being decrypted.In the other words,for arbitrarily computation on the ciphertext,the decryption result of it is the same as computation on the plaintext directly.Thus,there are a lot of applications of FHE technology,e.g.cloud computing,electronic voting,multi-party communication and etc.The fully homomorphic encryption scheme proposed recently are constructed in accordance with Gentrys FHE technique.However,the efficiency of the present FHE scheme is extra low and far from practical application.How to improve the efficiency and security of fully homomorphic encryption become the focus and pitfall of academic research.This thesis firstly introduce the background,related work,applications and main problems of FHE scheme in detail,and give a briefly introduction to Gentrys FHE technique.Then combined with Gentrys homomorphic encryption technique,we introduce a FHE scheme over the integer which was proposed by Dijk and Gentry et al.And we analyze and prove the security of the scheme.This paper proposes an improved fully homomorphic encryption scheme aimed at increaseing the efficiency of FHE scheme,which is based on Gentrys FHE technique too.The improved scheme can encrypt 2 bit plaintext each time and at same time reduce the public key size by employing Jean-Sebastien technique,accordingly the improved scheme is more efficient than Dijks scheme and has smaller public key size.The public key size of the proposed scheme is O(27),while Dijks schemes is O(210).Finally,we analyze the security of the proposed scheme is based on two hard problem,i.e the error-free approximate greatest common divisor problem and sparse subset sum problem.Keywords:fully homomorphic encryption(FHE),somewhat homomorphic encryption(SWHE),approximate greatest common divisor,sparse subset sum problemii南京航空航天大学硕士学位论文目录第一章绪论.11.1 全同态力口密技术概述.11.1.1 研究背景.11.1.2 全同态加密的定义.21.1.3 全同态加密技术的应用.31.2 研究现状和存在的问题.51.3 论文的主要工作.71.4 论文的组织结构.7第二章整数上的全同态加密方案.92.1 基本符号与定义.92.1.1 符号及其基本定义.92.1.2 全同态加密方案的构造思路.112.2 Dijk整数上的部分同态加密方案.122.2.1 对称部分同态方案.13222公钥部分同态方案.142.2.3 噪音增长分析.142.3 Dijk整数上的全同态加密方案.152.3.1 压缩解密电路.152.3.2 BootStrappable 方案.182.3.3 由 BootStrappable 方案变为全同态方案.192.4 Dijk整数上的全同态加密方案的缺陷与不足.232.5 本章小结.24第三章一次可以加密2 bit明文的全同态加密方案.253.1 整数上的全同态加密方案的改进.253.1.1 降低公钥尺寸的改进方案.253.1.2 整数上的一个快速FHE方案.263.2 一次加密2bit的部分同态加密方案.273.2.1 对称的部分同态加密方案.273.2.2 公钥的部分同态加密方案.28iii全同态加密技术及其应用3.2.3 噪音增长分析.303.3 一次加密2bit明文的全同态加密方案.313.3.1 压缩解密电路.313.3.2 BootStrappable 方案.323.3.3 由BootStrappable方案变为全同态加密方案.333.4 还存在的缺陷与不足.343.5 整数上的全同态加密方案的比较.353.6 本章小结.36第四章 安全性证明与分析.374.1 基础知识.374.2 Dijk等人方案的安全性分析与证明.384.2.1 公钥体制的SWHE的安全性证明.394.2.2 压缩解密电路的安全性分析.424.3 本文所提方案的安全性分析.424.3.1 公钥体制的SWHE的安全性证明.424.4 本章小结.45第五章总结与展望.465.1 总结.465.2 展望.47参考文献.48致谢.52在校期间的研究成果及发表的学术论文.53iv南京航空航天大学硕士学位论文图表清单图1.1加法同态和乘法同态.2图2.1加法扩展解密电路（左）和乘法扩展解密电路（右）.10图2.2 Evaluate中的电路是解密电路的情况.11图2.3 Evaluate中的函数是DecAdd的情况.12图2.4 Evaluate中的函数是。比由万的情况.12图2.5 three-for-two trick将三个数的和变为两个数的和.17图2.6计算勾和的算法.18图2.7普通解密电路（左）和解密电路在Evaluate算法中（右）的情况.20图 2.8 Recrypt（pk2,D,sk.,q）的示意图.20El图2.9 Recrypt算法中使用加法扩展的解密电路.21图2A0 Recrypt算法中使用乘法扩展的解密电路.22图2.11私钥在公钥pki+1下得到密文向量.22图2.12第，层电路的输入以及输出.23图3.1计算q和的快速算法.33表3.1公钥部分同态加密方案的对比.35表3.2全同态加密方案的对比.36v全同态加密技术及其应用注释表f一个t元函数实数Z向上取整t函数）的参数个数H实数z近似取整（四舍五入）pk公钥a实数Z向下取整sk私钥%Z除以夕的商近似取整c 1,C2,5个密文5（z）z mod pmi,m2,nit1个明文z mod pA一个加密方案的安全参数cE所有允许电路的集合PFHE中噪音长度De解密电路以及扩展的解密电路7私钥的二进制长度E对称的部分同态加密方案y公钥的二进制长度E；公钥部分同态加密方案T公钥的个数E2Bootstrappable部分同态方案vi南京航空航天大学硕士学位论文缩略词缩略词英文全称FHEFully Homomorphic EncryptionApproximate GCDApproximate Greatest Common DivisorPHEPrivacy Homomorphism EncryptionSSSPSparse Subset Sum ProblemLSBLeast Significant BitSWHESomeWhat Homomorphic EncryptionError-Free Approximate GCDError-free Approximate Greatest Common DivisorPGRPrivate Google SearchPartially Approximate GCDPartially Approximate Common Divisor Problem南京航空航天大学硕士学位论文第一章绪论1978年，在RSA”密码体制刚刚提出不久，Ri vest,Adleman,Dertouzos就提出了全同态 力口密(Fully homomorphic encryption,FHE)的概念(又叫隐私同态 privacy homomorphisms)o 他 们希望在不对密文解密的条件下，对密文进行任意运算等价于对明文进行相应运算。全同态加 密可以方便地进行密文搜索以及任意的密文运算，在云计算应用越来越广泛的今天，全同态加 密技术显得尤为重要；甚至有人认为，全同态加密技术是云计算的救星。本章首先对全同态加 密技术的研究背景、已有的研究成果以及存在的主要问题进行阐述，然后介绍本文的主要工 作及章节安排。1.1 全同态加密技术概述1.1.1 研究背景在公钥密码体制提出之后，全同态加密(FHE)就开始深深地困扰着密码学领域的学者和研 究人员。使用全同态加密方案得到的密文具有可直接运算的优良性质，即对密文进行任意计算 之后再解密，结果与对明文进行相应计算的结果相同。尽管研究的进展十分缓慢，但学者一直 都没有放弃。全同态加密技术的优越性质，决定了它在诸多场合下都有重要的应用价值。目前，已经有 很多公司提供云计算平台系统，但是极少有公司或者个人愿意使用，因为用户不愿意把隐秘信 息以明文的形式放在云端；而以密文的形式存放，又会导致对密文的查询和修改以及其他一些 操作极其不方便。全同态加密技术被认为是云安全的关键技术，对云计算的发展具有强大的推 动作用，并入选了麻省理工科技创业评出的“2011十大新兴技术”。另外，全同态加密技 术在密文搜索、物联网、电子投票等领域也有重要的应用。在密码界，全同态加密技术甚至被冠以“密码学的圣杯”的称号，入围2011年度美国大 众机械杂志的十大技术概念，大批顶尖研究人员被吸引到全同态加密技术的研究队伍中，IBM、微软等软件巨头也投入巨大的人力与物力进行全同态技术的研究。虽然，研究人员、学者以及 大型软件公司都付出了艰辛的努力，但是，全同态加密技术的研究进展一直很缓慢。直到2009 年IBM的研究员Craig Gentry才利用“理想格(ideal lattice)”构造了第一个真正意义上的全同态 加密方案，同时，在其博士论文中对如何构造全同态加密方案进行了更加深入的论述，并 指出了当前全同态加密技术研究的重点与难点。Gentry的全同态加密方法的提出，树立了全同 态加密技术研究的一座里程碑，给研究人员和学者构建了一个蓝图。但是，Gentry等人提出的 方案的效率很低，离实际应用还有很大的距离。如何改进全同态加密方案的效率与安全性将一 直成为全同态加密技术研究的热点与难点。1全同态加密技术及其应用1.1.2 全同态加密的定义用最通俗的话可以这么定义全同态加密：由全同态加密方案产生的密文，可以对密文进 行任意计算，解密结果与对明文进行相应计算的结果相同。用正式的语言可以描述为：若一个 加密方案E对加法和乘法都具有同态性质，则称方案E是一个全同态加密方案，其中，加法同 态和乘法同态如图1.1所示。RSAi是第一个同态加密方案，但是仅有乘法同态性质，而Rivest,Adleman,Dertouzos等人很有可能是受到了 RSA乘法同态性质的启发，才提出全同态加密 的概念的。下面首先给出全同态加密的严格定义，然后，介绍一个的全同态加密方案的构成。mi加同态：m2mi乘同态：m2Cl+C2埋驾加1+加2解f密0*。2厂 加1*加2Ci|-Encrypted under pk图1.1加法同态和乘法同态定义1.1（全同态加密方案）一个加密方案石如果满足：对密文做任意操作之后再解密，结 果与对明文进行相应操作结果相同，则称该加密方案是全同态加密方案3也可以描述为，若 Decrypt是方案E的解密算法，s左是解密密钥，pk是加密密钥，汽修,到,，珀是一个t元函数，贝I DecryptE（f（C,C2,.,Ct）,sk）=f（Ph,m2,m）。通常，一个普通的加密方案由KenGen,Encrypt,Decrypt三个算法组成，而一个全同态加 密方案还需要第四个算法Evaluate,下面将详细介绍全同态方案中的四个算法定义：KeyGen（Z）：密钥产生算法，根据安全参数A产生方案的加密密钥pk和解密密钥sk；Encrypt,/w）：加密算法，用加密密钥p上将明文相加密为密文c,输出密文c；Decrypt,c）：解密算法，用解密密钥解密密文c,得到明文加，输出明文机；Evaluate/,同态计算算法，输入加密密钥p左、具有I个输入的函数力以及方个密文序列ci,%”其中c尸Encrypt匕科）=1,2,J）。算法的输出结果为c*=Evaluate（法/；ci,%,6），且输出结果满足Decrpt（我c*月（如2,4t）。Evaluate算法的含义是：对密文进行 任意操作再解密，结果与对明文进行相应的操作结果相同；此处的函数/也可以换成函数对应 的二进制电路。作为输入。后面的章节中，我们将讨论Evaluate中的函数参数/是解密函数、加法扩展的解密函数、乘法扩展的解密函数时，Evaluate算法的特殊意义。关于加法扩展的解 密函数、乘法扩展的解密函数的具体定义，可以参考2.1.1小节。2南京航空航天大学硕士学位论文1.1.3 全同态加密技术的应用全同态加密技术具有可以直接操作密文的良好性质，在很多领域都有着非常重要的应 用，比如云计算、密文搜索、电子投票、多方通信等，当然，电子投票和多方通信仅要求部 分同态，即加法或者乘法同态即可满足其需求。正是因为全同态加密技术的重要的应用意义，研究人员和学者才会在过去的30多年中锲而不舍地进行研究。下面将分别介绍全同态加密 技术在各个领域的应用。(1)云计算云计算是计算机科学与技术领域向大规模化、集约化以及专业化发展的重要标志，是 IT界的诸多深刻变革之一；云计算虽然提高了设备的使用效率与价值，但是，不可忽略的 是，它给普通用户的信息资产的安全性与隐秘性带来了巨大的冲击与挑战。研究人员和学 者将云安全问题视为亟待解决和突破的问题，很多研究人员甚至认为，云安全已经成为阻碍 云计算发展的重要因素之一。根据Gartner 2009年的调查结果，至少有70%接受采访的企业 首席技术执行官表示，不愿意使用云计算的核心缘由是：云计算存在巨大的数据安全性以及 隐秘性问题。同时，一些云计算服务商，如Amazon、谷歌等，发生的各种安全事故更是加 深了人们对云计算的安全性的忧虑。在2009年，Google的大量用户资料因为云安全发生外 泄；同年，Amazon所提供的“简单存储服务”出现中断，一些单一依赖Amazon服务的网 站都被迫处于瘫痪的状态。麻省理工科技创业将全同态加密技术评为“2011十大新兴技术”，并认为全同态加密 技术将会极大的推动云计算在未来的发展。因为，云端使用全同态加密技术之后，用户的信息 可以以密文形式存放，全同态加密方案保证了对密文直接计算的便利性；同时，密文形式的数 据信息可以给用户的信息足够的安全保证。可见，全同态加密技术在云计算领域有重要的实际 应用意义。(2)密文搜索密文搜索是Rivest,Adleman,Dertouzos等人提出全同态加密概念的初衷之一，当数据处 于密文形式时，数据本身的一些特性会失去叵力，从而无法对数据进行直接运算。比如对于密文 的查找，当使用精确匹配查找字符串的密文时，不用解密就可以成功查找；但是，当需要对查 找的密文进行大量的模糊匹配或者是大量的比较操作时，如like,等，必须对密文解密得到对 应的明文才能进行查找。也就是说，对于普通的非同态加密方案，必须先解密才能对密文进行 运算，而解密无疑会造成巨大的时间和空间开销。如何才能做到不需要解密，而直接对数据进行操作？这个问题在1978年，Rivest等人就给 出了答案，即全同态加密技术；然而，理想总是美好的，如何构造全同态加密方案一直困扰了 学者与研究人员30多年。Gentry在2009年提出了第一个全同态加密方案，在他的论文中，3全同态加密技术及其应用同时给出了全同态加密方案构造思路，并在其博士论文中进行了更加深入的研究与阐述。Gentry的全同态加密方案构造思路的提出，无疑给困惑已久的研究人员和学者带来了光明与希 望。Google的隐秘搜索(Private Google Search,PGR)就是密文搜索在现实中应用的典型代表。当 然，目前解决密文搜索还有一些别的方法，例如，GQzsoyoglu等人提出的保持数据有序的加密 方案；L.Bouganim等人使用“智能卡”方法实现了加密数据的快速查找巴H.Hacigumus等 人使用“过滤技术”从而缩小解密范围，实现加密数据快速查询；但是，这些方法都有各自 的缺陷与不足，而全同态加密技术才是实现密文搜索的最佳手段。相信随着研究人员和学者对 全同态加密技术的不断深入研究，在不久的将来我们必定可以实现高效的密文搜索操作。(3)电子投票(E-Voting)1981年Chaum提出的不可追踪的电子邮件1I是电子投票的雏形，从此电子投票技术开 始迅速发展并取得了显著的研究成果。电子投票有以下两个目标：第一、确保投票人的选举 秘密性，即无法从选票中看出投票人选的是哪一个候选人；第二、一定要确保选举的权威性 与正确性，也就是说，不能出现伪造选票和遗漏有效选票的现象。在电子投票领域，同态加 密技术有着广泛的应用。Benaloh在1994年把“无收据性(receipt free)”引入到电子投票领域皿】，以达到预防电 子投票过程中出现的欺骗、犯罪行为(选票强迫和选票买卖)。所谓的无收据性是指：投票人 没有办法向第三方证明他自己提交的选票内容。然而，Hirt与Sako在文献13中证明了 Benaloh的上述方案在有多个计票成员的时候，不能满足无收据性；并在该文献中使用加法 同态的加密方案，提出了一个1-out-of-N的满足无收据性的电子投票方案。Riza等人在文献 14中展示了同态加密技术如何应用于有序的电子投票中(preferential elections),不过，文献 中提出的方案效率太低不能满足实际应用；文献15基于乘法同态加密方案提出了一种效率 更高的电子投票方案，具有更普遍的应用性。可见，同态加密技术在电子投票领域中有着重 要的应用意义。(4)多方计算(Multi-party communication)所谓的“多方计算”是指有两个或者两个以上的用户，每个用户拥有一部分秘密信息，而最终需要的信息是所有用户的信息进行一定的计算得到的。可以简单的将多方通信描述 为：几个用户中的第，个用户拥有秘密信息收，现在这几个用户想都知道/(如第2,加)，但 是每个用户又不想自己拥有的秘密信息明被其他用户知道。多方计算的典型代表是Andrew Yao等人提出的富翁问题(millionaire problem)16o富翁 问题是指如何让两个富翁Alice和Bob知道谁更富有，但是又不能让对方知道自己拥有的财 富的数额。虽然，Andrew Yao等人在文献16中给出了解决富翁问题的方案，但是方案的时 4南京航空航天大学硕士学位论文间与空间开销过大，不能应用到实际生活中。于是，研究人员提出了一系列的以加法同态加 密方案为基础的协议，大大的降低了解决富翁问题的时间和空间开销。如Hsiao-Ying Lin在 文献17中提出的协议，即可以使用加法同态加密方案，也可以使用乘法同态加密方案，当 然，使用乘法同态加密方案的时候，会获得更高的效率。其他的一些基于同态技术改进富翁 问题的例子，此处不再赘述。平均工资问题也是多方通信的经典代表问题之一。甲、乙、丙三人想知道三个人的平均 工资，但是又不想别人知道自己的实际的工资。这个时候，就可以使用一个全同态的加密方 案去解决这个问题。不妨假设甲、乙、丙三人的工资分别为。、氏c,对应的全同态加密的 密文分别为*、。*、三人分别将密文发送给可信第三方，由可信第三方去计算密文平 均值，再分别将密文的平均值发送给甲、乙、丙三人。甲、乙、丙对密文的平均值进行解密，就可以得到平均工资了，同时自己的工资依然是保密的。当然，除了上述提及的4个领域之外，全同态加密技术在其他的很多领域都有重要的应 用意义，本节将不再一一说明。下面，我们就对全同态加密技术的发展历程，以及目前FHE 研究的重点与难点进行全面的介绍。1.2 研究现状和存在的问题从1978年全同态加密的概念首次（当时称为隐私同态privacy homomorphism encryption,PHE）被提出来到2008年，尽管研究人员和学者在全同态加密技术上付出了不懈的努力，但是,研究进展甚微，人们提出的方案或者仅具有加法同态性质，或者仅有乘法同态性质，或者仅仅 只能进行有限次的加法和乘法同态运算。直到2009年研究人员才构造出第一个全同态加密方 案，可以说是全同态加密技术发展的一座里程碑。下面将分别简要介绍一下同态加密方案和全 同态加密方案的主要发展历程。RSA不仅是第一个既能用于加密又能用于签名的公钥密码方案，而且也是第一个同态加密 方案，不过，RSA仅具有乘法同态性质，且不是语义安全”Semantic security）的。1996年Boneh 和Lipton证明了整数环Zn上的任何非语义安全的同态加密算法可以在指数时间内被破解口叫 van Dam、Hallgen等人在文献20中分析了量子计算机下非语义安全的同态加密算法的安全性,且证明了在量子计算机下，任何确定性（即非语义安全）的同态加密算法可以在多项式时间被破 解。第一个语义安全的同态加密算法是Goldwasser-Micali在1982年提出的1，并给出了语义 安全的定义。此后，研究人员和学者提出了许多语义安全的加法同态的方案，例如Benaloh.,Naccache-Stem 22,Okamoto-Uchiyama23,Paillier 24,and Damgard-Jurik 的等人提出的方案。在 语义安全的同态方案中，Boneh-Goh-NissimM和Fellows and Koblitz也提出的方案，同时具有 加法和乘法同态性质；Boneh-Goh-NissimM提出的方案允许计算密文的二次公式（quadratic 5全同态加密技术及其应用formulas)的值；Fellows和Koblitz提出的方案允许密文在任何电路中进行计算，不过，此方 案的密文的长度随着电路深度的增加成指数增长。研究人员和学者也提出了许多基于格(lattices)和线性码(linear codes)的同态加密方案。文献 28,29,30,31,32中提出的加法同态方案都是基于格或者线性码的，其中，基于格的方案和 Armknecht、Sadeghi提出的方案阳同时具有加法和乘法同态性质；但是，密文之间进行运算时，密文的运算结果会按指数级别扩展。这些方案有一个共同的特性：密文中包含一部分噪音(error 或noise),且这些噪音随着密文的加法或者乘法运算而不断的增加；当噪音增加到一定程度时，密文就不能进行正确的解密。因此，这些同态加密方案也被称作pseudo homomorphism30,31,32 或者有界同态(bounded homomorphism)29。IBM研究院的研究员Gentry在2009年构造出第一个全同态加密(FHE)方案，方案的数学 基础是“理想格(ideal lattice)”，并在其博士论文中对全同态加密方案进行了更加详细的论述。这两篇文章给全同态加密技术的研究与发展带来了强大的动力，掀起了一股全同态加密技术研 究的热潮，国内外的专家和学者提出了许多改进的全同态方案。Marten van Dijk,Graig Gentry 等人提出了整数上的基于简单模运算的全同态方案网3旬,但是方案的执行效率比较低，i bit的明 文对应的密文约为万bit(其中，2是安全参数)，且公钥尺寸太大，无法编程实现。Vercauteren 和Smart使用Gentry的全同态加密思想，提出了密钥和密文尺寸相对较小的方案，提高了密文 同态运算的效率阳。stehle和Steinfel进一步优化Gentry的方案，以允许“可忽略概率解密错误”这一弱化条件，降低了密文计算复杂度的，从而得到一个代数数域(algebraic number fields)上的 较快速的全同态加密方案。目前，国内关于全同态加密方案的论文还比较少，汤殿华、祝世雄、曹云飞等人在文献37中提出的一种较快速的整数上的全同态加密方案，相比文献33中方案具 有更短的公钥尺寸、更小的解密复杂度；并在文献38中对Gentry的全同态加密思路中的重加 密技术进行了总结。虽然现在已经有很多改进的全同态加密方案被提出来，但是这些方案的效率都不高。Dijk 等人网提出的整数上的加密方案，以及上述按照Gentry的全同态加密思路构造的全同态加密方 案35,36,37,39,一次都仅仅只能加密1 bit明文，加密速度慢；然而，1 bit的明文对应的密文是一 个大整数(密文的二进制位数约为才，其中2是安全参数)或者是其他复杂数学对象，显然，这 导致原本只需要1 bit空间存储的明文变为需要N bit存储空间的密文(其中N是一个整数)，大 大的增加了存储开销。而且对密文进行任意运算的时候，都需要先对密文进行重加密，而重加 密的时候也是逐bit进行的，显然目前提出的全同态加密方案的效率都非常低，与实际的应用 还有很大距离。可见，如何改进全同态加密方案的执行效率是未来一段时间全同态加密技术研 究的重点与难点。6南京航空航天大学硕士学位论文1.3 论文的主要工作全同态加密技术具有可以直接处理密文的优越性质，在云计算、密文搜索、物联网、电子 投票、多方通信等领域都有着重要的应用。虽然，全同态加密技术已经有30多年的发展历史了，但是，目前的全同态加密方案都是依据Gentry在2009年提出的全同态加密方案构造思路构造 的，方案的执行效率很低，与实际应用还有很远的距离。本文的研究重点是如何提高整数上的 全同态加密方案的效率，具体工作如下所述：(1)对全同态加密技术的发展历程、研究背景等进行了简单的介绍，分析了当前的全同态加 密技术所面临的主要技术难点与重点；(2)对Dijk和Gentry提出的整数上全同态加密方案进行了详细的介绍，方案的安全性基于 近似最大公约数问题(approximate greatest common divisor,Approximate GCD)和稀疏子集问题(Sparse Subset Sum problem,SSSP),并给出了方案的安全性证明；(3)对Gentry的全同态加密方案的构造思路进行了总结与分析，并介绍了目前对整数上的 全同态加密方案进行改进的主要思路，对目前整数上的几种全同态加密方案进行对比，分析各 个方案的的优劣性；(4)使用Gentry的全同态加密思想，提出了一个整数上的一次可以加密2bit明文的全同态 加密方案；从而使得全同态加密算法的效率提高了一倍。方案的安全性基于Error-free近似最大 公约数问题(Error-free Approximate GCD)和稀疏子集问题(SSSP),并对方案的安全性进行了分析 与证明。1.4论文的组织结构本文一共包含五个章节，文章的组织结构安排如下：第一章绪论:首先对全同态加密技术进行了简单的介绍，包括全同态加密技术的研究背景、国内外研究进展、主要应用、目前的研究重点与难点。然后，给出了本文的研究重点，并对文 章所做的主要工作进行了总结。第二章 整数上的全同态加密方案：主要介绍Dijk和Gentry的整数上的全同态加密方案，给出了安全性证明与分析，并对Gentry的全同态加密方案构造思路进行说明。第三章 整数上全同态加密方案的改进:首先给出目前整数上的全同态加密方案的主要改进 思路，然后，按照Gentry的全同态加密技术，构造一个一次可以加密2 bit明文的全同态加密 方案，方案的安全性基于Error-free近似最大公约数问题和稀疏子集和问题。第四章安全性分析与证明：给出了第二章和第三章方案的安全性证明与分析，证明的基本 思路是将方案的安全性规约到一个数学难题上；具体为：假设方案存在一个多项式时间内的破 解算法，然后将对方案的破解算法转换为对数学难题的破解算法，而目前认为数学难题在多项 7全同态加密技术及其应用式时间内没有解，从而推出原假设错误，即证明原方案不存在破解算法，最终证明了原方案是 安全的。第五章总结与展望：对本文工作主要工作进行总结，并对今后可以进行的工作进行展望。8南京航空航天大学硕士学位论文第二章整数上的全同态加密方案在2009年，Craig Gentry使用理想格构造了第一个真正的全同态加密方案，在理论上取得 了很大的突破，并给研究人员和学者展现了一种全同态加密方案构造的蓝图。本文研究的重点 是整数上的全同态加密技术，理想格以及其他复杂数学对象上的全同态加密技术本文不进行阐 述。本章首先介绍Gentry全同态加密方案构造思路中的一些基本概念，然后，结合Gentry的 全同态加密方案构造思路，详细介绍Dijk和Gentry提出的整数上的全同态加密方案。下面先 给出整数上的全同态加密方案的常用符号以及定义。2.1基本符号与定义2.1.1 符号及其基本定义对于实数Z分别用|zz,z+l）、团（2-；,2+；和|_2（2-1,%表示向上取整、近似取 整以及向下取整。对于实数Z和整数P，用卷（Z）表示Z除以2的商近似取整），Z/Z）或者Z。表示z mod p的值，本文中模p运算的取值范围是o根据上述定义易知%（Z）=%以 及9（z）=z-%仁）*2。本文中用希腊字母表示方案中参数的取值范围，下面是本文方案中使用 到的希腊字母的含义：2：是方案的安全参数；夕：噪音的长度，为了阻止暴力攻击（brute-force attacks）噪音长度应该取夕二G（log2）,有时 为了方便也会用pr=p+a）QlogX）；7：私钥的二进制长度，为了让压缩的解密电路属于允许电路中，私钥长度应该满足不 等式 0（2log2 2）；/：公钥的二进制长度，为了防止基于格的对近似最大公钥数问题的破解，公钥长度应该 满足 Y-Gjk 21og，）；r：需要的公钥的个数，应该满足；本文使用文献39中的方法，可以得到 一个公钥尺寸较小的方案，实际的公钥个数为2五。后面的文章中将使用到这些符号，在后面将不再重复给出这些符号的定义。在正式阐述整 数上的全同态加密方案之前，我们先给出一些基本概念的定义，这些基本定义在文献3,4,33,34 中都可以找到，在下面的概念定义中将不再一一的写出参考文献。定义 2.1（允许函数 Permitted function）方案 E=（KeyGen,Encrypt,Decrypt,Evaluate）是一 个同态加密方案，/是一个方元函数；若对KeyGen（九）算法产生的任意密钥对岫左），任意选择 个明文如，加2,，w，以及由EncryptQLM算法产生的/密文,G，其中G=Encrypt 9全同态加密技术及其应用都有等式Decrptg Evaluate女工ci,c2,.,ct）=4加1,加2,孙）成立，则称函数/是方案E的允许函 数。函数/对应的二进制电路。称为方案E的允许电路（permitted circuit）,方案E的所有的允 许电路的集合记为金。若方案E的允许电路的集合金可以是任意的电路，则称方案E是全同 态加密方案（Fully homomorphic encryption scheme）；否贝U，称方案E是部分同态方案（Somewhat homomorphic encryption scheme）。定义2.2（扩展的解密电路Augmented Decryption circuits）将一个力口密方案的解密算法表示 成一个二进制电路（由二进制的加法和乘法门构成，输入的是私钥的二进制bit位和密文的二进 制bit位），则称这个电路为解密电路；一个同态加密方案E的扩展解密电路是由一个加法或乘 法电路将两个解密电路连接起来得到的，即：DecAdd（sA,q,Q）=Decrypt sk,c+Decrypt（skj）Dec Mu,（女,。1，。2）=Decrypt（sk,c J*Decrypt（skc?）其中Oeq（sKqg）是加法扩展解密电路，口口毗3左勺心）是乘法扩