We are given the problem in this question.

We know that we have to use the algorithm $A_D$ in order to get $e_i$. Our idea is that we construct a vector $l$ of $l_i$'s by getting $n$ samples from the $LPN$ oracle and construct a suitable parity check matrix $P \in \mathbb{F}_2^{(n-k)\times n}$ with which we can then input the syndrome $P\times l^t$ and the $P$ and get returned the value of $e$.

We wonder right now how the code is defined for which we will construct the parity check matrix as well as how to construct it.

Additionally we got the tip that we have to think about when exactly the parity cehck matrix exists and if so, if it is efficently computable.


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.