In the case of standard LWE samples \(({\textbf {A}},{\textbf {b = sA + e}})\) , \({\textbf {A}}\) is typically uniformly over \(\mathbb {Z}_q^{n \times m}\) . Under the \(\textsf {DLWE}\) assumption, the conditional distribution of \({\textbf {s}}|({\textbf {A}}, {\textbf {b}})\) and \({\textbf {s}}\) is expected to be consistent. However, in the case where an adversary chooses \({\textbf {A}}\) adaptively, the disparity between the two entities may be larger. In this work, our primary focus is on the quantification of the Average Conditional Min-Entropy \(\tilde{H}_\infty ({\textbf {s}}|{\textbf {sA + e}})\) of \({\textbf {s}}\) , where \({\textbf {A}}\) is chosen by the adversary. Brakerski and Döttling answered the question in one case: they proved that when \({\textbf {s}}\) is uniformly chosen from \(\mathbb {Z}_q^n\) , it holds that \(\tilde{H}_\infty ({\textbf {s}}|{\textbf {sA + e}}) \varpropto \rho _\sigma (\varLambda _q({\textbf {A}}))\) . We prove that for any \(d \le q\) , when \({\textbf {s}}\) is uniformly chosen from \(\mathbb {Z}_d^n\) or is sampled from a discrete Gaussian distribution, there are also similar results. As an application of the above results, we improved the multi-key fully homomorphic encryption and answered the question raised at the end of their work positively: we have GSW-type ciphertext rather than Dual-GSW, and the improved scheme has shorter keys and ciphertexts.
