摘要
伪随机函数是密码学领域最基本的原语之一,其自提出以来便备受关注.近几十年间发展起来的格理论在密码领域取得了很多重要的应用成果,特别是格上很多困难问题被普遍认为具备抵抗量子攻击的特性,在后量子密码方案设计中处于核心地位.对于格上伪随机函数的研究正式起始于Banerjee、Peikert和Rosen在2012年欧密会上发表的工作.此后,密码学家们围绕如何基于格困难问题设计伪随机函数方案开展了大量研究,特别是在提升伪随机函数方案的安全性、效率和并行性,以及扩展伪随机函数的功能方面取得了诸多成果.本文对格上伪随机函数的研究现状进行综述:总结了伪随机函数的通用构造方法以及格上伪随机函数依赖的底层困难问题;整理了现有基于格困难问题设计的伪随机函数方案,重点关注这些方案在提升安全性、效率或并行性方面采用的技术以及取得的成果;整理了格上具备扩展功能的伪随机函数的研究进展,包括具有密钥同态性质的伪随机函数、约束伪随机函数、水印伪随机函数以及可验证伪随机函数.
Abstract
Serving as one of the fundamental primitives in the field of cryptography,pseudorandom function(PRF)has received much attention since its introduction.Past decades of years witnessed the blossom of lattice theory,and it has found important applications in cryptography,many lattice based hard problems are widely believed to be intractable even against quantum algorithms,and play core roles in designing post-quantum cryptographic schemes.The study of lattice-based PRFs started from the breakthrough work proposed by Banerjee,Peikert and Rosen at EUROCRYPT 2012.Since then,cryptographers have conducted extensive researches focusing on designing PRFs from hard lattice problems,and have made much progress in improving the security,efficiency and parallelism of PRFs,as well as extending functionalities of PRFs.This paper surveys recent studies of lattice-based PRFs:introduces widely used generic constructions as well as lattice-based hard problems in designing PRFs.This paper summarizes existing lattice-based PRFs,especially their techniques and achievements in improving the security,efficiency and parallelism,traces the researches on lattice-based PRFs with extended functionalities,including the key-homomorphic PRFs,constrained PRFs,watermarkable PRFs and verifiable random functions.
基金项目
广东省基础与应用基础研究重大项目(2019B030302008)
国家自然科学基金(61925207)
国家重点研发计划(2022YFB2701500)
国家科技期刊平台
NSTL
万方数据