格密码学习笔记（七）：密码学中的q相关格、简介SIS问题和LWE问题
文章目录
- QQQ-相关格
- Ajtai提出的单向函数（SIS）
- Regev提出的容错学习问题（LWE）
- 致谢
QQQ-相关格
密码学中通常使用符合以下2个性质的（随机）格Λ\LambdaΛ构造具体方案：
- Λ⊆Zd\Lambda \subseteq \mathbb{Z}^dΛ⊆Zd是一个整数格；
- qZd⊆Λq \mathbb{Z}^d \subseteq \LambdaqZd⊆Λ对小整数qqq取模后呈现周期性。
定义（qqq-相关格，qqq-ary lattice） 如果格Λ\LambdaΛ满足qZn⊆Λ⊆Znq \mathbb{Z}^n \subseteq \Lambda \subseteq \mathbb{Z}^nqZn⊆Λ⊆Zn，则称Λ\LambdaΛ是一个qqq-相关格。
注：这里的“-ary”有“与…有关”的意思，如果翻译为“阶”感觉怪怪的，如果是qqq-阶群，感觉群里得有qqq个元素，但定义里又没有体现。
什么是qqq-相关格？举2个例子，对于任意A∈Zqn×d\bm{A} \in \mathbb{Z}_q^{n \times d}A∈Zqn×d，有
- Λq(A)={x∣xmodq∈A⊤Zqn}⊆Zd\Lambda_q(\bm{A}) = \{ \bm{x} | \bm{x} ~ \mathrm{mod} ~q \in \bm{A}^\top \mathbb{Z}^n_q \} \subseteq \mathbb{Z}^dΛq(A)={x∣x mod q∈A⊤Zqn}⊆Zd
- Λq⊥(A)={x∣Ax=0modq}⊆Zd\Lambda^\perp_q(\bm{A}) = \{ \bm{x} | \bm{Ax} = \bm{0} ~ \mathrm{mod} ~ q \} \subseteq \mathbb{Z}^dΛq⊥(A)={x∣Ax=0 mod q}⊆Zd
定理 对于任意格Λ\LambdaΛ，以下3个qqq-相关格判断条件是等价的：
- qZd⊆Λ⊆Zdq \mathbb{Z}^d \subseteq \Lambda \subseteq \mathbb{Z}^dqZd⊆Λ⊆Zd；
- 存在某些A\bm{A}A满足Λ=Λq(A)\Lambda = \Lambda_q(\bm{A})Λ=Λq(A)
- 存在某些A\bm{A}A满足Λ=Λq⊥(A)\Lambda = \Lambda^\perp_q(\bm{A})Λ=Λq⊥(A)
注意： 对于同一个A\bm{A}A，格Λq(A)\Lambda_q(\bm{A})Λq(A)和格Λq⊥(A)\Lambda^\perp_q(\bm{A})Λq⊥(A)是不同的。而对于一个A∈Zqn×d\bm{A} \in \mathbb{Z}^{n \times d}_qA∈Zqn×d，存在A′∈Zqk×d\bm{A}' \in \mathbb{Z}^{k \times d}_qA′∈Zqk×d，使得Λq(A)=Λq⊥(A′)\Lambda_q(\bm{A}) = \Lambda^\perp_q(\bm{A}')Λq(A)=Λq⊥(A′)。反过来亦如此。
对于同一个A\bm{A}A，Λq\Lambda_qΛq和Λq⊥\Lambda_q^\perpΛq⊥存在放缩对偶关系，即
- Λq(A)∨=1qΛq⊥(A)\Lambda_q(\bm{A})^\vee = \frac{1}{q} \Lambda^\perp_q(\bm{A})Λq(A)∨=q1Λq⊥(A)
- Λq⊥(A)∨=1qΛq(A)\Lambda^\perp_q(\bm{A})^\vee = \frac{1}{q} \Lambda_q(\bm{A})Λq⊥(A)∨=q1Λq(A)
Ajtai提出的单向函数（SIS）
Ajtai在1996年提出了基于qqq相关随机格的单向函数（One-Way Function，OWF），并给出了安全性证明。这里的SIS是Short Integer Solution的缩写。该OWF构造如下图。
定理 对于m>nlgqm > n ~ \mathrm{lg} ~ qm>n lg q，若SIVP问题在最差情况下依旧是困难的，那么fA(x)=Axmodqf_{\bm{A}}(\bm{x}) = \bm{Ax} ~ \mathrm{mod} ~ qfA(x)=Ax mod q是单向函数。
这里简要给出抗碰撞证明思路，后续公开课Daniele Micciancio教授有给出单向函数详细证明。
- fA(x)=Axmodqf_{\bm{A}}(\bm{x}) = \bm{Ax} ~ \mathrm{mod} ~ qfA(x)=Ax mod q，这里的x\bm{x}x是一个短向量，即一个二进制向量（联想CVP问题中点t\bm{t}t与格点之间的向量）；
- fAf_{\bm{A}}fA的核是qqq相关矩阵Λq⊥(A)\Lambda^\perp_q(\bm{A})Λq⊥(A)，注意：∀v∈Λq⊥(A)\forall \bm{v} \in \Lambda^\perp_q(\bm{A})∀v∈Λq⊥(A)，有fA(v)=0modqf_{\bm{A}}(\bm{v}) = \bm{0} ~ \mathrm{mod} ~ qfA(v)=0 mod q；
- 寻找碰撞fA(x)=fA(y)f_{\bm{A}}(\bm{x}) = f_{\bm{A}}(\bm{y})fA(x)=fA(y)等价于寻找一个短向量(v=x−y)∈Λq⊥(A)( \bm{v} = \bm{x} - \bm{y} ) \in \Lambda^\perp_q(\bm{A})(v=x−y)∈Λq⊥(A)；
- fA(x)f_{\bm{A}}(\bm{x})fA(x)的输出为x\bm{x}x的伴随译码，即函数输出取x\bm{x}x与对偶格基向量的积并仅保留小数部分，这个可以翻阅《格密码学习笔记（六）：格中模运算》，即尝试用碰撞问题的解寻找CVP问题的解，以此分析问题的难度；
- 对fA(x)f_{\bm{A}}(\bm{x})fA(x)求逆相当于求解伴随译码格式下的CVP问题，CVP问题的输入为Λq⊥(A)\Lambda^\perp_q(\bm{A})Λq⊥(A)和t∈x+Λq⊥(A)\bm{t} \in \bm{x} + \Lambda^\perp_q(\bm{A})t∈x+Λq⊥(A)（再次强调，这里的x\bm{x}x是一个短向量）；
- 若fAf_{\bm{A}}fA是一个压缩函数，那么x\bm{x}x的长度需要大于12λ1(Λq⊥(A))\frac{1}{2}\lambda_1(\Lambda^\perp_q(\bm{A}))21λ1(Λq⊥(A))（个人推测，这个可能跟用SIS答案解CVP问题的成功概率有关，后续学习笔记再进行补充、分析）。
注意，SIS≡Approximate ADD\mathsf{SIS} \equiv \text{Approximate} ~ \mathsf{ADD}SIS≡Approximate ADD（绝对距离解码）。
Regev提出的容错学习问题（LWE）
Regev在2005年提出Learning With Errors（LWE）。Learning（学习） 这个词常见于机器学习中，一个完整的机器学习方法包括模型和学习算法两部分，这里的“学习”可以理解成“figure out”，即求解出问题的解（从中学到某种知识）。LWE问题定义如下图。
LWE与SIS看起来有点不一样，但某种程度上这两者之间是对偶关系。在LWE问题中，输入和错误向量e\bm{e}e比SIS的向量短得多，得到的函数是单射的，安全性证明难度更大。
定理 若SIVP问题在最坏情况下是困难的，则函数gA(s,e)g_{\bm{A}}(\bm{s}, \bm{e})gA(s,e)在多数情况下难以求逆。
- 如果e=0\bm{e} = \bm{0}e=0，那么As+e=As∈Λ(A⊤)\bm{As} + \bm{e} = \bm{As} \in \Lambda(\bm{A}^\top)As+e=As∈Λ(A⊤)，这里的转置请往上回翻Λq(A)\Lambda_q(\bm{A})Λq(A)的定义；
- 若e≠0\bm{e} \neq \bm{0}e=0，则相当于求解qqq相关随机格Λ(A⊤)\Lambda(\bm{A}^\top)Λ(A⊤)和随机向量t=As+e\bm{t} = \bm{As} + \bm{e}t=As+e的CVP问题（注意这里没有SIS中的伴随译码形式，所以某种程度上与SIS之间存在对偶关系）；
- 一般情况下，e\bm{e}e的长度小于12λ1(Λ(A⊤))\frac{1}{2}\lambda_1\big(\Lambda(\bm{A}^\top)\big)21λ1(Λ(A⊤))，且e\bm{e}e是唯一确定的。
注意，LWE≡Approximate BDD\mathsf{LWE} \equiv \text{Approximate} ~ \mathsf{BDD}LWE≡Approximate BDD（有界距离解码）。
致谢
- Simons格密码公开课官网
Mathematics of Lattices - Simons Institute for the Theory of Computing - 哔哩哔哩中英双语视频（字幕组：重庆大学大数据与软件学院 后量子密码研究小组）
【中英字幕】Simons格密码讲座第1讲：格的数学定义_哔哩哔哩_bilibili - 其它格密码讲解课程和博文
Lattice学习笔记04：SIS与LWE问题
公开学习资料的无私奉献者