Timeline for Computational indistinguishability of two LWE type samples
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 16, 2022 at 7:47 | comment | added | Daniel S | I suggest we move discussion to this chat room. | |
| Apr 16, 2022 at 5:46 | comment | added | Morbius | *We are distinguishing between $A(x + s_2 + \cdots + s_k) + (e_2 + \cdots + e_k + e')$ and $u$.... | |
| Apr 16, 2022 at 5:36 | comment | added | Morbius | How can that be true? Let's say only $b_1 = 0$. Then, we are essentially distinguishing between $A(x + s_2 + s_3 + \cdots + s_k) + (e_1 + e_2 + \cdots + e_k) + e'$ and $u$. Isn't that just a variant of LWE? So, do we not need every $b_i$ to be $0$ for the samples to be distinguishable and not just at least one $b_i$ to be $0$? | |
| Apr 15, 2022 at 5:52 | comment | added | Daniel S | No, the argument is that if at least $b_i$ is 0, the set is easily distinguishable | |
| Apr 15, 2022 at 0:43 | vote | accept | Morbius | ||
| Apr 15, 2022 at 0:42 | comment | added | Morbius | The argument is just that when every $b_i$ is $0$, they are easily distinguishable, but such a case is exponentially unlikely. For every other case, for any choice of $k$, we can reduce it to LWE. | |
| Apr 15, 2022 at 0:39 | comment | added | Morbius | Just to sanity check, if there were polynomially many samples from either \begin{equation} (x, b_1, b_2, \ldots, b_k, ~Ax + b_1\cdot(As_1 + e_1) + b_2\cdot(As_2 + e_2) + \cdots + b_k\cdot(As_k + e_k) + e') ~~\text{or}~~\left(x, b_1, b_2, \ldots, b_k, u \right), \end{equation} for $b_i \in \{0, 1\}$, for a polynomially large $k$ and for secret vectors $s_1, \ldots, s_k$, then these will be indistinguishable, is that right? | |
| Apr 14, 2022 at 17:16 | history | edited | Daniel S | CC BY-SA 4.0 |
added 3 characters in body
|
| Apr 14, 2022 at 17:00 | history | edited | Daniel S | CC BY-SA 4.0 |
added 159 characters in body
|
| Apr 14, 2022 at 16:56 | history | answered | Daniel S | CC BY-SA 4.0 |