收集一下各个paper中看到的各种Hardness Assumption，主要太多了猪脑过载记不住
根据不同的问题划分为几个大板块吧，不知道归类的就先丢在第六部分
Quick View
1.Discrete Logarithm：与计算离散对数困难相关的问题
2.Factoring：与计算大整数分解困难的问题
3.Product Groups：与两个阶数已知且为素数的群相关的困难问题，通常用于构造Paring-Based Cryptography
4.Pairings：主要关注两个阶数已知且为素数的群的配对，关于双线性配对具体可以看Pairing-Based Cryptography
5.Lattices：知识盲区，等sha老师补充
6.Miscellaneous：这部分就很多了，比如Groth16用的d-KEA等等，还有一些不知道怎么归类的也都放在这里
1.Discrete Logarithm
Discrete Logarithm
一个比较基础的假设，许多签名方案和承诺方案都有用到
- Discrete Logarithm：给定PPT算法$GroupGen$和安全参数$\lambda$，算法输出$(G,p,g)$，其中$q$为长度为$\lambda$-bit的素数，$G$为一阶为$p$的循环群，$g$为$G$的一个生成元，对于任意PPT算法$\mathcal A$，有
$$ Pr[x\leftarrow \mathcal A(G,p,g,y):y=g^x|(G,p,g)\leftarrow GroupGen(\lambda),y\leftarrow G]\leq \epsilon(\lambda) $$
其中$\epsilon(\cdot)$为一个可忽略的函数
Discrete Logarithm Relation
Original paper$[5]$
- Discrete Log Relation：对于任意PPT敌手$\mathcal A$，对于任意$n\ge 2$，存在一个可忽略的函数$\mu (\lambda)$，满足
$$ Pr[\mathbb G=Setup(1^\lambda),g_1,...,g_n\stackrel{\$}{\leftarrow} \mathbb G;a_1,...,a_n\in \Z _p\leftarrow (\mathcal A,g_1,...,g_n):\exist a_i\neq 0\wedge\prod_{i=1}^ng_i^{a_i}=1]\leq \mu(\lambda) $$
2.Factoring
Factoring Assumption
数论里面最基础，应用最广泛的假设之一
- Factoring Assumption：对于安全参数$\lambda$，给定一个生成器$Gen$用于两个长度为$\lambda$-bit的素数$p,q$和$n=pq$，对于任意PPT算法$\mathcal A$，
$$ Pr[(p,q)\leftarrow\mathcal A(n)|(n,p,q)\leftarrow Gen(\lambda)]\leq \epsilon(\lambda) $$
其中$\epsilon(\cdot)$为一个可忽略的函数
很多算法都用了这个假设，最经典的就是RSA了，RSA的安全性在于敌手无法分解模数$n$，从而无法计算私钥，目前的RSA都是2048 bits，也即$\lambda=2048$
RSA Assumption
- RSA Assumption：给定PPT算法$RSAGen$，该算法输入为安全参数$\lambda$，输出为RSA算法的参数$(n,e,d)$，其中$n$为两个长度为$\lambda$-bit的素数$p,q$的乘积，$e\in\Z^*_{\phi(n)},ed\equiv1 \ mod \ \phi(n)$，则对于任意PPT算法$\mathcal A$，有
$$ Pr[x\leftarrow \mathcal A(n,e,y):y=x^e \ mod \ n|(n,e,d)\leftarrow RSAGen(\lambda),y\leftarrow \Z^*_n]\leq\epsilon(\lambda) $$
其中$\epsilon(\cdot)$为一个可忽略的函数
RSA假设简单来说，就是知道公钥和密文，敌手无法解密出明文
Quadratic Residuosity Assumption
Original paper:$[1]$
对$x\in\N$，记$Z_x^*$为其缩系，记$Z^{+1}_x$为$Z_x^*$中Jacobi符号为$+1$的元素组成的集合，也即$Z^{+1}_x=\{y\in Z^*_x|(y|x)=+1\}$，其中$(y|x)$表示Jacobi符号，定义$Q_x(y)$如下
$$ \begin{cases} Q_x(y)=1,y \ is\ a\ quadratic \ residue \ mod\ x\\ Q_x(y)=0,otherwise \\ \end{cases} $$
然后Quadratic Residuosity Assumption定义如下
- Quadratic Residuosity Assumption：对于任意多项式大小的电路族$\{C_k|k\in N\}$，满足
$$ Pr[x\leftarrow Z_2(k);y\leftarrow Z^{+1}_x:C_k(x,y)=Q_x(y)]<\frac{1}{2}+\frac{1}{k^{-O(1)}} $$
2 or 3 Assumption
Original paper:$[2]$
先引入一个记法$Z_s(k)$，其中$s\geq 1$，表示长度为$k$比特的$s$个素数的乘积构成的集合，也即
$$ Z_s(k)=\{N|N=\prod_{i=1}^sp_i \} $$
其中$p_i$表示素数，2 or 3 Assumption如下
- 2 or 3 Assumption：对于任意正常数$c$和足够大的$k$，对于任意多项式大小的电路族$\{C_k|k\in N\}$，满足
$$ |P_{Z_2(k)}-P_{Z_3(k)}|<k^{-c} $$
其中$P_{Z_2(k)}=Pr[x\leftarrow Z_2(k):C_k(x)=1],P_{Z_3(k)}=Pr[x\leftarrow Z_3(k):C_k(x)=1]$
2 or 3 Assumption简单来说就是，任意多项式大小的电路族无法区分一个整数是两个素数的乘积还是三个素数的乘积
2OR3A是一个比Deciding QR还困难的假设
3.Product Groups
4.Pairings
5.Lattices
6.Miscellaneous
Knowledge of Exponent Assumption$(KEA1)$
Original paper:$[3]$
记$p$为一大素数，且满足$2p+1$也为素数，记$g$是$\Z ^*_{2p+1}$的子群的生成元，该子群的阶为$p$
假设给定输入$(p,g,g^a)$，要求算法输出$(C,Y)=(C,C^a)$，敌手在不知道$a$的情况下，其只有一种方法生成$(C,Y)$，也即随机选择$c\in \Z_p$，令$C=g^c,Y=(g^a)^c$
- Knowledge of Exponent Assumption(KEA1)：对于任意敌手$\mathcal A$，给定输入$(p,g,g^a)$，输出$(C,Y)=(C,C^a)$，则存在一个抽取器$\mathcal {\bar A}$，满足
$$ Pr[c\leftarrow \mathcal {\bar A}(p,g,g^a):C=g^c\ |\ (C,Y)\leftarrow \mathcal A(p,g,g^a):Y=C^a]\geq1-negl $$
KEA1描述的是敌手在不知道$a$的情况下只有这一种方法生成$(C,Y)$，换言之，若敌手可以生成这样的$(C,Y)$，则意味着他以极大概率知道某个$c\in \Z_p$，满足$C=g^c$
KEA2
Original paper:$[4]$
在KEA1的基础上再加了一个指数
- KEA2：对于任意敌手$\mathcal A$，给定输入$(p,g,g^a,g^b,g^{ab})$，输出$(C,Y)=(C,C^b)$，则存在一个抽取器$\mathcal {\bar A}$，满足
$$ Pr[c\leftarrow \mathcal {\bar A}(p,g,g^a,g^b,g^{ab}):C=g^c \vee C=(g^a)^c \ |\ (C,Y)\leftarrow \mathcal A(p,g,g^a,g^b,g^{ab}):Y=C^b]\geq1-negl $$
这里敌手在不知道$a,b$的情况下有两种方式生成$(C,Y)$
- 选择$c\in \Z_p$，令$C=g^c,Y=(g^b)^c$
- 选择$c\in \Z_p$，令$C=(g^a)^c,Y=(g^{ab})^c$
KEA2描述的是敌手在不知道$a,b$的情况下只有这两种方法生成$(C,Y)$，换言之，若敌手可以生成这样的$(C,Y)$，则意味着他以极大概率知道某个$c\in \Z_p$，满足$C=g^c$或$C=(g^{ab})^c$
但是原始论文中指出了KEA2是错误的==（具体错在哪没仔细看）==
KEA3
Original paper:$[4]$
在KEA2的基础上做了一些小修改
- KEA3：对于任意敌手$\mathcal A$，给定输入$(p,g,g^a,g^b,g^{ab})$，输出$(C,Y)=(C,C^b)$，则存在一个抽取器$\mathcal {\bar A}$，满足
$$ Pr[c\leftarrow \mathcal {\bar A}(p,g,g^a,g^b,g^{ab}):C=g^c \vee C=(g^a)^c \ |\ (C,Y)\leftarrow \mathcal A(p,g,g^a,g^b,g^{ab}):Y=C^b]\geq1-negl $$
The q-Power Knowledge of Exponent Assumption
Original paper:$[5]$
q-PKE假设实际上时KEA和KEA3的广义化，意思是给定$(g,g^x,...,g^{x^q},g^{\alpha x},...,g^{\alpha x^q})$，敌手无法在不知道$(a_0,...,a_q)$的情况下构造$c=\prod ^q_{i=0}(g^{x^i})^{a_i}$和$\hat c=\prod ^q_{i=0}(g^{\alpha x^i})^{a_i}$，满足$\hat c =c^\alpha$
利用Bellare和Palacio[BP04]中的记法，记$(y;z)\larr (\mathcal A||\chi_\mathcal A)(x)$表示$\mathcal A$输入$x$输出$y$，$\chi_\mathcal A$输入相同的$x$但是输出$z$
Definition 1(q-PKE)：$q(k)$-power knowledge of exponent assumption，说的是对于群 $\mathcal G$，满足对于任意的非均匀PPT时间敌手$\mathcal A$，存在一个非均匀PPT抽取器$\chi_\mathcal A$，满足
$$ Pr[(p,G,G_T,e)\larr \mathcal g(1^k);g\larr G\backslash\{1\};\alpha,x\larr \Z^*_p;\sigma=(p,G,G_T,e,g,g^x,...,g^{x^q},g^{\alpha x},...,g^{\alpha x^q});(c,\hat c;a_0,...,a_q)\larr (\mathcal A||\chi_\mathcal A)(\sigma):\hat c=c^\alpha\wedge c\neq \prod ^n_{i=0}g^{a_ix^i}=0] $$
太长了可能博客显示不出来，给个截图
The q-Computational power Diffie-Hellman Assumption
Original paper:$[5]$
The q-Computational power Diffie-Hellman Assumption：也即给定$(g,g^x,...,g^{x^q},g^\beta,g^{\beta x},...,g^{\beta x^q})$，难以计算出缺失的某个元素$g^{\beta x^j}$
CDH假设是给定$g,g^\beta,g^x$，难以计算$g^{\beta x}$，q-CPDH实际上是对CDH的广义化
Definition 2(q-CPDH)：$q(k)$-computational power Diffie-Hellman assumption，说的是对于群$\mathcal G$和所有的$j\in \{0,1,...,q\}$、所有的非均匀PPT敌手$\mathcal A$，满足
$$ Pr[(p,G,G_T,e)\larr \mathcal g(1^k);g\larr G\backslash\{1\};\beta,x\larr \Z^*_p;\sigma=(p,G,G_T,e,g,g^x,...,g^{x^q},g^\beta,g^{\beta x},...,g^{\beta x^{j-1}},g^{\beta x^{j+1}},...,g^{\beta x^q}):y=g^{\beta x^j}]\approx 0 $$
The q-strong Diffie-Hellman Assumption
Original paper$[6,7]$
Definition(q-SDH)：对于群$\mathcal G$和任意敌手$\mathcal A$，满足
$$ Pr[(p,\mathbb G,\mathbb G_T,e)\larr \mathcal G(1^k);g\larr \mathbb G\backslash\{1\};s\larr \Z^*_p;\mathcal \sigma\larr (p,\mathbb G,\mathbb G_T,e,g,g^s,...,g^{s^q});y\larr \mathcal A(\sigma):y=e(g,g)^{\frac{1}{s+c}},c\in \Z^*_p]=negl(k) $$
Reference
$[1]$ Shafi Goldwasser, Silvio Micali:Probabilistic Encryption. J. Comput. Syst. Sci. 28(2): 270-299 (1984)
$[2]$ Manuel Blum, Paul Feldman, Silvio Micali:Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract). STOC 1988: 103-112
$[3]$ Ivan Damgård:Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks. CRYPTO 1991: 445-456
$[4]$ Mihir Bellare, Adriana Palacio:The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols. IACR Cryptol. ePrint Arch. 2004: 8 (2004)
$[6]$ Dan Boneh, Xavier Boyen:Short Signatures Without Random Oracles. EUROCRYPT 2004: 56-73
$[7]$ Rosario Gennaro:Multi-trapdoor Commitments and Their Applications to Proofs of Knowledge Secure Under Concurrent Man-in-the-Middle Attacks. CRYPTO 2004: 220-236