通过两个实验来定义语义安全性
- 有一个试图攻击系统的敌人Adv. A。（类似于伪随机数生成器中的统计测试）
- 有两个Challenger，非常相似，用0或1来区分。
- 会做些什么呢？：
（1）从秘钥空间K中随机选择秘钥k；
（2）敌人会输出两条消息 m 0 m_{0} m0和 m 1 m_{1} m1，长度相等；
（3）观测敌人得到 m 0 m_{0} m0和 m 1 m_{1} m1加密行为是否不同；在实验1中得到了 m 1 m_{1} m1加密，实验0中得到了 m 0 m_{0} m0加密。如果在这两个实验中，他以相同的概率输出1，表明敌人无法区分实验0和1；如果敌人能够以明显不同的概率输出1，表明能够区分这两个实验。
定义事件：
F
o
r
b
=
0
,
1
W
b
:
=
[
e
v
e
n
t
t
h
a
t
E
X
P
(
B
)
=
1
]
For\ b = 0, 1\ \ \ W_b := [event\ that\ EXP(B) = 1]
For b=0,1 Wb:=[event that EXP(B)=1]
定义优势：敌人A相对方案E的语义安全优势，是这两个事件的概率之差。
A
d
v
s
s
[
A
,
E
]
:
=
∣
P
r
[
W
0
]
−
P
r
[
W
1
]
∣
∈
[
0
,
1
]
Adv_{ss}[A,E] := |Pr[W_0] - Pr[W_1]| ∈ [0,1]
Advss[A,E]:=∣Pr[W0]−Pr[W1]∣∈[0,1]
越接近0，越安全，越接近1，越容易区分，越不安全。
语义安全性定义
对于所有有效的攻击者A，如果
A
d
v
s
s
[
A
,
E
]
Adv_{ss}[A,E]
Advss[A,E]是可忽略的，则对称加密方案E是语义安全的。
=
>
f
o
r
a
l
l
e
x
p
l
i
c
i
t
m
0
,
m
1
∈
M
:
E
(
k
,
m
0
)
≈
P
E
(
k
,
m
1
)
=> for\ all\ explicit\ m_{0}, m_{1} ∈ M: {E(k,m_{0})} ≈_{P} {E(k,m_{1})}
=>for all explicit m0,m1∈M:E(k,m0)≈PE(k,m1)
敌人展示的这两条消息，无法区分。
举例
有一个损坏了的加密方案。有一个敌人A，给了ciphertext密文，总是能够推断出明文的最低有效位。如果语义是安全的，不会存在这样的敌人。
- Challenger随机挑选秘钥k，攻击者发送两条消息 m 0 m_{0} m0和 m 1 m_{1} m1，最低有效位分别是1和0。
- Challenger返回 m 0 m_{0} m0和 m 1 m_{1} m1的密文ciphertext。
- 敌人输出 m 0 m_{0} m0或 m 1 m_{1} m1的最低有效位。
这个敌人的语义安全优势是？
A
d
v
s
s
[
B
,
E
]
=
∣
P
r
[
E
X
P
(
0
)
=
1
]
−
P
r
[
E
X
P
(
1
)
=
1
]
∣
=
∣
0
−
1
∣
=
1
Adv_{ss}[B,E] = |Pr[EXP(0)=1] - Pr[EXP(1)=1]| = |0 - 1| = 1
Advss[B,E]=∣Pr[EXP(0)=1]−Pr[EXP(1)=1]∣=∣0−1∣=1
敌人仅仅推断出最低有效位，足以在语义安全的定义下，完全攻破了系统。知道任何1个位，语义都是不安全的。敌人A只需发2条消息，
m
0
、
m
1
m_{0}、m_{1}
m0、m1，使在A了解的一件事下值为0，另一件事值为1，比如A了解消息中所有位的异或XOR，那么A就能区分出
m
0
m_{0}
m0和
m
1
m_{1}
m1，足以攻破系统。如果一个密码在语义上是安全的，有效的攻击者是不会得到任何关于明文的任何信息。这是完美的安全性。注意是应用于有效的攻击者，而不是所有可能的攻击者。
OTP是语义安全的
假设有一个攻击者要打破一次性密码本的语义安全性，发送2条消息
m
0
m_{0}
m0和
m
1
m_{1}
m1，长度相等。得到
m
0
、
m
1
m_{0}、m_{1}
m0、m1的密文，试图区分。
for all A：
A
d
v
s
s
[
A
,
E
]
=
∣
P
r
[
A
(
k
⊕
m
0
)
=
1
]
−
P
r
[
A
(
k
⊕
m
1
)
=
1
]
∣
=
0
Adv_{ss}[A,E] = |Pr[A(k⊕m_{0})=1] - Pr[A(k⊕m_{1})=1]| = 0
Advss[A,E]=∣Pr[A(k⊕m0)=1]−Pr[A(k⊕m1)=1]∣=0
k
⊕
m
0
k⊕m_{0}
k⊕m0和
k
⊕
m
1
k⊕m_{1}
k⊕m1是均匀分布的，完全相同。所以A得到的输入是密文上的均匀分布。
=
>
=>
=>一次性密码本是语义安全的，对所有攻击者甚至不用限制是有效的，没有攻击者能够区分
k
⊕
m
0
k⊕m_{0}
k⊕m0和
k
⊕
m
1
k⊕m_{1}
k⊕m1。
接下来要证明一个安全的伪随机数生成器意味着流密码在语义上是安全的。
标签：Pr,语义,秘钥,m1,m0,攻击者,敌人,安全性 From： https://blog.csdn.net/sharloopSeason/article/details/143838306