International Association
for Cryptologic Research

For standard \LWE samples $(\mathbf{A},\mathbf{b = sA + e})$, $\mathbf{A}$ is typically uniformly over $\mathbb{Z}_q^{n \times m}$, and under the \LWE assumption, the conditional distribution of $\mathbf{s}$ given $\mathbf{b}$ and $\mathbf{s}$ should be consistent. However, when $\mathbf{A}$ is chosen by an adversary, the gap between the two may be larger. In this work, we are mainly interested in quantifying $\tilde{H}_\infty(\mathbf{s}|\mathbf{sA + e})$, while $\mathbf{A}$ is chosen by an adversary. Brakerski and D\"{o}ttling answered the question in one case : they proved that when $\mathbf{s}$ was uniformly chosen from $\mathbb{Z}_q^n$, it holds that $\tilde{H}_\infty(\mathbf{s}|\mathbf{sA + e}) \varpropto \rho_\sigma(\Lambda_q(\mathbf{A}))$. We prove that for any $d < q$ and $\mathbf{s}$ is uniformly chosen from $\mathbb{Z}_d^n$, the above result still holds.

In addition, as an independent result, we have also proved the regularity of the hash function mapped to the prime-order group and its Cartesian product.

As an application of the above results, we improved the multi-key fully homomorphic encryption\cite{TCC:BraHalPol17} and answered the question raised at the end of their work in positive way : we have GSW type ciphertext rather than Dual-GSW, and the improved scheme has shorter keys and ciphertexts