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

《整数上的全同态加密方案的改进.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３０卷第５期计算机应用研究Ｖｏｌ．３０Ｎｏ．５２０１３年５月ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓＭａｙ２０１３整数上的全同态加密方案的改进林如磊，王箭，杜贺（南京航空航天大学计算机科学与技术学院，南京２１００１６）摘要：目前的全同态加密方案的效率还很低，与实际的应用还有很大的距离，提高全同态加密方案的效率和安全性是全同态加密技术研究的重点与难点。为了提高效率，在Ｄｉｊｋ等人的全同态加密方案的基础上，将模２运算改为模４运算，并使用Ｇｅｎｔｒｙ的全同态思想，提出了一种更快速的全同态加密方案，改进之后的方案

2、一次可７以加密２ｂｉｔ的数据，且公钥尺寸降低到Ο珟（λ），从而比Ｄｉｊｋ等人的方案具有更高的效率和更小的公钥尺寸。新方案的安全性基于近似最大公因子问题和稀疏子集和问题。关键词：全同态加密；近似最大公因子问题；稀疏子集和问题；公钥尺寸中图分类号：ＴＰ３０９文献标志码：Ａ文章编号：１００１３６９５（２０１３）０５１５１５０５ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１３６９５．２０１３．０５．０６０ＩｍｐｒｏｖｅｄｆｕｌｌｙｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎｏｖｅｒｉｎｔｅｇｅｒｓＬＩＮＲｕｌｅｉ，ＷＡＮＧＪｉａ

3、ｎ，ＤＵＨｅ（ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，ＮａｎｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＡｅｒｏｎａｕｔｉｃｓ＆Ａｓｔｒｏｎａｕｔｉｃｓ，Ｎａｎｊｉｎｇ２１００１６，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅｐｒｅｓｅｎｔｆｕｌｌｙｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎｓｃｈｅｍｅｉｓｅｘｔｒａｌｏｗａｎｄｆａｒｆｒｏｍｐｒａｃｔｉｃａｌａｐｐｌｉｃａｔｉｏｎ．Ｈｏｗｔｏｉｍｐｒｏｖｅｔｈｅｅｆｆｉｃｉｅｎｃｙａｎｄｓｅｃｕｒｉｔｙｏｆｆｕｌｌｙｈｏｍｏｍｏｒｐｈｉ

4、ｃｅｎｃｒｙｐｔｉｏｎｂｅｃｏｍｅｔｈｅｆｏｃｕｓａｎｄｐｉｔｆａｌｌｏｆａｃａｄｅｍｉｃｒｅｓｅａｒｃｈ．Ｉｎｏｒｄｅｒｔｏｉｍｐｒｏｖｅｔｈｅｅｆｆｉｃｉｅｎｃｙ，ｔｈｉｓｐａｐｅｒｐｕｔｆｏｒｗａｒｄａｎｉｍｐｒｏｖｅｄｓｃｈｅｍｅｏｆｔｈｅｂａｓｅｏｆＤｉｊｋ’ｓｓｃｈｅｍｅｕｓｉｎｇＧｅｎｔｒｙ’ｓｆｕｌｌｙｈｏｍｏｍｏｒｈｐｉｃｔｅｃｈｎｏｌｏｇｙ．Ｔｈｅｉｍｐｒｏｖｅｄｓｃｈｅｍｅｃｏｕｌｄｅｎｃｒｙｐｔ２ｂｉｔｐｌａｉｎｔｅｘｔｅａｃｈｔｉｍｅａｎｄｒｅｄｕｃｅｔｈｅｐｕｂｌｉｃｋｅｙｓｉｚｅｔｏΟ珟（λ７），ａ

5、ｃｃｏｒｄｉｎｇｌｙｔｈｅｉｍｐｒｏｖｅｄｓｃｈｅｍｅｗａｓｍｏｒｅｅｆｆｉｃｉｅｎｔｔｈａｎＤｉｊｋ’ｓｓｃｈｅｍｅａｎｄｈａｄｓｍａｌｌｅｒｐｕｂｌｉｃｋｅｙｓｉｚｅ．ＴｈｅｓｅｃｕｒｉｔｙｏｆｔｈｅｐｒｏｐｏｓｅｄｓｃｈｅｍｅｗａｓｂａｓｅｄｏｎｂｏｔｈｔｈｅａｐｐｒｏｘｉｍａｔｅＧＣＤｐｒｏｂｌｅｍａｎｄｔｈｅｓｐａｒｓｅｓｕｂｓｅｔｓｕｍｐｒｏｂｌｅｍ．Ｋｅｙｗｏｒｄｓ：ｆｕｌｌｙｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎ；ａｐｐｒｏｘｉｍａｔｅＧＣＤ；ｓｐａｒｓｅｓｕｂｓｅｔｓｕｍｐｒｏｂｌｅｍ；ｐｕｂｌｉｃｋｅｙ

6、ｓｉｚｅ［８］方案，提高了效率。Ｓｔｅｈｌｅ等人对Ｇｅｎｔｒｙ的方案进行了优!引言化，以允许可忽略概率解密错误这一弱化条件，提出了较快速［１］［２］的全同态加密方案，降低了比特计算复杂度。目前，国内关于１９７８年，在ＲＳＡ密码体制刚刚提出不久，Ｒｉｖｅｓｔ等人［９］全同态加密方案的论文还比较少，汤殿华等人提出一种较提出了全同态加密的概念（又叫隐私同态，ｐｒｉｖａｃｙｈｏｍｏｍｏｒ快速的整数上的全同态加密方案，相对文献［５］中方案具有更ｐｈｉｓｍｓ），并认为全同态加密技术是可以实现的，同时提出了几短的公钥尺寸、更小的解密复杂度，

7、并在文献［１０］中对Ｇｅｎｔｒｙ种候选的同态加密方案。他们希望在不对密文解密的条件下，的全同态加密技术进行了总结。虽然现在已经有很多改进的对密文进行任何运算，得到的结果解密后与对明文进行相应运全同态加密方案被提出来，但是这些方案的效率都很低。Ｄｉｊｋ算的结果相同。全同态加密思想提出之后，国内外的研究人员［５］等人提出的整数上的加密方案，一次仅能加密１ｂｉｔ明文，且以及学者对全同态加密进行了大量的研究，然而他们提出的方对密文进行处理时，需要进行重加密，这将导致原本的１ｂｉｔ密案都只能对密文进行有限次同态运算，没有达到真正的全文变为

8、一个大整数。显然，改进全同态加密方案的执行效率是同态。未来全同态加密研究的重点与难点。第一个全同态加密（ｆｕｌｌｙｈｏｍｏｍｏｒｐｈｉｓｍｅｎｃｒｙｐｔｉｏｎ）方案是本文使用Ｇｅｎｔｒｙ的全同态加密思想，对Ｄｉｊｋ等人提出的［３］ＩＢＭ研究员Ｇｅｎｔｒｙ在２００