公钥加密系统中析取范式的查询方法

摘要

本发明公开了一种公钥加密系统中析取范式的查询方法，包括步骤：(1)随机选取安全参数，并选择2n+3个随机数α

说明书

技术领域

本发明涉及计算机信息安全领域，更具体地说，本发明涉及一种公 钥加密系统中析取范式的查询方法。

背景技术

公钥系统是这样一个系统：密钥是由信息的接收者成对生成的，每 对密钥由一个公钥和一个私钥组成，公钥为公开的，而私钥由接收者自 己秘密保存。任何发送者可以用公钥加密信息并发送给接收者，而此加 密信息只能由拥有对应私钥的接收者才能解密。析取范式关键词查询是 为了检测一个文档的关键词列表中是否包含至少一个用户想要查询的关 键词。假设文档关键词列表中的关键词集合为A，用户想要查询的关键 词为B，那么析取范式关键词查询就是为了查询那些A∪B≠Θ的文档。此 处，Θ代表空集。

现有的在密文上支持析取范式关键词查询使用内积的方法。该方法 通过把关键词集合A映射成一组向量X，把关键词集合B映射成V，然 后在不解密的情况下通过计算X·V是否为0来判断A∪B是否为空集。通 过此方法，来达到在不解密的情况下进行密文上的析取范式关键词查询。

通过使用以上的方法，虽然能解决析取范式关键词查询，但是由于 将关键词映射到一组向量上，会引起系统空间和时间复杂度的指数型上 升。

发明内容

本发明的目的在于提供一种公钥加密系统中析取范式的查询方法， 其能够建立一个关键词域无关的公钥密钥体制下的进行析取关键词查询 体系和方法。

一种公钥加密系统中析取范式的查询方法，包括以下步骤：

(1)随机选取安全参数，并选择2n+3个随机数α₀，α₁，...，α_n，β₀，β₁，...，β_n， 其中n为整数，q为素数，Z_q^*是在q上的乘法群；

(2)根据以下公式对安全参数和随机数进行计算，以得到公共密钥 pk和秘密密钥sk：

$\mathrm{pk}=\{X_0=g^{{\alpha }_0},X_1=g^{\alpha 1},...,X_n=g^{{\alpha }_n},Y_0=g^{{\beta }_0},Y_1=g^{{\beta }_1},...,Y_n=g^{{\beta }_n},Z=g^{\theta },\mu =\hat{e}(g,g)\}$$,\mathrm{sk}=\{{\alpha }_0,{\alpha }_1,...,{\alpha }_n,{\beta }_0,{\beta }_1,...,{\beta }_n,\theta \in Z_q^{*}\},$其中G₁，G₂为两个循环群，q是循环群 的阶数且为素数，g为G₁的任一生成元，为双线性配对函数，且 $\hat{e}:G_1\times G_1\to G_2;$

(3)对公共密钥pk和一组关键词集合W＝{W₁，W₂，...，W_n}进行计算， 以得到索引I_w，并对秘密密钥sk和另一组关键词集合Q＝{Q₁，Q₂，...，Q_m}进 行计算，以得到陷门T_Q，具体包括以下子步骤：

(31)选择n²+2n个随机数r₁，r₂，...，r_n和其中i∈[1，n]， j∈[0，n]；

(32)对于每个W_i∈W，计算$A_{\mathrm{ij}}=X_j^{r_i}\times g^{r_i{H}_1{\left(W_i\right)}^j+u_{\mathrm{ij}}}=g^{r_i({\alpha }_j+H_1{\left(W_i\right)}^j)+u_{\mathrm{ij}}},$$B_{\mathrm{ij}}=Y_j^{u_{\mathrm{ij}}}=g^{{\beta }_j{u}_{\mathrm{ij}}},$$C_i=Z^{r_i}=g^{\theta r_i},$$D_i=H_2\left({\mu }^{r_i}\right),$其中i∈[1，n]，$H_1:\left\{\mathrm{0,1}\right\}*\to {\left\{\mathrm{0,1}\right\}}^{{\log }_2^q}$和$H_2:G_2\to {\left\{\mathrm{0,1}\right\}}^{{\log }_2^q}$为两个哈希函数；

(33)根据以上公式得到索引I_w：

$I_w=\left(\begin{array}{cccccccccccccc}{A}_{10}& A_{11}& ·& ·& ·& A_{1n}& B_{10}& B_{11}& ·& ·& ·& B_{1n}& C_1& D_1\\ A_{20}& A_{21}& ·& ·& ·& A_{2n}& B_{20}& B_{21}& ·& ·& ·& B_{2n}& C_2& D_2\\ ·& ·& & ·& & ·& ·& ·& & ·& & ·& ·& ·\\ ·& ·& & ·& & ·& ·& ·& & ·& & ·& ·& ·\\ ·& ·& & ·& & ·& ·& ·& & ·& & ·& ·& ·\\ A_{n0}& A_{n1}& ·& ·& ·& A_{\mathrm{nn}}& B_{n0}& B_{n1}& ·& ·& ·& B_{\mathrm{nn}}& C_n& D_n\end{array}\right)$

(34)选择s-m个随机关键词{w₁，w₂，...，w_s-m}，其中m≤s≤n；

(35)构建一个s阶多项式f(x)＝a_sx^s+a_s-1x^s-1+...+a₁x¹+a₀，f(x)具 有s个根为H₁(Q₁)，H₁(Q₂)，...H₁(Q_m)，H₁(w₁)，H₁(w₂)，...，H₁(w_s-m)；

(36)选择一个随机数u∈Z_q，计算出$T_{1j}=g^{\frac{a_j}{{\Sigma }_{j=0}^s{a}_j{a}_j+{\Sigma }_{j=0}^s{a}_j\mathrm{u\theta }}},$$T_{2j}=T_{1j}^{\frac{1}{{\beta }_j}},$

其中j∈[0，s]，并令T₃＝u，Z_q是在q上的整数群；

(37)根据以上公式得到陷门为T_Q＝(T₁₀，...，T_1s，T₂₀，...，T_2s，T₃)；

(4)根据索引I_w、陷门T_Q和公共密钥pk确定关键词集合 W＝{W₁，W₂，...，W_n}是否与关键词集合Q＝{Q₁，Q₂，...，Q_m}匹配，具体包括子步 骤：

(41)设置计数器v＝0；

(42)判断v不大于n；

(43)若v不大于n，则检查以下等式是否成立：$H_2\left(\frac{{\mathrm{test}}_{i1}}{{\mathrm{test}}_{i2}}\right)=D_i,$其中i∈[1，n]，${\mathrm{test}}_{i1}={\Pi }_{j=0}^s\hat{e}(T_{1j},A_{\mathrm{ij}}{C}_i^{T_3}),$${\mathrm{test}}_{i2}={\Pi }_{j=0}^s\hat{e}(T_{2j},B_{\mathrm{ij}});$

(44)若等式成立，则表示二者匹配，并输出1。

上述步骤(4)进一步包括：若v大于n，则表示二者不匹配，并输 出0。

上述步骤(4)进一步包括：若等式不成立，则设置v＝v+1，并返回 步骤(42)。

本发明具有以下优点：

1.本发明支持多关键词检索的需求；

2.本发明可以不利用关键词域作为辅助信息；

3.本发明空间和时间复杂度为O(n²)。这里n为一个文档的关键词列 表中关键词的个数。

附图说明

图1是本发明公钥加密系统中析取范式的查询方法的流程图。

图2是本发明查询方法中步骤(3)的细化流程图。

图3是本发明查询方法中步骤(4)的细化流程图。

具体实施方式

以下结合附图对本发明进行具体描述。

如图1所示，本发明公钥加密系统中析取范式的查询方法包括以下 步骤：

(1)随机选取安全参数，并选择2n+3个随机数α₀，α₁，...，α_n，β₀，β₁，...，β_n， 其中n为整数，q为素数，Z_q^*是在q上的乘法群；

(2)根据以下公式对安全参数和随机数进行计算，以得到公共密钥 pk和秘密密钥sk：

$\mathrm{pk}=\{X_0=g^{{\alpha }_0},X_1=g^{\alpha 1},...,X_n=g^{{\alpha }_n},Y_0=g^{{\beta }_0},Y_1=g^{{\beta }_1},...,Y_n=g^{{\beta }_n},Z=g^{\theta },\mu =\hat{e}(g,g)\}$$,\mathrm{sk}=\{{\alpha }_0,{\alpha }_1,...,{\alpha }_n,{\beta }_0,{\beta }_1,...,{\beta }_n,\theta \in Z_q^{*}\},$其中G₁，G₂为两个循环群，q是循环群 的阶数且为素数，g为G₁的任一生成元，为双线性配对函数，且 $\hat{e}:G_1\times G_1\to G_2;$

(3)对公共密钥pk和一组关键词集合W＝{W₁，W₂，...，W_n}进行计算， 以得到索引I_w，并对秘密密钥sk和另一组关键词集合Q＝{Q₁，Q₂，...，Q_m}进 行计算，以得到陷门T_Q；

(4)根据索引I_w、陷门T_Q和公共密钥pk确定关键词集合 W＝{W₁，W₂，...，W_n}是否与关键词集合Q＝{Q₁，Q₂，...，Q_m}匹配。

如图2所示，上述步骤(3)包括以下子步骤：

(31)选择n²+2n个随机数r₁，r₂，...，r_n和其中i∈[1，n]， j∈[0，n]；

(32)对于每个W_i∈W，计算$A_{\mathrm{ij}}=X_j^{r_i}\times g^{r_i{H}_1{\left(W_i\right)}^j+u_{\mathrm{ij}}}=g^{r_i({\alpha }_j+H_1{\left(W_i\right)}^j)+u_{\mathrm{ij}}},$$B_{\mathrm{ij}}=Y_j^{u_{\mathrm{ij}}}=g^{{\beta }_j{u}_{\mathrm{ij}}},C_i=Z^{r_i}=g^{\theta r_i},D_i=H_2\left({\mu }^{r_i}\right),$其中i∈[1，n]，$H_1:\left\{\mathrm{0,1}\right\}*\to {\left\{\mathrm{0,1}\right\}}^{{\log }_2^q}$和$H_2:G_2\to {\left\{\mathrm{0,1}\right\}}^{{\log }_2^q}$为两个哈希函数；

(33)根据以上公式得到索引I_w：

$I_w=\left(\begin{array}{cccccccccccccc}{A}_{10}& A_{11}& ·& ·& ·& A_{1n}& B_{10}& B_{11}& ·& ·& ·& B_{1n}& C_1& D_1\\ A_{20}& A_{21}& ·& ·& ·& A_{2n}& B_{20}& B_{21}& ·& ·& ·& B_{2n}& C_2& D_2\\ ·& ·& & ·& & ·& ·& ·& & ·& & ·& ·& ·\\ ·& ·& & ·& & ·& ·& ·& & ·& & ·& ·& ·\\ ·& ·& & ·& & ·& ·& ·& & ·& & ·& ·& ·\\ A_{n0}& A_{n1}& ·& ·& ·& A_{\mathrm{nn}}& B_{n0}& B_{n1}& ·& ·& ·& B_{\mathrm{nn}}& C_n& D_n\end{array}\right)$

(34)选择s-m个随机关键词{w₁，w₂，...，w_s-m}，其中m≤s≤n；

(35)构建一个s阶多项式f(x)＝a_sx^s+a_s-1x^s-1+...+a₁x¹+a₀，f(x)具 有s个根为H₁(Q₁)，H₁(Q₂)，...H₁(Q_m)，H₁(w₁)，H₁(w₂)，...，H₁(w_s-m)；

(36)选择一个随机数u∈Z_q，计算出$T_{1j}=g^{\frac{a_j}{{\Sigma }_{j=0}^s{a}_j{a}_j+{\Sigma }_{j=0}^s{a}_j\mathrm{u\theta }}},$$T_{2j}=T_{1j}^{\frac{1}{{\beta }_j}},$其中j∈[0，s]，并令T₃＝u，Z_q是在q上的整数群；

(37)根据以上公式得到陷门为T_Q＝(T₁₀，...，T_1s，T₂₀，...，T_2s，T₃)。 如图3所示，上述步骤(4)包括以下子步骤：

(41)设置计数器v＝0；

(42)判断v不大于n，若v不大于n，则转入步骤(43)，否 则转入步骤(46)；

(43)检查以下等式是否成立：$H_2\left(\frac{{\mathrm{test}}_{i1}}{{\mathrm{test}}_{i2}}\right)=D_i,$其中i∈[1，n]， ${\mathrm{test}}_{i1}={\Pi }_{j=0}^s\hat{e}(T_{1j},A_{\mathrm{ij}}{C}_i^{T_3}),$${\mathrm{test}}_{i2}={\Pi }_{j=0}^s\hat{e}(T_{2j},B_{\mathrm{ij}}),$w若等式成立，则转入步 骤(44)，否则转入步骤(45)；

(44)表示二者匹配，并输出1；

(45)设置v＝v+1，并返回步骤(42)；

(46)表示二者不匹配，并输出0。