An Automatic Analysis Approach Toward Indistinguishability of Sampling on the LWE Problem  

作　　者：Shuaishuai Zhu Yiliang Han Xiaoyuan Yang 

机构地区：[1]the College of Cryptography Engineering,Engineering University of People's Armed Police,Xi'an 710086,China [2]the Key Laboratory of Network and Information Security under the People's Armed Police,Engineering University of People's Armed Police,Xi'an 710086,China

出　　处：《Tsinghua Science and Technology》2020年第5期553-563,共11页清华大学学报（自然科学版（英文版）

基　　金：supported by the National Natural Science Foundation of China(Nos.61572521 and U1636114);the National Key Project of Research and Development Plan(No.2017YFB0802000);the Innovative Research Team Project of Engineering University of PAP(No.KYTD201805);the Fundamental Research Project of Engineering University of PAP(No.WJY201910)。

摘　　要：Learning With Errors (LWE) is one of the Non-Polynomial (NP)-hard problems applied in cryptographic primitives against quantum attacks.However,the security and efficiency of schemes based on LWE are closely affected by the error sampling algorithms.The existing pseudo-random sampling methods potentially have security leaks that can fundamentally influence the security levels of previous cryptographic primitives.Given that these primitives are proved semantically secure,directly deducing the influences caused by leaks of sampling algorithms may be difficult.Thus,we attempt to use the attack model based on automatic learning system to identify and evaluate the practical security level of a cryptographic primitive that is semantically proved secure in indistinguishable security models.In this paper,we first analyzed the existing major sampling algorithms in terms of their security and efficiency.Then,concentrating on the Indistinguishability under Chosen-Plaintext Attack (IND-CPA) security model,we realized the new attack model based on the automatic learning system.The experimental data demonstrates that the sampling algorithms perform a key role in LWE-based schemes with significant disturbance of the attack advantages,which may potentially compromise security considerably.Moreover,our attack model is achievable with acceptable time and memory costs.Learning With Errors (LWE) is one of the Non-Polynomial (NP)-hard problems applied in cryptographic primitives against quantum attacks.However,the security and efficiency of schemes based on LWE are closely affected by the error sampling algorithms.The existing pseudo-random sampling methods potentially have security leaks that can fundamentally influence the security levels of previous cryptographic primitives.Given that these primitives are proved semantically secure,directly deducing the influences caused by leaks of sampling algorithms may be difficult.Thus,we attempt to use the attack model based on automatic learning system to identify and evaluate the practical security level of a cryptographic primitive that is semantically proved secure in indistinguishable security models.In this paper,we first analyzed the existing major sampling algorithms in terms of their security and efficiency.Then,concentrating on the Indistinguishability under Chosen-Plaintext Attack (IND-CPA) security model,we realized the new attack model based on the automatic learning system.The experimental data demonstrates that the sampling algorithms perform a key role in LWE-based schemes with significant disturbance of the attack advantages,which may potentially compromise security considerably.Moreover,our attack model is achievable with acceptable time and memory costs.

关 键 词：lattice-based cryptography learning with errors security model Non-Polynomial(NP)-hard problems 

分 类 号：O413[理学—理论物理] TN918.4[理学—物理]