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

摘要

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