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.
computational complexity cryptography learning parity with noise min-entropy