基于SIS的同态陷门函数的新算法及其应用

摘要

云计算与大数据的发展对数据的存储与分析提出了更高的要求，云计算的安全与密码学息息相关，同态密码能够分析和处理经过系统加密过的数据，为数据的存储与分析提供了保证。常见的同态加密支持密文的加法和乘法运算，使其满足云计算环境下的多种计算方式的要求。最近几年，越来越多的人对云计算环境下数据计算的认证越来越感兴趣，同态签名可以实现云环境下不泄漏信息的消息认证。
　　电子信息技术发展对密码体制的安全性要求越来越高，这也催生了量子等新型信息技术建立和发展。量子信息技术研究加快了量子计算机和量子密码体制的发展，抗量子计算公钥密码也成为当下一个研究的热点问题。格密码体制是密码学研究的一个重要领域，由于格的密码体制安全性基于NP-Hard或者NP-C问题，使得格密码被普遍认为是抗量子攻击的公钥密码体制之一。
　　Gorbunov，Vaikuntanathan和Wichs[1]提出基于格上SIS问题的同态陷门函数(HTDF)，他们基于HTDF构造了同态签名方案。对一个同态陷门函数，已知HTDF的公钥，l个消息x:(x1，x2，…，xl)的签名(σ):=（σ1，σ2，…，σl），存在有效的算法计算电路g(x)的签名σ'.对于同态陷门函数，其安全性是基于格上的最小整数解(SIS)问题，在Gorbunov-Vaikuntan-athan-Wichs的同态签名方案中，基于信息熵证明了HTDF的安全性，在签名方案的设计中，电路的深度d是提前设置的，同态运算的的噪音增长依赖于输入x1和电路g，同态运算的噪音的界为2O(logλ)·d.
　　基于格的同态密码体制不但在云计算环境下密文的检索，数据的存储与验证具有潜在的价值，而且是抵抗量子攻击的。在这篇文章中，主要研究的内容:
　　工具矩阵(Gadget)陷门的应用使得格密码方案中的陷门生成算法更加容易。已经证明:关于工具矩阵的最小整数解问题是容易的。对于均匀随机选取整向量v，工具矩阵G，存在有效的求逆算法G-1找到短的向量u满足:Gu=v.文章中充分应用工具矩阵的求逆算法定义一种新的运算法则，使得签名的噪音增长呈多项式的，很大程度改进了原文电路深度的范围，对于设计全同态签名方案具有重要的意义。
　　用工具矩阵的性质提出一个更简单的HTDF的安全性证明，并分析随机预示模型下的同态签名方案的安全性。新的同态运算法则使得签名方案的的同态性质更好。同态运算所得到的签名的噪音U*的界为O（poly（λ））d.

目录

声明

摘要

符号说明

第一章 绪论

§1．1 研究背景及意义

§1．2 本文结构安排

第二章 背景知识

§2．1 密码学相关定义

§2．2 格相关知识

§2．3 离散高斯分布

§2．4 工具矩阵

§2．5 本章小结

第三章 同态陷门函数

§3．1 定义

§3．2 同态运算

3．2．1 Wichs的同态计算

3．2．2 新的同态计算方法

§3．3 同态陷门函数的应用

3．3．1 签名

3．3．2 安全性

§3．4 本章小结

第四章 总结与展望

参考文献

致谢