Rényi divergence on learning with errors

• 作 者: Yang TAO Han WANG Rui ZHANG
• 机 构: State Key Laboratory of Information Security, Institute of Information Engineering,Chinese Academy o
• 出 处: 中国科学：信息科学（英文版）
• 发表日期: 2020年9期
• 关键词: Rényi divergence learning with errors decision problems search problems post-qua

Many lattice-based schemes are built from the hardness of the learning with errors problem,which naturally comes in two flavors: the decision LWE and search LWE.In this paper,we investigate the decision LWE and search LWE by Rényi divergence respectively and obtain the following results: For decision LWE,we apply RD on LWE variants with different error distributions (i.e.,center binomial distribution and uniform distribution,which are frequently used in the NIST PQC submissions) and prove the pseudorandomness in theory.As a by-product,we extend the so-called public sampleability property and present an adaptively public sampling property to the application of Rényi divergence on more decision problems.As for search LWE,we improve the classical reduction proof from GapSVP to LWE.Besides,as an independent interest,we also explore the intrinsic relation between the decision problem and search problem.