# Solving LPN using algorithm for syndrome decoding

Given an algorithm $$A_D$$ which solves an instance of the decoding problem $$e \in \mathbb{F}_2^n$$ in time $$T_D$$ given a parity check matrix $$H \in \mathbb{F}_2^{(n-k)\times n}$$ and a syndrome $$s \in \mathbb{F}_2^n$$.

You are also given a LPN-oracle with error-probability $$\tau$$.

Construct an algorithm which solves the LPN-problem with complexity $$\tilde O(T_D)$$.

Expanding on this question because of a friendly piece of advice from @kelalaka:

The decoding problem is defined as:

Given the parity check matrix $$P \in \mathbb{F}_2^{(n-k)\times n}$$, $$\omega$$ and $$x=c+e$$ with $$c \in C$$ and $$\mathrm{wt}(e)=\omega$$, find $$e \in \mathcal{F}_2^n$$.

The LPN is defined as:

Given $$x_i \in \mathbb{F}_2^n$$, $$l_i=\langle x_i,s\rangle+e$$, $$i \in [m]$$, $$\Pr[e_i=1]=p$$, $$p \in [0,1/2)$$, find $$s \in \mathcal{F}_2^n$$.

My progress:

To be really honest I have trouble understanding the whole topic and because of COVID remote teaching it is really hard to ask for help.

My first idea would be to use $$l_i$$ as $$x$$ in the algorithm $$A_D$$ and construct a fitting parity check matrix in order to get $$e_i$$ which I can then use to get the value of $$\langle x_i,s\rangle$$ and since I already know $$x_i$$ I am now able to extract $$s$$. But this won't work because I don't think there is a way for finding a unique solution for $$s$$ knowing $$e_i$$, $$l_i$$ and $$x_i$$.

I think I need to also use the error probability $$\tau$$, but am too confused right now to think of anything promising.

• Welcome to Cryptography. This seems a pure homework dump with no effort. As such cases, this is going to be closed. What have you tried where did you stuck? – kelalaka Jun 15 '20 at 19:56
• @kelalaka Thanks for the tip. I expanded my question with more info and my thoughts :) – Pg1234 Jun 15 '20 at 21:36
• The following is how I personally like to think about it, and makes the situation clearer (to me at least). View the $x_i$ as column vectors. Define $X\in\mathbb{F}_2^{n\times m}$ as these column vectors concatenated together, i.e. $X = [x_1,\dots, x_m]$. One can then view then LPN problem as recovering $s$ given $(X, s^t X + e) \in \mathbb{F}_2^{n\times m}\times \mathbb{F}_2^m$. – Mark Jun 19 '20 at 0:43