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.
