本文共 8002 字，大约阅读时间需要 26 分钟。

organization：特殊数、集合、运算关系、其他

汇总基础建议参考yuyu

(本文停止更新)

1. 数

安全参数：正整数$n或\lambda$。

正素数一般用$p$,$q$。 上确界supermum，最小上界$sup$

---

2. 集合

$\mathbb{Z}$表示整数集合，也有直接用$Z$表示的。

$\mathbb{R}$表示实数集合，也有直接用$R$表示的。 $\mathbb{N}$表示正数集合，也有直接用$N$表示的。 $s$ bits的集合， { 0 , 1 } s \{0,1\}^s {

0,1}s 例：$${\mathbb{Z}}_q：表示在[-\frac{q-1}{2},\frac{q-1}{2}]范围内的整数。$$$${\mathbb{Z}}_q^n:n维向量模q。$$$${\mathbb{Z}}_q^{n\times m}:一组n\times m的矩阵，其元素在{\mathbb{Z}}_q上。$$

群

商群$G/N$，设 $N$ 是群$G$的正规子群。定义集合$G/N$是 $N$ 在 $G$ 中的所有左陪集的集合，就是说 $G/N=\{$

aN:a∈G}，即商群每个元素都是$N$与$a$的乘法运算，$N$相当于群$G$的“单位元”。

环

环Ring:环$R=\mathbb{Z}[x]/(x^n+1)$，和环$R_q={\mathbb{Z}}_q[x]/(x^n+1)$

商环(剩余类环)：也有类似商群的概念 R / N = { a + N , a ∈ R } R/N=\{a+N,a\in R\} R/N={

a+N,a∈R} 因此，密码学中环则有： Z [ x ] / < x n + 1 > = { a ( x n + 1 ) : a ∈ Z } \Z[x]/<x^n+1> = \{ a(x^n+1) : a∈\Z \} Z[x]/<xn+1>={

a(xn+1):a∈Z} $R^{\times }$:表示$R$中逆元。 环中多项式：$f={\sum }_{i=0}^{N-1}{f}_i{x}^i$ 对任意正整数，令$\left[k\right]$代表集合 { 1 , ⋯   , k } \left\{ {1, \cdots ,k} \right\} {

1,⋯,k}。 ${\Lambda }^{\perp }$:垂直符号, 指 0或空(NULL) 集合运算： $A\in B$,子集 $A\subset B$,包含 差集：$A-B$，密码学中常用$A\backslash B$形式，例如： Z m \ { 0 } \Z^m\backslash \{0\} Zm\{

0},

域

有限素域$GF(p)$

格

$\Lambda$:格，

其他 $\Lambda =\mathcal{L}(B)$，表示由基$B$生成的格。 $\eta (\Lambda )$，表示格中最短向量（或者满足条件的短向量）的范数。 Λ ⊥ ( T ) = { T x = 0 ( m o d    q ) } , 也 写 成 Λ q ⊥ ( T ) \Lambda^\perp(T)=\{Tx=0 (\mod q)\},也写成\Lambda^\perp _q(T) Λ⊥(T)={

Tx=0(modq)},也写成Λq⊥​(T) Λ u ⊥ ( T ) = { T x = u ( m o d    q ) } = Λ q ⊥ ( T ) \Lambda^\perp_u(T)=\{Tx=u (\mod q)\}=\Lambda^\perp_q(T) Λu⊥​(T)={

Tx=u(modq)}=Λq⊥​(T) ${\Lambda }^{\ast }$:对偶格

向量&矩阵

黑体小写字母代表列向量，如向量$\mathbf{v}$。

黑体大写字母代表矩阵，如矩阵$\mathbf{A}$。

---

3. 运算

内积inner product：$<\mathbf{x},\mathbf{y}>$

对于任意的向量$\mathbf{v}$，它的第$i$个分量用${\mathbf{v}}_i$表示，它的范数为 ∥ v ∥ = ( ∣ v 1 ∣ p + ⋯ + ∣ v n ∣ p ) 1 / p \left\| \bold v \right\| = {({\left| {

{v_1}} \right|^p} + \cdots + {\left| { {v_n}} \right|^p})^{1/p}} ∥v∥=(∣v1​∣p+⋯+∣vn​∣p)1/p，为了写作简便，当 $p=2$ 时，我们不写$p$也就是说向量的欧几里得范数简记为$\Vert \mathbf{v}\Vert$。

令${\mathbf{a}}_i$表示矩阵的第个列向量，定义 ∥ A ∥ p = max ⁡ i ( ∥ a i ∥ p ) {\left\| \bold A \right\|_p} = {\max _i}({\left\| {

{\bold a_i}} \right\|_p}) ∥A∥p​=maxi​(∥ai​∥p​)。 $$s\stackrel{\$}{⟵}\mathcal{D}:x在分布\mathcal{D}上选择。$$$$s\stackrel{\$}{⟵}\mathcal{S}:表示x在集合\mathcal{S}上均匀随机选择。$$ 也有用$s\leftarrow S$表示选取（或采样），或者$k{\in }_R{Z}_p^{\ast }$（$R$表示随机选取，$\ast$表示正数。）

统计距离Statistical distance：离散分布的统计距离，连续分布的统计距离

给定矩阵$\mathbf{B}$,$\tilde{\mathbf{B}}$表示$\mathbf{B}$的施密特正交变换，$\Vert \tilde{\mathbf{B}}\Vert$表示其范数。

• 向量的范数：

  1-范数:向量元素绝对值之和，${\Vert \mathbf{x}\Vert }_1=\sum _{i=1}^N\left|x_i\right|$
  2-范数（又称Euclid范数，欧几里得范数）：向量元素绝对值的平方和再开方，表示向量的长度，${\Vert X\Vert }_2=\sqrt{\sum _{i=1}^N{x_i}^2}$
  无穷范数，所有向量元素绝对值中的最大值,${\Vert X\Vert }_{\infty }=\underset{i}{\max }\left|x_i\right|$

• 矩阵的范数

  1-范数：列和范数，即所有矩阵列向量绝对值之和的最大值，${\Vert A\Vert }_1=\underset{j}{\max }\sum _{i=1}^m\left|a_{i,j}\right|$
  2-范数：谱范数，即$A^{\prime }A$矩阵的最大特征值的开平方，${\Vert A\Vert }_2=\sqrt{{\lambda }_1},\lambda 是A^{T}A的最大特征值。$
  $\infty$范数：行和范数，即所有矩阵行向量绝对值之和的最大值${\Vert A\Vert }_{\infty }=\underset{i}{\max }\sum _{j=1}^m\left|a_{i,j}\right|$

4. 关系

渐进

We use the standard asymptotic notation $f=O(g)$ (or $g=\Omega (f)$) when $\lim su{p}_{n\to \infty }|f(n)/g(n)|<\infty$

$f=o(g)$ (or $g=\omega (f)$) when $li{m}_{n\to \infty }|f(n)/g(n)|=0$, and $f=\Theta (g)$ when $f=O(g)$ and $f=\Omega (g)$.

渐进符号：设函数$f(n),g(n)$均为$\mathbb{N}\to {\mathbb{R}}^{+}$的函数，约定符号：

(1)若$limf(n)/g(n)\ne \infty$，则称函数$g(n)$为函数$f(n)$的一个渐进上界，记作$f(n)=O(g(n))$。 (2)若$limf(n)/g(n)\ne 0$，则称函数$g(n)$为函数$f(n)$的一个渐进下界，记作$f(n)=\Omega (g(n))$。 (3)若$limf(n)/g(n)=\infty$，则称函数$f(n)$是关于函数$g(n)$的无穷大量，记作$f(n)=\omega (g(n))$。

---

5. 其他

其他-1

对任意字符串$s$和$t$(在不致引起混滑的情况下，我们有时也把向量看做字符串)，$|s|$表示的比特

长度，$s||t$表示两个字符串的级联，$s\oplus t$代表它们的$XOR$操作。 对于实数$x$，$|x|$表示$x$的绝对值。

其他-2

施密特正交

可忽略函数：可忽略：$negl(n)$，压倒性优势：$1-ngel(n)$PS:注意利用概率总和为1进行公式变换。 统计距离：两个分布的距离。

---

参考上符号定义

加密参数：For a cryptographic signature scheme, $\lambda$ denotes its security level and $q_s$ the maximal number of signature queries which may be made. Following the assumptions of [NIS16],we suppose that $q_s\le 2^{64}$.

矩阵，向量，维度：Matrices will usually be in bold uppercase (e.g. $\mathbf{B}$), vectors in bold lowercase (e.g. $\mathbf{v}$) and scalars – which include polynomials – in italic (e.g. $s$). We use the row convention for vectors.

The transpose of a matrix B may be noted ${\mathbf{B}}^t$. It is to be noted that for a polynomial $f$, we do not use $f^{{}^{\prime }}$ to denote its derivative in this document.

商环：For $q\in N^{\ast }$, we denote by ${\mathbb{Z}}_q$ the quotient ring $\mathbb{Z}/q\mathbb{Z}$; in Falcon, $q=12289$ is prime so ${\mathbb{Z}}_q$ becomes a finite field.

We also denote by ${\mathbb{Z}}_q^{\times }$ the group of invertible elements of ${\mathbb{Z}}_q$, and by $\phi$ Euler’s totient function: $\phi (q)=|{\mathbb{Z}}_q^{\times }|=q-1$ since $q$ is prime.

数域：

内积：

Ring Lattice环格：

离散高斯：For $\sigma ,\mu \in \mathbb{R}$ with $\sigma >0$, we define the Gaussian function ${\rho }_{\mu ,\sigma }$ as ${\rho }_{\mu ,\sigma }(x)=exp(-|x-\mu {|}^2/2{\sigma }^2)$, and the discrete Gaussian distribution $D_{\mathbb{Z},\sigma ,\mu }$ over the integers as

$$D_{\mathbb{Z},\sigma ,\mu }(x)=\frac{{\rho }_{\mu ,\sigma }(x)}{{\sum }_{z\in \mathbb{Z}}{\rho }_{\sigma ,\mu }(z)}$$ The parameter $\mu$ may be omitted when it is equal to zero.

域范数Filed Norm：

施密特正交：Any matrix $B\in {\mathcal{Q}}^{n\times m}$ can be decomposed as follows:

$$B=L\times \tilde{B},$$ where $L$ is lower triangular with 1’s on the diagonal, and the rows${\tilde{b}}_i$’s of $\tilde{B}$ verify $b_i{b}_j^{\star }=0$ for $i\ne j$. When $B$ is full-rank , this decomposition is unique, and it is called the Gram-Schmidt orthogonalization (or GSO). We will also call Gram-Schmidt norm of Bthe following value: $$\Vert B{\Vert }_{GS}=\underset{\tilde{\mathbf{b}}\in \tilde{\mathbf{B}}}{\max }\Vert {\tilde{\mathbf{b}}}_i\Vert$$

参考

---

1. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions

2. 田苗苗. 基于格的数字签名方案研究[D].中国科学技术大学,2014.

转载地址：http://ljtzi.baihongyu.com/