Short version:
Are there some results that are known on the security of the Learning With Error problem when there are some leakages, notably on the noise? (In my case these leakages come from a bit that is leaked after successful decryption.) More precisely, if I have a bit string $d_0$ and if I give an encrypted version of this string $y_0 := A s_0 + e_0 + q/2 \begin{pmatrix}d_0 & 0 \dots 0\end{pmatrix}$ to an adversary, what can this adversary learn about $d_0$ if he is allowed to learn at most $\log(n)$ bits of information (it may be about the noise $e_0$, or even about $d_0$ or about the trapdoor of $A$ directly since I don't have an argument to say why these bits couldn't be about $d_0$...)? Can we say more things if we know that this information comes from the fact that a $y$ chosen by an adversary can be decrypted?
Long version:
I have a protocol whose security boils down to the security of the following "game":
- Alice (honest) sends an "encryption" of a bit string $d_0 \in \{0,1\}^n$ to Bob (malicious and having access to a quantum computer) whose security is based on LWE. More precisely, she sends a matrix $A$ and a vector $y_0 := As_0+e_0 + q/2\begin{pmatrix}d_0 & 0 \dots 0\end{pmatrix})$, where $A$ is a matrix of elements in $\mathbb{Z}_q$, $s_0$ is a random vector, and $e_0$ is a "noise" vector with small elements.
- Bob sends a message $y$ back to Alice.
- Alice decrypts this $y$ into $y = As + e + q/2 \begin{pmatrix} d & 0 & \dots & 0\end{pmatrix}$, and may abort (basically she aborts if $y$ has a too large noise $e$ or if $e-e_0$ is also too large, i.e. if $||e||_\infty \geq \mu$ or if $||e-e_0||_\infty \geq \mu$ for some $\mu$... but if possible I'd like to make a few assumption as possible on the properties of the abort to get a more general result and to simplify the analysis. Indeed, I've got the feeling that the main property we need is that the probability of not aborting is not negligible). If she aborts, she tells it, Bob, for example by sending a bit $a = 0$, while if on the contrary, she accepts the run, she sends $a=1$.
- If the protocol didn't abort, Alice also sends a challenge $m$ (for "mask") to Bob in order to do a kind of privacy amplification, and extract one bit. The goal of Bob is to output $m \oplus d_0 := \sum_i m[i] \oplus d_0[i] \mod 2$.
Now, I'd like to prove that there exists no (quantum) polynomially bounded Bob such that:
- the probability of having an accepted run is $\geq \frac{1}{poly(n)}$ (if needed I can also make it constant I think)
- when Alice accepts the run, then Bob cannot win with a non-negligible advantage, i.e. the probability of winning is $\leq \frac{1}{2} + \frac{1}{negl(n)}$
Intuitively, I have the feeling that the above game is secure, since as soon as Bob has a non-negligible probability of being accepted by Alice, he can extract only a polynomial amount of information about $d$, and therefore he should not have enough information about $d$ to be able to answer to a random challenge $m$. Actually, I think that the leftover hash lemma could be used to prove the security of the protocol if we were able to remove the message $y_0$ from Alice to Bob. But the issue is that since the abort probability depends on the encryption $y_0$, I don't think that the semantic security of our encryption scheme is enough to allow us to replace $y_0$ with encryption of $0$...
So here is my question: do you know some tools (generic theorems, or results related explicitly to LWE) that could help me to prove the security of this game? Notably, is it known that LWE is still somehow secure when there are some leakages on the noise, or when we are given single shot access to an oracle that can say if decryption was successful or not? Are there some methods to prove that the probability of aborting is independent of the value of $d_0$? For now, I tried to look at lossy functions, but my main issue is that since Alice needs to decrypt a message at some point and give some information to Bob on whether she succeeded or not, it's not clear to me what we should do in case of lossy functions... All the methods I know based on indistinguishability fail if at some point we are allowed to decrypt a message...
Sorry if my statement can't be made more precise at that point, and feel free to give any reference/tool that may be close or not to that issue. Thanks a lot!
