[February 3rd 2025] Public-key encryption

[Exyss]

[cornflexxx]

(Sketch) From a worst case $(A,b)$ instance we can get a random instance with the following transformation :
Sample random vector $s' \leftarrow{\mathbb{Z}_q^n}$

$$ (A,b' = b + As') = (A , b' = As + e + As') = (A, b' = A(s + s') + e \mod q)$$

so the solution is $s'' = s + s'$, hence it is randomly distributed instance ( since we're adding over $\mathbb{Z}_q$). Now on average with $\mathcal{A}$ we can get correct $s''$ w.p. $\ge 0.1$, and extract $s = s'' - s'$. To get the $0.99$ we can apply error reduction, i.e. repeat the above process many times (constant) and output the most common $s = s''- s'$. (To reduce the error we can apply either Chebyshev or Chernoff, both works in that case). (Edit: the error reduction can't work in this case , the probability is too low- strictly less than $1/2$ -and there's no deterministic way to verify the correctness of the solution we find at each run)