整数上的全同态加密方案的改进

　 　 收稿日期： ２０１２ ０９ ０４； 修回日期： ２０１２ １０ ２８　 　 基金项目： 国家“８６３”计划高技术研究发展项目（２００９ＡＡ０４４６０１）；江苏省普通高校研究
生科研创新计划资助项目（ＣＸＺＺ１２＿０１６１）；中央高校基本科研业务费专项资金资助项目
　 　 作者简介：林如磊（１９８６ ），男，安徽合肥人，硕士，主要研究方向为全同态加密 （ｌｉｎｒｕｌｅｉ＠１３９． ｃｏｍ）；王箭，男，教授，博士，主要研究方向为密
钥管理、密码协议、隐私保护、恶意追踪等；杜贺，男，博士，主要研究方向为密钥管理、数字签名等．
整数上的全同态加密方案的改进

林如磊， 王　 箭， 杜　 贺
（南京航空航天大学 计算机科学与技术学院， 南京 ２１００１６）
摘　 要： 目前的全同态加密方案的效率还很低，与实际的应用还有很大的距离，提高全同态加密方案的效率和
安全性是全同态加密技术研究的重点与难点。 为了提高效率，在 Ｄｉｊｋ 等人的全同态加密方案的基础上，将模２
运算改为模４ 运算，并使用Ｇｅｎｔｒｙ 的全同态思想，提出了一种更快速的全同态加密方案，改进之后的方案一次可
以加密２ ｂｉｔ 的数据，且公钥尺寸降低到
珟
Ο（λ
７
），从而比Ｄｉｊｋ 等人的方案具有更高的效率和更小的公钥尺寸。 新
方案的安全性基于近似最大公因子问题和稀疏子集和问题。
关键词： 全同态加密； 近似最大公因子问题； 稀疏子集和问题； 公钥尺寸
中图分类号： ＴＰ３０９　 　 　 文献标志码： Ａ　 　 　 文章编号： １００１ ３６９５（２０１３）０５ １５１５ ０５
ｄｏｉ：１０． ３９６９ ／ ｊ． ｉｓｓｎ． １００１３６９５． ２０１３． ０５． ０６０
Ｉｍｐｒｏｖｅｄ ｆｕｌｌｙ ｈｏｍｏｍｏｒｐｈｉｃ ｅｎｃｒｙｐｔｉｏｎ ｏｖｅｒ ｉｎｔｅｇｅｒｓ
ＬＩＮ Ｒｕｌｅｉ， ＷＡＮＧ Ｊｉａｎ， ＤＵ Ｈｅ
（Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ＆ Ｔｅｃｈｎｏｌｏｇｙ， Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ａｅｒｏｎａｕｔｉｃｓ ＆ Ａｓｔｒｏｎａｕｔｉｃｓ， Ｎａｎｊｉｎｇ ２１００１６， Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ： Ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｔｈｅ ｐｒｅｓｅｎｔ ｆｕｌｌｙ ｈｏｍｏｍｏｒｐｈｉｃ ｅｎｃｒｙｐｔｉｏｎ ｓｃｈｅｍｅ ｉｓ ｅｘｔｒａ ｌｏｗ ａｎｄ ｆａｒ ｆｒｏｍ ｐｒａｃｔｉｃａｌ ａｐｐｌｉｃａｔｉｏｎ．
Ｈｏｗ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ａｎｄ ｓｅｃｕｒｉｔｙ ｏｆ ｆｕｌｌｙ ｈｏｍｏｍｏｒｐｈｉｃ ｅｎｃｒｙｐｔｉｏｎ ｂｅｃｏｍｅ ｔｈｅ ｆｏｃｕｓ ａｎｄ ｐｉｔｆａｌｌ ｏｆ ａｃａｄｅｍｉｃ ｒｅｓｅａｒｃｈ．
Ｉｎ ｏｒｄｅｒ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ， ｔｈｉｓ ｐａｐｅｒ ｐｕｔ ｆｏｒｗａｒｄ ａｎ ｉｍｐｒｏｖｅｄ ｓｃｈｅｍｅ ｏｆ ｔｈｅ ｂａｓｅ ｏｆ Ｄｉｊｋ’ ｓ ｓｃｈｅｍｅ ｕｓｉｎｇ Ｇｅｎｔｒｙ’ ｓ
ｆｕｌｌｙ ｈｏｍｏｍｏｒｈｐｉｃ ｔｅｃｈｎｏｌｏｇｙ． Ｔｈｅ ｉｍｐｒｏｖｅｄ ｓｃｈｅｍｅ ｃｏｕｌｄ ｅｎｃｒｙｐｔ ２ ｂｉｔ ｐｌａｉｎｔｅｘｔ ｅａｃｈ ｔｉｍｅ ａｎｄ ｒｅｄｕｃｅ ｔｈｅ ｐｕｂｌｉｃ ｋｅｙ ｓｉｚｅ ｔｏ
珟
Ο（λ
７
），ａｃｃｏｒｄｉｎｇｌｙ ｔｈｅ ｉｍｐｒｏｖｅｄ ｓｃｈｅｍｅ ｗａｓ ｍｏｒｅ ｅｆｆｉｃｉｅｎｔ ｔｈａｎ Ｄｉｊｋ’ｓ ｓｃｈｅｍｅ ａｎｄ ｈａｄ ｓｍａｌｌｅｒ ｐｕｂｌｉｃ ｋｅｙ ｓｉｚｅ． Ｔｈｅ ｓｅｃｕｒｉｔｙ
ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ｓｃｈｅｍｅ ｗａｓ ｂａｓｅｄ ｏｎ ｂｏｔｈ ｔｈｅ ａｐｐｒｏｘｉｍａｔｅ ＧＣＤ ｐｒｏｂｌｅｍ ａｎｄ ｔｈｅ ｓｐａｒｓｅｓｕｂｓｅｔ ｓｕｍ ｐｒｏｂｌｅｍ．
Ｋｅｙ ｗｏｒｄｓ： ｆｕｌｌｙ ｈｏｍｏｍｏｒｐｈｉｃ ｅｎｃｒｙｐｔｉｏｎ； ａｐｐｒｏｘｉｍａｔｅ ＧＣＤ； ｓｐａｒｓｅ ｓｕｂｓｅｔ ｓｕｍ ｐｒｏｂｌｅｍ； ｐｕｂｌｉｃ ｋｅｙ ｓｉｚｅ
　 引言
１９７８ 年，在ＲＳＡ
［１］
密码体制刚刚提出不久，Ｒｉｖｅｓｔ 等人
［２］
提出了全同态加密的概念（ 又叫隐私同态，ｐｒｉｖａｃｙ ｈｏｍｏｍｏｒ
ｐｈｉｓｍｓ），并认为全同态加密技术是可以实现的，同时提出了几
种候选的同态加密方案。 他们希望在不对密文解密的条件下，
对密文进行任何运算，得到的结果解密后与对明文进行相应运
算的结果相同。 全同态加密思想提出之后，国内外的研究人员
以及学者对全同态加密进行了大量的研究，然而他们提出的方
案都只能对密文进行有限次同态运算，没有达到真正的全
同态。
第一个全同态加密（ｆｕｌｌｙ ｈｏｍｏｍｏｒｐｈｉｓｍ ｅｎｃｒｙｐｔｉｏｎ）方案是
ＩＢＭ 研究员Ｇｅｎｔｒｙ
［３］
在２００９ 年利用理想格（ｉｄｅａｌ ｌａｔｔｉｃｅ）构造
的，并在其博士论文
［４］
中对全同态加密方案进行了更加深入
的论述。 这两篇文章给全同态加密技术的研究与发展带来了
强大的动力。 国内外的学者提出了许多改进的全同态方案。
Ｄｉｊｋ 等人
［５，６］
提出了整数上的基于模运算的全同态方案，但是
方案的执行效率比较低，加密１ ｂｉｔ 的明文对应 λ
５
ｂｉｔ 的密文
（λ 是安全参数），且公钥尺寸太大。 Ｓｍａｒｔ 等人
［７］
使用 Ｇｅｎｔｒｙ
的全同态加密思想，提出了具有相对较小的密钥和密文尺寸的
方案，提高了效率。 Ｓｔｅｈｌｅ 等人
［８］
对 Ｇｅｎｔｒｙ 的方案进行了优
化，以允许可忽略概率解密错误这一弱化条件，提出了较快速
的全同态加密方案，降低了比特计算复杂度。 目前，国内关于
全同态加密方案的论文还比较少，汤殿华等人
［９］
提出一种较
快速的整数上的全同态加密方案，相对文献［５］中方案具有更
短的公钥尺寸、更小的解密复杂度，并在文献［１０］中对 Ｇｅｎｔｒｙ
的全同态加密技术进行了总结。 虽然现在已经有很多改进的
全同态加密方案被提出来，但是这些方案的效率都很低。 Ｄｉｊｋ
等人
［５］
提出的整数上的加密方案，一次仅能加密１ ｂｉｔ 明文，且
对密文进行处理时，需要进行重加密，这将导致原本的１ ｂｉｔ 密
文变为一个大整数。 显然，改进全同态加密方案的执行效率是
未来全同态加密研究的重点与难点。
本文使用Ｇｅｎｔｒｙ 的全同态加密思想，对 Ｄｉｊｋ 等人提出的
整数上的全同态加密方案进行了改进。 将Ｄｉｊｋ 等人的方案中
的模２ 运算变为模４ 运算，并限制了部分参数的选取；在给出
新方案的噪声增长分析之后，使用 Ｇｅｎｔｒｙ 的全同态加密技术
得到一个全同态加密方案。 改进之后的方案一次可以加密２
ｂｉｔ 明文， 并使用文献［１１］ 中的技术将公钥尺寸缩小到
珟
Ο（λ
７
），显然改进之后的方案具有更高的效率和更小的公钥尺
寸。 方案的安全性基于近似最大公约数问题（ ａｐｐｒｏｘｉｍａｔｅ
ｇｒｅａｔｅｓｔ ｃｏｍｍｏｎ ｄｉｖｉｓｏｒ）和稀疏子集和问题。
第３０ 卷第５ 期
２０１３ 年５ 月　
计 算 机 应 用 研 究
Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ
Ｖｏｌ． ３０ Ｎｏ． ５
Ｍａｙ ２０１３