密码学报2016，Vol.3Issue(5)：419-432,14.DOI:10.13868/j.cnki.jcr.000140
格上可编程杂凑函数的新构造*
New Construction of Lattice-based Programmable Hash Function
摘要
Abstract
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).关键词
格/可编程杂凑函数/标准模型/数字签名Key words
lattices/programmable Hash functions/standard model/digital signatures分类
信息技术与安全科学引用本文复制引用
张江..格上可编程杂凑函数的新构造*[J].密码学报,2016,3(5):419-432,14.基金项目
国家重点基础研究发展项目(973计划)(2013CB338003) （973计划）
国家自然科学基金项目(61602046) （61602046）
