符号说明

数域

\(R\)：实数
\(Z\)：整数
\(C\)：复数
\(Q\)：有理数

空间

\(R^n\)：n维实数
\(Z^n\)：n维整数
\(C^n\)：n维复数
\(Q^n\)：n维有理数

集合

\(Z^+\)：正整数
\(R^+\)：非负实数
\(Z_q,q\geq 1\)：商环\(Z/qZ\)
\(\left [ n \right ]\)：表示\({1,...,n}\)
\(A/B\)：B在A上的补集
\(|B|\)：集合B中元素的个数
\(log\)：以2为底
\(M^T\)：向量/矩阵的转置

区间

（1）对于\(x,y\in R\)，其中\(y>0\)，\(\left \lfloor x \right \rfloor\)表示小于\(x\)的最大整数，\(x mod y =x-\left \lfloor x/y \right \rfloor y\)
（2）\(\left \lceil x \right \rfloor=\left \lfloor x+1/2 \right \rfloor\)

范数

（1）欧式范数（\(l_2\)范数）
向量：\(||v||=(\sum_{i}v_i^2)^{1/2}\)
矩阵：\(||M||=max_i||m_i||,m_i\)是\(M\)的第\(i\)列

分布采样

（1）D表示集合S上的一个概率分布，\(x\leftarrow D\)表示根据概率D采样\(x\in S\)
（2）\(U(S)\)：S上的均匀分布
（3）若D是一个概率算法，使用\(y\leftarrow D(x)\)表示在输入x上运行算法D，最后赋值\(D(x)\)到输出y上

最小熵(min entropy)

这里\(X\)是集合中的分布还是元素？

复杂度 渐进标准

多项式的(polynomial)

对于某个常数\(c\)，若\(f(n)=O(n^c)\)，则称\(f(n)\)关于n是多项式的，记为\(poly(n)\)。

可忽略的(hegligible)

对于任意常数\(c\)，有\(f(n)=o(n^{-c})\)，则称\(f(n)\)关于n是可忽略的，记为\(negl(n)\)

若一个事件以至少\(1-negl(n)\)的概率发生，则称这件事发生的概率是压倒性的（overwhelming）

语义安全

（1）\(ADV_Y^X\)：算法\(A\)在攻击基于安全定义\(X\)的方案\(Y\)时的优势，可简写为\(ADV(A)\)
（2）统计不可区分

若\(\Delta (D_1,D_2)\leq negl(n)\)，则称\(D_1\)和\(D_2\)是统计不可区分的，表示\(D_1\approx _s D_2\)。
（3）计算不可区分
对于任意可区分分布\(D_1\)和\(D_2\)的概率多项式时间（PPT）算法A，若\(|Pr[A(1^n,D_1)=1]-Pr[A(1^n,D_2)=1]|\leq negl(n)\)，则称\(D_1\)和\(D_2\)是计算不可区分的，表示\(D_1\approx _c D_2\)
（4）分布不可区分

一次一密（完美/理想保密）

一次一密，是理想情况下最安全的加密算法，但存在两个重要问题：
（1）每加密一次，需要更换一个密钥
（2）密钥的长度和明文相当。

实际保密

攻击者成功优势

优势的取值一般和加密算法的安全位数有关。

参考

1、https://www.zhihu.com/question/37203836/answer/70932036
2、格上不经意传输协议的分析与设计