Lattice-based, LWE-leakage model for Gaussian and uniform secret and its application in decentralization

Abstract In the case of standard LWE samples $$({\textbf {A}},{\textbf {b = sA + e}})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>A</mml:mi> <mml:mo>,</mml:mo> <mml:mrow> <mml:mi>b</mml:mi> <mml:mo>=</mml:mo> <mml:mi>sA</mml:mi> <mml:mo>+</mml:mo> <mml:mi>e</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , $${\textbf {A}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>A</mml:mi> </mml:math> is typically uniformly over $$\mathbb {Z}_q^{n \times m}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>Z</mml:mi> <mml:mi>q</mml:mi> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×</mml:mo> <mml:mi>m</mml:mi> </mml:mrow> </mml:msubsup> </mml:math> . Under the $$\textsf {DLWE}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>DLWE</mml:mi> </mml:math> assumption, the conditional distribution of $${\textbf {s}}|({\textbf {A}}, {\textbf {b}})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>s</mml:mi> <mml:mo>|</mml:mo> <mml:mo>(</mml:mo> <mml:mi>A</mml:mi> <mml:mo>,</mml:mo> <mml:mi>b</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and $${\textbf {s}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>s</mml:mi> </mml:math> is expected to be consistent. However, in the case where an adversary chooses $${\textbf {A}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>A</mml:mi> </mml:math> 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}})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mover> <mml:mi>H</mml:mi> <mml:mo>~</mml:mo> </mml:mover> <mml:mi>∞</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>s</mml:mi> <mml:mo>|</mml:mo> <mml:mrow> <mml:mi>sA</mml:mi> <mml:mo>+</mml:mo> <mml:mi>e</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> of $${\textbf {s}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>s</mml:mi> </mml:math> , where $${\textbf {A}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>A</mml:mi> </mml:math> is chosen by the adversary. Brakerski and Döttling answered the question in one case: they proved that when $${\textbf {s}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>s</mml:mi> </mml:math> is uniformly chosen from $$\mathbb {Z}_q^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>Z</mml:mi> <mml:mi>q</mml:mi> <mml:mi>n</mml:mi> </mml:msubsup> </mml:math> , it holds that $$\tilde{H}_\infty ({\textbf {s}}|{\textbf {sA + e}}) \varpropto \rho _\sigma (\varLambda _q({\textbf {A}}))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mover> <mml:mi>H</mml:mi> <mml:mo>~</mml:mo> </mml:mover> <mml:mi>∞</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>s</mml:mi> <mml:mo>|</mml:mo> <mml:mrow> <mml:mi>sA</mml:mi> <mml:mo>+</mml:mo> <mml:mi>e</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>∝</mml:mo> <mml:msub> <mml:mi>ρ</mml:mi> <mml:mi>σ</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>Λ</mml:mi> <mml:mi>q</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>A</mml:mi> <mml:mo>