Lattice-Based, More General Anti-leakage Model and Its Application in Decentralization

In the case of standard \(\textsf{LWE}\) samples \((\textbf{A},\mathbf {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}|\mathbf {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}|\mathbf {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 [6] 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.