Randomness re-use in LWE encryption scheme

Question

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.

Answer 1

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).

Answer 2

xagawa's original answer is almost correct, except for the valid concern pointed out by Florian in the comments. (The updated answer looks good to me.)

The answer to the question is "yes," except that the most 'lattice-y' proof works for the modified version of the Regev system defined in Applebaum-Cash-Peikert-Sahai CRYPTO'09. (A version of this was also sketched in GPV'08, in connection with the tight security reduction for the IBE.) Much like in Regev's system, in ACPS we encrypt (almost) as $\mathbf{r} \cdot \mathbf{P}$, where $\mathbf{P}=[\mathbf{A} \mid \mathbf{b}=\mathbf{A}\mathbf{s} + \mathbf{e}]$ is the public key. However, we choose $\mathbf{r}$ from a discrete Gaussian distribution over $\mathbb{Z}^m$ with parameter $\omega(\sqrt{\log n})$. In addition, we add a little "smoothing noise" $\tilde{e}$ to the final coordinate of $\mathbf{r} \cdot \mathbf{P}$. (See the paper for full details.)

The point of these modifications is that for almost any fixed choice public key, the ciphertext distribution (over the choice of encryption randomness alone) is a "true" LWE distribution, with Gaussian error. (This does not appear to be the case for Regev's original system, where $\mathbf{r}$ is binary.) We'll see how this is used in the proof outline below.

The above system generalizes in the expected way to two (or more) message bits, using a public key of the form $[\mathbf{A} \mid \mathbf{b}_1 \mid \mathbf{b}_2]$ where $\mathbf{b}_i = \mathbf{A} \mathbf{s}_i + \mathbf{e}_i$. To prove security where $\mathbf{s}_2$ is known to the attacker, we first transition from Game0 to Game1 as in xagawa's answer, making $\mathbf{A}'=[\mathbf{A} \mid \mathbf{b}_1]$ uniform.

Now, the main point is that conditioned on any value of $\mathbf{r} \mathbf{A}'$ (which itself is uniform), the distribution of $\mathbf{r}$ is a discrete Gaussian over a coset of $\Lambda^\perp(\mathbf{A}')$. By a lemma from Regev's LWE paper, the distribution of $\mathbf{r} \cdot \mathbf{e}_2 + \tilde{e}_2$ is therefore itself Gaussian, with a parameter that depends on the norm $\| \mathbf{e}_2 \|$ and the Gaussian parameters of $\mathbf{r}, \tilde{e}_2$.

What this means is that Game1 is statistically close to a Game2 where we have no $\mathbf{r}$ at all. Instead we choose $\mathbf{A}'$ uniformly, choose uniform $[\mathbf{u} \mid u_1]$ in place of $\mathbf{r} \mathbf{A}'$, choose $\mathbf{b}_2=\mathbf{A} \mathbf{s}_2 + \mathbf{e}_2$ as usual, and finally set the 'pad' for the second encrypted bit to be $\mathbf{u} \cdot \mathbf{s}_2 + e$, where $e$ is Gaussian with the proper parameter (which depends on $\|\mathbf{e}_2\|$).

This all generalizes somewhat to more revealed secret keys, but there is some degradation: we need to understand the distribution of $\mathbf{r} \mathbf{E} + \tilde{\mathbf{e}}$ for fixed $\mathbf{E}$, discrete Gaussian $\mathbf{r}$, and "smoothing" noise $\mathbf{e}$. We were able to analyze this somewhat in ACPS'09, but it's not clear whether we got the best possible results.

Alternatively, it's likely that there is another proof for Regev's original system using xagawa's games, if we also use a stronger version of the LHL that allows for some side information/leakage on the hash input $\mathbf{r}$ (in this case, $\mathbf{r} \cdot \mathbf{e}_2$). Similarly, there will be some degradation with more revealed secret keys. See xagawa's answer for details.