New answers tagged

2

Here is the optimization in more detail. Start with $[\bar{A} \mid I_n \mid G']$ where $\bar{A} \in \mathbb{Z}_q^{n \times n}$ and $G = [I_n \mid G']$ (where $I_n$ is the $n$-by-$n$ identity matrix). Note that the concrete gadget matrices $G$ constructed in the paper already contain an identity submatrix (up to reordering of columns). But in general, $G$ ...


3

As a quick aside, while Hermite refers to the same person, "Hermitian" means something different for matrices than "Hermite Normal Form". HNF is essentially "Row Echelon Form/Gaussian Elimination where you can't divide". HNF Optimization: First, we can discuss "Reducing the columns of $E$ modulo the HNF", which does ...


0

Per Mark's suggestion, I looked into the "hidden" tests in lwe-estimator and read a few papers. I summarized my findings as an answer here: Arora-Ge attack, and the improved version using Grobner bases, work better when $q$ is small, but it starts to be impractical once the number of samples $n$ and $q$ is very large, e.g., $q=2^{64}$. This seems ...


Top 50 recent answers are included