SupplementaryMaterials AFurtherDetailsofLWE

A.3 OverviewofAttacksonLWE Typically, attacks on the LWE problem use an algebraic approach and involve lattice reduction algorithms such as BKZ [22]. Forinstance,theBKWstyleattack [5]uses combinatorial methods; however, this assumes access to an unbounded number of LWE samples. Binary and ternary secret distributions are widely used in homomorphic encryption schemes. In[14]and[47],both papers give reductions of binary-LWE to hard lattice problems, implying the hardness of binaryLWE. Let us now turn to the attacks on (sparse) binary/ternary secrets.