密钥生成：运行
G
e
n
Gen
Gen，得到
(
f
,
f
−
1
)
(f,f^{-1})
(f,f−1)。令
p
k
=
f
,
s
k
=
f
−
1
pk=f,sk=f^{-1}
pk=f,sk=f−1。
加密算法：
E
(
⋅
)
=
f
(
⋅
)
E(\cdot)=f(\cdot)
E(⋅)=f(⋅)
解密算法：
D
f
−
1
(
⋅
)
=
f
−
1
(
⋅
)
D_{f^-1}(\cdot)=f^{-1}(\cdot)
Df−1(⋅)=f−1(⋅) 由于
f
(
⋅
)
f(\cdot)
f(⋅)是确定性的，例如RSA算法对于输入
x
x
x得到的
E
(
x
)
E(x)
E(x)是确定的，因此其不能用于构造出语义安全的公钥加密方案。我们需要对其进行“随机化”，引入随机比特。 令
H
=
{
h
K
:
{
0
,
1
}
K
→
{
0
,
1
}
}
K
≥
1
H=\{h_{\mathcal{K}}:\{ 0,1 \}^{\mathcal{K}} \rightarrow \{ 0,1 \}\}_{\mathcal{K} \geq 1}
H={hK:{0,1}K→{0,1}}K≥1，
F
F
F是一个陷门置换。
H
H
H是
F
F
F的一个随机比特，如果对于所有的PPT敌手
A
\mathcal{A}
A，存在一个可忽略的函数
ε
(
K
)
\varepsilon(\mathcal{K})
ε(K)，使得
A
\mathcal{A}
A在下面的对抗中，优势
A
d
v
A
(
K
)
≤
ε
(
K
)
{Adv}_{\mathcal{A}}(\mathcal{K}) \leq \varepsilon(\mathcal{K})
AdvA(K)≤ε(K)：
F
u
n
c
t
i
o
n
A
(
K
)
:
{Function}_{\mathcal{A}}(\mathcal{K}):
FunctionA(K):
(
f
,
f
−
1
)
←
G
e
n
(
K
)
(f,f^{-1}) \leftarrow Gen(\mathcal{K})
(f,f−1)←Gen(K)；
x
←
R
{
0
,
1
}
K
x \leftarrow _{R}\{ 0,1 \}^{\mathcal{K}}
x←R{0,1}K；
y
=
f
(
x
)
y=f(x)
y=f(x)； 返回
A
(
f
,
y
)
A(f,y)
A(f,y)
A
\mathcal{A}
A的优势定义为：
A
d
v
A
(
K
)
=
∣
P
r
[
F
u
n
c
t
i
o
n
A
(
K
)
=
h
K
(
x
)
]
−
1
2
∣
{Adv}_{\mathcal{A}}(\mathcal{K})=\lvert Pr[{Function}_{\mathcal{A}}(\mathcal{K})=h_{\mathcal{K}}(x)] - \frac{1}{2} \rvert
AdvA(K)=∣Pr[FunctionA(K)=hK(x)]−21∣。因为猜对随机比特的概率为
1
2
\frac{1}{2}
21，所以在这里可以减去
1
2
\frac{1}{2}
21当做
A
\mathcal{A}
A的优势。 下面构造随机比特： 设
h
K
′
(
x
∣
r
)
=
x
⋅
r
h_{\mathcal{K}}^{\prime}(x|r)=x \cdot r
hK′(x∣r)=x⋅r，
f
:
{
0
,
1
}
K
→
{
0
,
1
}
K
f:\{ 0,1 \}^{\mathcal{K}} \rightarrow \{ 0,1 \}^{\mathcal{K}}
f:{0,1}K→{0,1}K。定义一个新的置换
f
′
f^{\prime}
f′,
f
′
:
{
0
,
1
}
K
→
{
0
,
1
}
K
f^{\prime} : \{ 0,1 \}^{\mathcal{K}} \rightarrow \{ 0,1 \}^{\mathcal{K}}
f′:{0,1}K→{0,1}K定义为
f
′
(
x
∣
r
)
=
f
(
x
)
⊕
h
′
f^{\prime}(x|r)=f(x)\oplus h^{\prime}
f′(x∣r)=f(x)⊕h′，其中
h
′
h^{\prime}
h′为随机比特。 其中运算“
⋅
\cdot
⋅”表示二元点乘。若
x
=
x
1
x
2
⋯
x
K
∈
{
0
,
1
}
K
,
r
=
r
1
r
2
⋯
r
K
∈
{
0
,
1
}
K
x=x_1x_2 \cdots x_{\mathcal{K}} \in \{ 0,1 \}^{\mathcal{K}},r=r_1r_2 \cdots r_{\mathcal{K}} \in \{ 0,1 \}^{\mathcal{K}}
x=x1x2⋯xK∈{0,1}K,r=r1r2⋯rK∈{0,1}K，则
x
⋅
r
=
x
1
r
1
⊕
x
2
r
2
⊕
⋯
⊕
r
K
x
K
x \cdot r=x_1r_1 \oplus x_2r_2 \oplus \cdots \oplus r_{\mathcal{K}}x_{\mathcal{K}}
x⋅r=x1r1⊕x2r2⊕⋯⊕rKxK。 引入随机比特后的方案： 密钥产生过程：
G
e
n
K
e
y
(
K
)
:
GenKey(\mathcal{K}):
GenKey(K):
(
f
,
f
−
1
)
←
G
e
n
(
K
)
(f,f^{-1})\leftarrow Gen(\mathcal{K})
(f,f−1)←Gen(K)
r
←
R
{
0
,
1
}
K
r \leftarrow _{R}\{ 0,1 \}^{\mathcal{K}}
r←R{0,1}K
p
k
=
(
f
,
r
)
,
s
k
=
f
−
1
pk=(f,r),sk=f^{-1}
pk=(f,r),sk=f−1 加密过程（
M
M
M为待加密消息，
M
∈
{
0
,
1
}
M \in \{ 0,1 \}
M∈{0,1}）：
E
p
k
(
M
)
:
E_{pk}(M):
Epk(M):
x
←
R
{
0
,
1
}
K
x \leftarrow _{R}\{ 0,1 \}^{\mathcal{K}}
x←R{0,1}K
y
=
f
(
x
)
y=f(x)
y=f(x)
h
′
=
x
⋅
r
h^{\prime}=x \cdot r
h′=x⋅r 输出
(
y
,
h
′
⊕
M
)
(y,h^{\prime}\oplus M)
(y,h′⊕M) 解密过程（
b
b
b为
h
′
⊕
M
h^{\prime}\oplus M
h′⊕M）：
D
s
k
(
y
,
b
)
D_{sk}(y,b)
Dsk(y,b) 输出
b
⊕
(
f
−
1
(
y
)
⋅
r
)
b \oplus (f^{-1}(y) \cdot r)
b⊕(f−1(y)⋅r)
b
⊕
(
f
−
1
(
y
)
⋅
r
)
=
(
h
′
⊕
M
)
⊕
(
x
⋅
r
)
=
(
(
x
⋅
r
)
⊕
M
)
⊕
(
x
⋅
r
)
=
(
x
⋅
r
)
⊕
M
⊕
(
x
⋅
r
)
=
M
b \oplus (f^{-1}(y) \cdot r)=(h^{\prime}\oplus M) \oplus (x \cdot r)=((x \cdot r)\oplus M) \oplus (x \cdot r)=(x \cdot r) \oplus M \oplus (x \cdot r)=M
b⊕(f−1(y)⋅r)=(h′⊕M)⊕(x⋅r)=((x⋅r)⊕M)⊕(x⋅r)=(x⋅r)⊕M⊕(x⋅r)=M