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.

  • 2
    $\begingroup$ 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? $\endgroup$
    – kelalaka
    Commented Jun 15, 2020 at 19:56
  • $\begingroup$ @kelalaka Thanks for the tip. I expanded my question with more info and my thoughts :) $\endgroup$
    – Pg1234
    Commented Jun 15, 2020 at 21:36
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Mark Schultz-Wu
    Commented Jun 19, 2020 at 0:43


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.