常量噪声下带辅助输入的LPN公钥密码

• 作者: 程海涛 钱海峰 韩刚
• 来源期刊: 密码学报
• 学科: 工学
• 关键词: LPN问题 后量子公钥密码 辅助输入 选择明文攻击 公钥密码
• 年，卷（期）: 2017,（5）
• 所属期刊栏目: 后量子密码专栏
• 页码范围: 506-516
• 页数: 11页
• 分类号: TP309.7
• 字数: 8821字
• 语种: 中文
• DOI: 10.13868/j.cnki.jcr.000202

摘要

在STOC 2009上,Dodis,Kalai和Lovett研究了(静态的)带有指数级难以求逆辅助输入的LPN(Learning Parity with Noise)问题的困难性,他们通过引入一个新的假设(被称为带噪声的子空间学习问题,Learning Subspace with Noise)证明了LPN问题在高噪声条件下是准多项式(quasi-polynomial)困难的,然而他们的结果并未在LPN的标准假设下得到证明.本文将介绍Yu(ePrint 2009/467)以及Goldwasser等人在ITCS 2010上提出的"从子空间中取样(sampling from subspace)"技术,利用该技术Yu等人(CRYPTO 2016)证明了标准LPN蕴含了一种新的健壮的(抗泄漏)工作模式.换而言之,常量噪声(constant-noise)的LPN在带有亚指数级难以求逆的辅助输入时仍具有与标准LPN假设下可比拟的安全性.更进一步,在亚指数级困难(即2ω(n1/2)),n为密钥大小)常量噪声LPN假设下,Yu等人(CRYPTO 2016)基于poly-logarithmic熵源得到一种LPN问题变体,并进一步构造CPA/CCA安全公钥加密(PKE)方案和不经意传输(oblivious transfer,OT)协议,从而证明了标准LPN蕴含公钥加密.在此之前(特别是自Alekhnovich发表在FOCS 2003的工作以来),如何在常量噪声LPN假设下构造PKE和OT一直是未解决的公开问题.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	钱海峰	华东师范大学计算机科学技术系	19	83	5.0	8.0
2	程海涛	华东师范大学计算机科学技术系	1	0	0.0	0.0
3	韩刚	西北工业大学电子信息学院	6	14	3.0	3.0