Reading: PAE

Trustworthy deep learning.

Reading: Peikert’s wide-angle survey for the lattice backbone[^peikert], Brakerski’s FHE survey for the leveled-to-full control argument[^brakerski-survey], and the Gentry / BGV / BV / GSW / FV papers for the actual mechanism[^gentry][^bgv][^bv][^gsw][^fv]. Beyond Parts 0-3, the only extra objects needed here are introduced locally: noisy LWE-style decryptions, structured ring or module arithmetic, gadget bases, and evaluation keys. Part 7 is where those objects become one controlled evaluation procedure.

The procedure fails at a very specific point. Addition keeps decryption inside the same noisy linear relation. Multiplication does not. It lifts the decryption equation from a linear secret-key basis to a higher-degree basis, enlarges the ciphertext object, and spends decoding margin at the same time. If FHE is to support general evaluation, it needs a control layer exactly at that break.

That control layer is gadget decomposition plus evaluation keys. Once that interface is explicit, key switching becomes a noisy basis change, relinearization becomes the special case that removes post-multiplication secret-key degree, and the leveled-versus-fully-homomorphic split becomes a question of whether the noise budget can be managed forever or only up to a fixed depth.[^brakerski-survey]

从拉格朗日插值法到 FFT. Part-1.

It was listed by the Science magazine as one of the ten greatest algorithms in the 20th century

从 FT 开始加速多项式乘法。主要记录了笔者学习傅里叶变换这一特殊线性变换时的笔记。

Reading path: Micciancio-Regev 的 survey / lecture-note 主线[^micciancio-regev]，再接 GPV[^gpv]、Lyubashevsky 的 trapdoor-free signature line[^lyu12]、Falcon[^falcon] 与 Dilithium[^dilithium]。这一篇只讨论结构，不写成 NIST 结果综述。

Part 4 和 Part 5 讲的是 hardness 如何支撑 encryption 与 KEM：SIS / LWE 给出难解关系，RLWE / MLWE / NTRU 给出更适合实现的结构。Part 6 反过来问另一个问题。假设已经有困难问题了，signer 到底靠什么持续生成“可验证而且足够短”的 witness？

这是签名线和加密线分叉的地方。加密只要求 honest party 能解码；签名要求 honest signer 主动制造一个受控分布的短向量，而且这个过程不能把 trapdoor 本身逐次泄露出去。于是短基、陪集、预像采样、Gaussian sampling、Fiat-Shamir with aborts 会在这一篇同时出现。

Working thesis: lattice signatures need more than encryption hardness. They need a mechanism for distribution-controlled short witness generation.

Reading: Peikert’s survey spine[^peikert-survey], Regev’s lecture-note framing[^regev-notes], and the primary RLWE / Module-LWE / Kyber / NTRU papers[^rlwe][^module][^kyber][^ntru] are enough to keep the taxonomy straight.

Part 4 already fixed the baseline: LWE is noisy linear algebra, and the noise is what blocks elimination. Part 5 asks a different question. If the hard core is already there, what do we gain by forcing that core to live inside a quotient ring or a module?

Micciancio-Regev’s lecture-note framing[^mr], Regev’s 2005 reduction[^regev], and Peikert’s 2009 encryption perspective[^peikert09] are the three anchors for this bridge chapter.

Part 0-3 already gave the lattice side: basis reduction, CVP/Babai intuition, SIS, and ISIS. Here we change only one ingredient, but it changes the entire cryptographic surface. The goal is to stabilize plain LWE first, not to preview structured lattices yet.