ax+b mod p比特安全的列表译码证明

作者：谢小容; 吕克伟; 王鲲鹏

来源：系统科学与数学, 2012, 32(11): 1366-1376.

• 硬核谓词
• 列表译码
• 单向函数
• 比特安全 Hard-core predicate
• list decoding
• one-way function
• bit security

2003年Akavia基于列表译码提出研究硬核谓词的一般框架,并将该方法成功地应用于许多硬核谓词的研究.但是,对于ax+b mod p的任意比特是任意单向函数的硬核谓词,这个关于单向函数的一般性结论能否适用,仍是一个公开问题.文章利用这种新方法研究积性码可接近的单向陷门函数的比特安全性,并且证明ax+b mod p的任意比特是p阶循环群上该类单向函数的硬核谓词.

• 单位
  中国科学院信息工程研究所; 中国科学院研究生院; 信息安全国家重点实验室