New answers tagged lwe
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
Related Tags
lwe × 92lattice-crypto × 51
post-quantum-cryptography × 27
ring-lwe × 24
homomorphic-encryption × 14
key-exchange × 7
newhope × 5
public-key × 4
cryptanalysis × 3
provable-security × 3
hardness-assumptions × 3
trapdoor × 3
encryption × 2
discrete-logarithm × 2
implementation × 2
attack × 2
nist × 2
coding-theory × 2
sis × 2
rsa × 1
aes × 1
randomness × 1
multiparty-computation × 1
finite-field × 1
factoring × 1