The Research On The Robustness Of Learning Parity With Noise

Quantum computer is a kind of physical device that follows the laws of quantum mechanics.It can be used for high-speed mathematical and logical operation,storage and processing of quantum information.With the deepening of the research of quantum computer,it is found that if the quantum computer is built successfully,most of the existing public cryptographic systems will be broken.Under these circumstances,although the first quantum computer has not yet been born,the study on the cryptographic systems which is secure under quantum computers has begun.Learning parity with noise(LPN)is a famous problem in learning theory and cryptography and it is useful in constructing various lightweight cryptographic primitives.The most important thing is that in cryptography Learning parity with noise(LPN)is secure even in a quantum computer model,so it has attracted a lot of attention recently.The scientific researchers not only study applications of learning parity with noise(LPN),but also study its hardness in depth.There 're previous results that were established by Dodis,Kalai and Lovett(STOC 2009)that the LPN problem is robust on high-entropy secrets under non-standard hard learning assumptions.Recently,Suttichaya and Bhattarakosol claimed that LPN is provable secure(reducible from the LPN assumption itself)even when the secret remains any linear amount of min-entropy and thus resolves the long-standing open problem.However,in Suttichaya and Bhattarakosol s proof which is to prove that non-standard as-sumption LPN(?)implies standard assumption LPN(?)some of the steps in the process are incorrect.(n,l? Z+is secrurity parameter.D is a distribution over Z2l with min-entropy k ?l.?,??[0,0.5]is noise parameter.In LPN assumption,l and n are the secret lenght,1/2-(1/2-?)(1-?)n adn 1/2-(1-?)n/2 are noise rate)Then,Suttichaya and Bhattarakosol's proof that a symmetric encryption scheme in a non-standard LPN assumption is CPA secure is not true is not established based on the above conclusions(in fact,not proven).The main contribution of this paper is to point out the flaws of proof by Suttichaya and Bhattarakosol.It is shown below:1.The noise rate is not reasonable above.To be applied to encryption,the noise rate should be bounded away from uniform at least polynomially.2.BC is sampled from a random subspace of dimension n<k<l and thus far from being uniform over {0,1?m×l(recall that m>>l).Every entry of matrix EF is distributed to Ber1/2-(1-?)n/2 for(1-?)n/2?1/poly(l)(see item 1 above).Therefore,A=BC(?)EF is not statistically close to uniform.3.Suttichaya and Bhattarakosol prove that every entry of EF is distributed according to Ber1/2-(1-?)n/2 and then conclude that EF follows Ber1/2m×l-(1-?)n/2,which is not true since there 's no guarantee that the entries of EF are all independent.This paper not only point out that Suttichaya and Bhattarakosol s proof is fatally flawed and their understanding about the problem is erroneous,but also offer a remedy with some slight adaption to the problem setting useing "from random subspace sampling "(ICS 2010).After we solve the open problem,we find out two application schemes with CPA security based on the conclusions of this paper.