Randomness re-use in LWE encryption scheme Let me describe the scheme first, it is the scheme proposed by O. Regev when he introduced the LWE assumption.


$sk = \textbf{s} \in \mathbf{Z}_q^n$
$pk = \textbf{A}\textbf{s}+\textbf{e}$ where $\textbf{A}\in \mathbf{Z}_q^{m\times n}$ and $\textbf{e}\leftarrow \chi^m$
$ct=(\mathbf{r}\mathbf{A},\mathbf{r}pk+\lfloor \frac{q}{2} \rceil x)$ where $\mathbf{r} \leftarrow \{0,1\}^m$ and $x$ is the message


I know that this scheme is secure under randomness reuse, that is for 2 different messages $\mathbf{x}_1$ and $\mathbf{x}_2$ and secret keys $\mathbf{s}_1$ and $\mathbf{s}_2$, the following scheme is secure against chosen plaintext attacks:


$ct = (\mathbf{r}\mathbf{A},\mathbf{r}pk_1+\lfloor \frac{q}{2} \rceil x_1,\mathbf{r}pk_2+\lfloor \frac{q}{2} \rceil x_2)$


Here is my question: If an adversary has one of the secret keys, say $s_1$, is the message $x_2$ still secure against him?

I've been searching around but I only found about security when the adversary doesn't know any key.
I give another simple proof using the leftover hash lemma.
The proof goes as follows, where I'll abuse the notation and assume that q is prime.

Game0

The adversary can see 
$$(A,b,c,u,v,w,s)
= (A, As+e, At+f, rA, rb+x\lfloor q/2 \rceil, rc+y\lfloor q/2 \rceil, s).$$

Game1

The view is changed as
$$(A,b,c,u,v,w,s)
= (A, As+e, c, rA, rb+x\lfloor q/2 \rceil, rc+y\lfloor q/2 \rceil, s),$$
 where we change $c = At+f$ with random $c$. 
From the LWE assumption, Game0 is indistinguishabe from Game1.

Game2

The view is changed as
$$(A,b,c,u,v,w,s)
= (A,As+e,c,u,rb+x\lfloor q/2 \rceil,z+y\lfloor q/2 \rceil, s)$$
where we replace $rA$ and $rc$ with random $u \gets \mathbb{Z}_q^n$ and $z \gets \mathbb{Z}_q$.

In this game, $y$ is completely hidden, since $z$ is chosen uniformly at random.

Game1 vs Game2

If the term $v=rb+x\lfloor q/2 \rceil$ disappears, 
 then we can invoke the leftover hash lemma as Regev originally did.

We can still invoke the generalized leftover hash lemma in [DORS08] even if the term $v$ remains.
Very roughly speaking, 
 if $m \geq (n+2) \lg{q} + 2(1/\epsilon) + O(1)$, 
 then we can say the distance between Game1 and Game2 is at most $\epsilon$. 

Generalized leftover hash lemma

Let us define the average min-entropy of $R$ given $I$ as follows:
$$\tilde{H}_{\infty}(R \mid I)
 = -\log\left(\mathrm{Exp}_{i \gets I}\left[
  \max_{r} \Pr[R = r \mid I = i]
  \right]\right).
$$
Intuitively speaking, this entropy is the logarithm of predictability of $R$ given $I$. As we expected, if $I$ leaks the information of $R$, the average min-entropy of $R$ given $I$ decreases. 

Let us consider the average min-entropy of $r$ given $v = rb + x\lfloor q/2 \rceil$.
By invoking  [Lemma 2.2 (b), DORS08], we have that 
$$
 \tilde{H}_{\infty}(r \mid v)
  \geq H_{\infty}(r) - \lg{q}.
$$
That is, the average min-entropy of $r$ given $v$
 is at least the min-entropy of $r$, which is $m$, minus $\lg{q}$. 

Now, let us review the generalized leftover hash lemma in [DORS08]:
For a family of universal hash functions $\{H_d : \{0,1\}^n \to \mathcal{S}\}$
for any random variables $R$ and $I$,
we have
$$
\Delta\Big(
 (H_{D}(R),D,I),
 (U_{\mathcal{S}},D,I)
\Big) \leq \frac{1}{2} \sqrt{2^{-\tilde{H}_{\infty}(R \mid I)} \cdot \#\mathcal{S}},
$$
where $U_{\mathcal{S}}$ is a random variable distributed according to the uniform distribution over $\mathcal{S}$.

By replace $D$ with $(A,c)$, $R$ with $r$,
 $H_{D}(R)$ with $(rA,rc)$, and $I$ with $v$,
 $\mathcal{S}$ with $\mathbb{Z}_q^{n+1}$,
 we obtain the upperbound of the statistical distance as $\frac{1}{2} \sqrt{2^{\tilde{H}_{\infty}(r \mid rb)} \cdot q^{n+1}}$, which is at most $\epsilon$ if $m = (n+2)\lg{q} + 2\log(1/\epsilon) + \Omega(1)$.


[DORS08] Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin and Adam Smith: "Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data" in SIAM Journal of Computing, 38(1):97--139, 2008. (Prelim. version is Dodis, Reyzin and Smith in EUROCRYPT 2004).