目录
=
子群决策问题
关于子群决策问题主要是可以，在上篇文章中总结过：
归约证明（Reduction Proof）
对密码体制安全性证明：
参考
一般来说密码学的方案或者协议Π都是建立在某个困难问题上面，例如RSA公钥加密体制j建立在因数分解， 这个困难问题记作P
条件命题：只要P是安全的（难以解决的） 那么我们的方案Π 就是安全的。 同样的P 能够被安全攻破，那么Π就不再安全。
但是直接去证明这个条件命题是很困难的，我们一般采取从他的逆否命题入手。
PPT:概率多项式时间
在这里我的理解是：从反证法入手，困难问题是作为已知、公认的前提条件。假设存在可以攻破方案的敌手，且拥有的优势为
?
(
t
)
\epsilon(t)
?(t),会建立与攻破困难问题的敌手的假设，通过概率来判断，达到了敌手攻破困难问题的证明。
原文的安全证明
这是原文关于BGN安全性证明。
理解
这里我的理解是，对于
B
\mathcal{B}
B产生的两条消息
m
0
,
m
1
m_0,m_1
m0?,m1?,
A
\mathcal{A}
A会对其中一个进行加密
C
=
g
m
b
x
r
∈
G
C=g^{m_{b}}x^{r}∈\mathbb{G}
C=gmb?xr∈G，然后给
B
\mathcal{B}
B，进行挑战攻破。这里设计到对与
x
x
x属于哪一个群的讨论，如果
x
∈
G
x∈\mathbb{G}
x∈G那么
B
\mathcal{B}
B，只能是纯猜测，概率为
P
[
b
′
=
n
]
=
1
/
2
P[b'=n]=1/2
P[b′=n]=1/2,无法攻破该方案，如果
x
∈
G
的一个子群
x∈\mathbb{G}的一个子群
x∈G的一个子群，那么这个情况下，那么给
B
\mathcal{B}
B的挑战是一个真正的语义安全游戏，
P
[
b
′
=
n
]
>
1
/
2
+
?
(
t
)
P[b'=n]>1/2+\epsilon(t)
P[b′=n]>1/2+?(t) 因为
B
\mathcal{B}
B是假设以一个
?
(
t
)
\epsilon(t)
?(t)的优势来攻破这个方案的，那么拥有同样优势的
A
\mathcal{A}
A在解决困难问题优势也是不可忽略：
这样就证明了逆否命题条件的成立！
关于这部分的内容，我自己感觉还是有点难理解，对于不同的加密体制的安全性证明中所使用的方法细节也值得好好思考~