The symmetric-key encryption scheme from [1] is based on the LPN (learning parity with noise) problem. The definition of the problem is, informally, that the adversary cannot recover $\mathbf{s}$ from $\mathbf{A} \cdot \mathbf{s} \oplus \mathbf{e}$ given $\mathbf{A}$, where $\mathbf{A}, \mathbf{s}$ and $\mathbf{e}$ are some random (public) matrix, the secret and the noise vector, respectively. The noise $\mathbf{e}$ is sampled from a Bernoulli distribution with parameter $\eta$.

My understanding is that typically $0 < \eta < 1/2$. But the lower $\eta$ is, the easier it is to break LPN (when $\eta$ is 0 LPN can be solved using Gaussian elimination). Suppose I need a security level of, for example, 80 bits, how do I select the value of $\eta$ if other parameters are fixed? I understand [1] provides some concrete parameters, but it's unclear to me how to calculate the security level from a concrete value of $\eta$.

[1] https://link.springer.com/chapter/10.1007/978-3-540-70583-3_55


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.