格上可编程杂凑函数的新构造*

摘要

2008年， Hofheinz和Kiltz在美密会(CRYPTO)上提出了可编程杂凑函数的概念。作为刻画了分割证明技术的密码原语，可编程杂凑函数是构造标准模型下可证明安全密码方案的有力工具。受到传统可编程杂凑函数的启发， Zhang等人在2016年美密会上提出了格上可编程杂凑函数的概念，并给出多个在标准模型下可证明安全密码方案的通用构造。本文继续研究基于格的可编程杂凑函数，并利用格上的伪交换性给出新的可编程杂凑函数的实例化构造。进一步，通过将新的可编程杂凑函数与传统有限猜测证明技术的结合，本文构造了基于格上困难问题可证明安全的数字签名方案。在技术上，本文的签名方案突破了Ducas和Micciancio基于理想格的签名方案(CRYPTO 2014)对于底层代数结构可交换性的依赖，并揭示了Ducas和Micciancio的证明技术可以无缝地平移到一般格上用于构造在标准模型下可证明安全的高效数字签名方案，从而在某种程度上解决了 Ducas和 Micciancio 遗留的公开问题。在效率上，本文的签名方案实现了对数的验证密钥长度和常数的签名长度，即验证密钥和签名分别只包含O(log)个矩阵和一个格向量，其中是签名消息的长度。%At CRYPTO 2008, Hofheinz and Kiltz proposed the concept of programmable hash function (PHF). As a primitive capturing the partitioning proof trick, PHF is a powerful tool to construct provably secure cryptographic schemes in the standard model. Inspired by the traditional PHF, at CRYPTO 2016, Zhang et al. studied the lattice-based PHF and showed several generic cryptographic constructions in the standard model. In this paper, we continue the study of lattice-based PHF, and propose a new instantiation of lattice-based PHF by using a property called “pseudo-commutativity” on general lattices. Moreover, we construct a new provably secure digital signature scheme based on hard lattice problems, by combining our new PHF with the traditional “confined guessing” technique. Technically, our scheme removes the requirements for the commutativity property on ideal lattices, which is crucial for the signature scheme of Ducas and Micciancio (CRYPTO 2014), and suggests that the techniques used by Ducas and Micciancio can be smoothly adopted to general lattices to construct signature schemes with security in standard model. With respect to the efficiency, our scheme achieves logarithmic verification keys (consisting ofO (logl)matrices, where is the message length) and short signatures (consisting of a single lattice vector).