ax＋bmodp比特安全的列表译码证明  

PROVING THE SECURITY OF ALL BITS OF ax + b mod p USING LIST DECODING

作　　者：谢小容[1] 吕克伟[2] 王鲲鹏[2] 

机构地区：[1]中国科学院研究生院信息安全国家重点实验室,北京100049 [2]中国科学院信息工程研究所信息安全国家重点实验室,北京100195

出　　处：《系统科学与数学》2012年第11期1366-1376,共11页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金(60970154,60970153)资助项目;中国科学院战略性先导专项,子课题海运信息安全共性关键技术研究(XDA06010702)

摘　　要：2003年Akavia基于列表译码提出研究硬核谓词的一般框架,并将该方法成功地应用于许多硬核谓词的研究.但是,对于ax+b mod p的任意比特是任意单向函数的硬核谓词,这个关于单向函数的一般性结论能否适用,仍是一个公开问题.文章利用这种新方法研究积性码可接近的单向陷门函数的比特安全性,并且证明ax+b mod p的任意比特是p阶循环群上该类单向函数的硬核谓词.In 2003, Akavia, et al. introduced a unifying framework to study the hard- core predicates using list decoding and succeeded in the the study of many hard-core predicates. However, it is still an open question whether the general result that any bit of ax ＋ bmodp is a hard-core predicate for any one-way function can be proved by list decoding. In this paper, we utilize this new idea to study the security of one-way function with multiplicative access, and prove that any bit of ax ＋ bmodp is a hard-core predicate for any one-way function defined on a cyclic group of order p with multiplicative access for prime p.

关 键 词：硬核谓词 列表译码 单向函数 比特安全 

分 类 号：TN918.1[电子电信—通信与信息系统]