Paper reference: Public Key Encryption with Keyword Search | SpringerLink

PEKS using Bilinear Maps#

Construction#

素数p阶群, （乘法群）定义双线性映射：#

非退化性：

• $e(g,g) \rightarrow g' , \; where \; g' \; is \; a \; generator \; of \; G_2$

Hash functions:#

• $H_1: \{0,1\}^* \rightarrow G_1$
• $H_2 : G_2 \rightarrow \{0,1\}^{\log{p}}$

PEKS Scheme#

KeyGen:#

input 安全参数$\lambda$ , 群阶p, $G_1$ ,$G_2$ ，$\alpha \xleftarrow{\text\$} Z^*_p$, g是 $G_1$ 的一个生成元

output $A_{pub} = [g,h=g^\alpha] \; and \; A_{priv} =\alpha$

一个典型的RSA公私钥分发

PEKS($A_{pub},W$):#

$r \xleftarrow{\text\$} Z^*_p$ , then compute $t = e(H_1(W),h^r)$

output $S=[g^r,H_2(t)]$

$Trapdoor(A_{priv},W) => T_W =H_1(W)^\alpha$#

Notice that $t ∈ G_2$  and $T_W ∈ G_1$

Test($A_{pub}$, S, $T_W$)#

S=[A,B]

output $H_2(e(T_W,A)) == B$

proof:#

BDH Assumption#

“Bilinear Diffie-Hellman Problem (BDH): Fix a generator g of G1. The BDH problem is as follows: given g, ga, gb, gc ∈ G1 as input, compute e(g, g)abc ∈ G2. We say that BDH is intractable if all polynomial time algorithms have a negligible advantage in solving BDH.” (Boneh et al., 2004, p. 512)

安全性证明#

定理1. 非交互式PEKS在适应性选择关键词攻击下具有语义安全，如果BDH是难解问题。#

• 安全目标：在自适应选择关键词攻击下语义安全。

• ​归约到BDH问题：

  • 假设存在攻击者 A 能以优势 ϵ 区分关键词加密，构造算法 B 利用 A 解决BDH问题。

  • ​模拟过程：

    1. B 接收BDH挑战 $(g,g^α,g^β,g^γ)$ ，模拟公钥 $h=g^α$ 。

    2. 对 A 的陷门查询，若关键词关联 $g^β$ ，则终止；否则返回合法陷门。

    3. 挑战阶段，随机选择 $W^b$ ​，构造密文 $(g^γ,H_2​(e(g^β,g^{αγ})))$ 。

    4. 攻击者成功时，B 从哈希列表提取 $e(g,g)^{αβγ}$ 。

• ​优势分析：

  • B 的成功概率为 $ϵ/(e \cdot q_T \cdot ​q_{H_2}​​ )$ ，其中 $q_T$ ​ 为陷门查询次数， $q_{H_2}$ ​​ 为哈希查询次数。