格上可编程杂凑函数的新构造*??
2008年， Hofheinz和Kiltz在美密会(CRYPTO)上提出了可编程杂凑函数的概念。作为刻画了分割证明技术的密码原语，可编程杂凑函数是构造标准模型下可证明安全密码方案的有力工具。受到传统可编程杂凑函数的启发， Zhang等人在2016年美密会上提出了格上可编程杂凑函数的概念，并给出多个在标准模型下可证明安全密码方案的通用构造。本文继续研究基于格的可编程杂凑函数，并利用格上的伪交换性给出新的可编程杂凑函数的实例化构造。进一步，通过将新的可编程杂凑函数与传统有限猜测证明技术的结合，本文构造了基于格上困难问题可证明安全的数字签名方案。在技术上，本文的签名方案突破了Ducas和Micciancio基于理想格的签名方案(CRYPTO 2014)对于底层代数结构可交换性的依赖，并揭示了Ducas和Micciancio的证明技术可以无缝地平移到一般格上用于构造在标准模型下可证明安全的高效数字签名方案，从而在某种程度上解决了 Ducas和 Micciancio 遗留的公开问题。在效率上，本文的签名方案实现了对数的验证密钥长度和常数的签名长度，即验证密钥和签名分别只包含O(log?)个矩阵和一个格向量，其中?是签名消息的长度。
格、可编程杂凑函数、标准模型、数字签名
3
TP309.7(计算技术、计算机技术)
国家重点基础研究发展项目973计划2013CB338003;国家自然科学基金项目61602046
2016-11-22（万方平台首次上网日期，不代表论文的发表时间）
共14页
419-432
