Algorithm

Finding a Close Point in a Lattice

Reference [Bab85] On Lovász’ lattice reduction and the nearest lattice point problem [Kle00] Finding the closest lattice vector when it’s unusually close [GPV08] Trapdoors for Hard Lattices and New Cryptographic Constructions [DP16] Fast Fourier Orthogonalization [GMRR22] Power analysis attacks on falcon.

Jul 10, 2023 6 min read Note

Barrett Reduction and Montgomery Reduction

Given a variable $a$ and a prime number $q$, we want to securely compute $a \text{ mod } q$.

The Barrett reduction is usually used in addition.

The Montgomery reduction is usually used in multiplication and reduction.

Oct 31, 2022 4 min read Note

Note on Number Theoretic Transform

NTT Github Repo: python-NTT FFT Recall for a sequence of signal $x=(x_0, x_1,\cdots,x_{N-1})$. The Fast-Fourier Transform does $$ \hat{x} =FFT(x)= \left ( \sum_{n=0}^{N-1} x_n e^{-2 \pi i\frac{ n m}{N}} \right)_{0\leq m\leq N-1} $$

Jun 18, 2022 3 min read Note