基于短整数解问题的伪随机函数新构造

New pseudorandom functions based on SIS

伪随机函数是构造密码原型的重要工具。基于短整数解问题,在格上设计出2个伪随机函数,第一个利用树状伪随机综合器的思想,达到并行化效果,第二个虽是串行构造,但降低了公钥尺寸。二者均具有小模数,而且是可证明安全的。与A Banerjer,C Peikert和A Rosen 3人提出的方案(EUROCRYPT 2012)相比,此提出的伪随机函数具有渐少的密钥量;在构造方法上,由于避免了凑整技术的使用,伪随机函数的生成效率得到了提高。

Pseudorandom functions are vital tools in the construction of cryptographic primitives. Under the hard as-sumption of SIS （short integer solution）, two lattice-based pseudorandom functions are proposed. The first one has paral-lel structure by the ideal of tree-like pseudorandom synthesizer, and the second one is serial structure whose public keysize is reduced. Both constructions have small modulus and provable security. Compared with A Banerjer, C Peikert andA Rosen＇s construction （EUROCRYPT 2012）, their key sizes are asymptotically smaller, and efficiency are improved byavoiding the ＂rounding＂ technology.