Solving the learning parity with noiseʼs open question

• This paper solves the open question about the hardness of the LPN assumption when the secret key is leaked.
• We show that the leaked key LPN is not easier than the standard LPN.
• The leaked key LPN remains secure but the security parameter is reduced to the secret keyʼs min-entropy.
• The noise parameter for the Bernoulli distribution is also reduced, that is similar to the case of LWE.
• We also show that the LPN based symmetric encryption scheme is robust.

The classical cryptographic primitives are constructed on the assumptions that the private key is securely kept and uniformly distributed. Learning parity with noise is a famous problem used to construct several cryptographic primitives. This research studies the open question about the hardness of the learning parity with noise assumption when the secret vector is not uniform and has sufficient min-entropy. The proofs show that the standard learning parity with noise implies that it is secure even if the secret vector is sampled from an arbitrary distribution with sufficient entropy. Furthermore, this paper shows that the symmetric encryption scheme from learning parity with noise is secure even if the secret key has min-entropy at least k.