点个关注吧谢谢！
有需要论文知道、审稿，申博资料准备，答辩等的可以私信
五、Common Reference String公共字符串
设定
q
=
n
2
+
3
n
−
2
q=n^2+3n-2
q=n2+3n−2，然后定义三个集合。可以看到三个集合中的元素个数远小于集合
[
q
]
=
{
1
,
2
,
.
.
.
,
q
}
[q]=\{1,2,...,q\}
[q]={1,2,...,q}的元素个数。（在后续文章可以看到这样划分的原因）
分别调用Restriction Argument的公共字符串生成算法。
Proof
下面来证明前面文章用到的引理1：即找不到一组非零元素使得
∑
i
=
0
q
a
i
x
i
=
0
\sum_{i=0}^qa_ix^i=0
∑i=0qaixi=0
证：假设存在敌手能找到一组非零元素使得
∑
i
=
0
q
a
i
x
i
=
0
\sum_{i=0}^qa_ix^i=0
∑i=0qaixi=0，那么可以构造算法破解q-CPDH困难性问题（见前文）。
- 挑战者收到q-CPDH问题实例 p , G , G T , e , g , g x , . . , g x q , g β , g β x , . . . , g β x j − 1 , g β x j + 1 . . . , g β x q 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} p,G,GT,e,g,gx,..,gxq,gβ,gβx,...,gβxj−1,gβxj+1...,gβxq.
- 挑战者将 p , G , G T , e , g , g x , . . , g x q p,G,G_T,e,g,g^x,..,g^{x^q} p,G,GT,e,g,gx,..,gxq发送给敌手，如果敌手计算出 x x x，那么就可以计算出 ( g β ) x j (g^\beta)^{x^j} (gβ)xj。
- 挑战者计算出四组公共字符串，并将其发送给敌手
- 如果敌手计算出非零元素使得 ∑ i = 0 q a i x i = 0 \sum_{i=0}^qa_ix^i=0 ∑i=0qaixi=0，那么可以求出该多项式 q q q个解，然后以此尝试找出 x x x使得 g 1 = g x g_1=g^x g1=gx，然后可以计算 ( g β ) x j (g^\beta)^{x^j} (gβ)xj.
生成的公共字符串均可以通过下列等式进行验证，e.g:
∀
i
∈
[
q
]
:
e
(
g
,
g
i
+
1
)
=
e
(
g
,
g
x
i
+
1
)
=
e
(
g
x
,
g
x
i
)
\forall i\in [q]: e(g,g_{i+1})=e(g,g^{x^{i+1}})=e(g^x,g^{x^i})
∀i∈[q]:e(g,gi+1)=e(g,gxi+1)=e(gx,gxi)
e
(
g
,
g
^
i
)
=
e
(
g
,
g
i
α
^
)
=
e
(
g
^
,
g
i
)
e(g,\hat{g}_i)=e(g,g_i^{\hat{\alpha}})=e(\hat{g},g_i)
e(g,g^i)=e(g,giα^)=e(g^,gi)
∀
i
∈
S
~
:
e
(
g
,
h
~
i
)
=
e
(
g
,
g
i
β
~
)
=
e
(
h
~
,
g
i
)
\forall i\in \tilde{S}: e(g,\tilde{h}_i)=e(g,g_i^{\tilde{\beta}})=e(\tilde{h},g_i)
∀i∈S~:e(g,h~i)=e(g,giβ~)=e(h~,gi)
其余的类似。
