一种集合成员关系判定的密码学构造方法及系统

摘要

本发明实施例公开了一种集合成员关系判定的密码学构造方法及系统，能够对集合成员关系进行密码学表示，所述方法包括：将集合U中的每个元素e

说明书

技术领域

本发明涉及信息技术领域，特别是指一种集合成员关系判定的密码学构造 方法及系统。

背景技术

元素与集合之间的“属于”和“不属于”是最常见的二元关系，给定集合 U＝{e₁，…，e_n}，对任意子集属于关系通常用∈表示，如e∈S，表示元素e 存在于子集S中；同样的，不属于关系通常用表示，如表示元素e不 存在于子集S中。当集合S只有一个元素时，退化为元素“相等”和“不相等” 关系；如对其扩展，还能得到子集“包含”和“非包含”关系，以及集合“相 等”与“不相等”关系等。

在密码学中常用“属于”与“不属于”关系实现元素与集合间关系的判定， 即，表示对给定元素e是否存在于(或不存在于)S中的一个判定。如果要求 这种判定是密码学安全的，则当e∈S(或)时，任何人不能向他人宣称 错误关系(或e∈S)，或者说任何人不能伪造判定(或e∈S)。

密码学集合操作在安全协议设计与安全计算领域中具有重要的理论价值 与应用价值，可实现基于集合的广播加密、具有属于和非逻辑的基于属性加密、 集合关系的谓词加密、基于集合的隐私保护关键字检索等方案。密码学“属于” 关系与“不属于”关系本质上是密码学的安全计算技术，是保证网络及计算机 系统下信息安全的基本技术，可广泛在电子商务、电子政务、网上交易、甚至 军用网络中进行应用。

例如，在面向群组的广播加密中，数据发送者可能希望指定某些用户进行 解密信息，那么他只需要将这些指定用户生成集合S；依靠密码学属于关系实 现算法，可对任意用户e是否属于该集合S进行密码学判定：如果e∈S，那么 可以进行解密；否则，即使用户具有以往的授权也是无法实现解密。

再如，基于属性的加密中，某一属性由不同属性值构成集合，例如，城市 ＝{北京、上海、深圳、伦敦、纽约、……}，消息发送者可以从该集合中选择 一些属性值构成“授权”解密的属性值子集或“非授权”解密的属性值子集，并用 此子集对消息进行加密得到密文。同时，该密码系统内的每名成员具有一组属 性值及对应的属性值密钥来标识自己的身份，依靠本专利中密码学属于关系实 现算法，当一个接收者试图解密时，他将自己的属性值与属性值密钥与密文中 的加密子集进行比对，如果满足子集中“属于”或“不属于”的要求，那么他 能够正确解密出消息。目前，密码学研究中尚无法对集合成员关系进行密码学 表示。

发明内容

本发明要解决的技术问题是提供一种集合成员关系判定的密码学构造方 法及系统，以解决现有技术所存在的无法对集合成员关系进行密码学表示的问 题。

为解决上述技术问题，本发明实施例提供一种集合成员关系判定的密码学 构造方法，包括：

获取给定任意集合U{e₁，…，e_n}，将集合U中的每个元素e_i转化为密码学空 间内的随机点v_i；

获取给定集合根据所述随机点v_i确定集合S中的每个元 素e_i'对应的随机点v_i'，并根据所述随机点v_i'构造函数f_S(x)；

引入一个随机秘密γ，根据所述函数f_s(x)确定f_s(γ)，并根据所述随机秘密 γ确定公开参数mpk；

通过密码学方法，以所述公开参数mpk作为输入对f_S(γ)进行处理生成所述 集合S的密码学表示。

可选地，所述随机点包括：随机数或随机向量；

所述根据所述随机点v′_i构造函数包括：

将集合S中每个元素e_i'对应的随机点v_i'作为H(x)的零点构造零点多项式 函数f_S(x)；或者

将集合S中每个元素e′_i对应的随机点v′_i作为H(x)的极点构造极点多项式 函数f_s(x)；

其中，H(x)＝P(x)/Q(x)是一个有理多项式，表示两个多项式P(x)和Q(x)相 除，对于一个变量z，当P(z)＝0时，P(x)的根z称为H(x)的零点，当Q(z)＝0时， Q(x)的根z被称为H(x)的极点；

所述构造函数还包括：由所述随机点v′_i构造的拉格朗日插值多项式、牛顿 插值多项式、埃尔米特插值多项式、伯恩斯坦多项式、斐波那契多项式、二项 式型多项式或相应代数曲线。

可选地，所述通过密码学方法，以所述公开参数mpk作为输入对f_S(γ)进行 处理生成所述集合S的密码学表示包括：

通过密码学方法，以所述公开参数mpk作为输入对f_S(γ)进行处理生成所述 集合S的聚合函数Aggregate(mpk,S)，当所述函数f_s(x)为零点多项式时，该聚合 函数称为零点聚合函数ZerosAggr(mpk，S)，当所述函数f_s(x)为极点多项式时，该 聚合函数称为极点聚合函数PolesAggr(mpk，S)；

通过所述聚合函数将所述集合S压缩成确定长度的随机数或随机向量R_S， R_S是所述聚合函数Aggregate(mpk,S)的输出聚合值，且R_S的长度与所述集合S中 元素个数无关。

可选地，所述通过所述聚合函数将所述集合S压缩成确定长度的聚合值R_S之后包括：

通过所述聚合函数构造密码学判定算法对元素与元素之间等于和不等于 关系进行判定；和/或

通过所述聚合函数构造密码学判定算法对元素与集合之间属于和不属于 关系进行判定；和/或

通过所述聚合函数构造密码学判定算法对集合与集合之间包含和不包含 关系进行判定。

可选地，所述通过所述聚合函数构造密码学判定算法对元素与集合之间属 于关系进行判定包括：

获取元素e_i，当e_i∈S时，令S_-＝S\{e_i}，则聚合值R_S-由零点聚合函数 ZerosAggr(mpk，S)确定；

当时，令S_-＝S\{e_i}，则聚合值R_S-不能由任何多项式时间算法确定， 所述多项式时间算法包括：ZerosAggr(mpk，S)；

所述通过所述聚合函数构造密码学判定算法对元素与集合之间不属于关 系进行判定包括：

获取元素e_i，当时，令S₊＝S∪{e_i}，则聚合值由极点聚合函数 PolesAggr(mpk，S₊)确定；

当e_i∈S时，令S₊＝S∪{e_i}，则聚合值不能由任何多项式时间算法确定， 所述多项式时间算法包括：PolesAggr(mpk，S₊)。

可选地，所述通过所述聚合函数构造密码学判定算法对元素与集合之间属 于关系进行判定包括：

根据集合S的极点聚合函数PolesAggr(mpk，S)输出的聚合值R_S构造对所述 聚合值R_S的承诺；

对于所述元素e_i，当e_i∈S时，根据确定的所述零点聚合函数 ZerosAggr(mpk，S)输出的聚合值R_S-验证所述承诺；

当则不存在任何多项式时间算法验证所述承诺；

所述通过所述聚合函数构造密码学判定算法对元素与集合之间不属于关 系进行判定包括：

根据集合S的零点聚合函数ZerosAggr(mpk，S)输出的聚合值R_S构造对所述 聚合值R_S的承诺；

对于所述元素e_i，当时，根据确定的极点聚合函数PolesAggr(mpk，S)输 出的聚合值R_S+验证所述承诺；

当e_i∈S时，则不存在任何多项式时间算法验证所述承诺。

另一方面，本发明还提供一种集合成员关系判定的密码学构造系统，包括：

随机化单元：用于获取给定任意集合U{e₁，…，e_n}，将集合U中的每个元素 e_i转化为密码学空间内的随机点v_i；

函数生成单元：用于获取给定集合根据所述随机点v_i确 定集合S中的每个元素e_i'对应的随机点v_i'，并根据所述随机点v_i'构造函数f_S(x)；

秘密点确定单元：用于引入一个随机秘密γ，根据所述函数f_S(x)确定f_S(γ)， 并根据所述随机秘密γ确定公开参数mpk；

密码学处理单元：用于通过密码学方法，以所述公开参数mpk作为输入对 f_S(γ)进行处理生成所述集合S的密码学表示。

可选地，所述密码学处理单元包括：

处理模块：用于通过密码学方法以所述公开参数mpk作为输入对f_S(γ)进行 处理生成所述集合S的聚合函数Aggregate(mpk,S)，当所述函数f_S(x)为零点多项 式时，该聚合函数称为零点聚合函数ZerosAggr(mpk，S)，当所述函数f_S(x)为极点 多项式时，该聚合函数称为极点聚合函数PolesAggr(mpk，S)；

压缩模块：用于通过所述聚合函数将所述集合S压缩成确定长度的随机数 或随机向量R_S，R_S是所述聚合函数Aggregate(mpk,S)的输出聚合值，且R_S的长 度与所述集合S中元素个数无关。

可选地，所述系统还包括：

第一判定单元：用于通过所述聚合函数构造密码学判定算法对元素与元素 之间等于和不等于关系进行判定；和/或

第二判定单元：用于通过所述聚合函数构造密码学判定算法对元素与集合 之间属于和不属于关系进行判定；和/或

第三判断单元：用于通过所述聚合函数构造密码学判定算法对集合与集合 之间包含和不包含关系进行判定。

可选地，所述第二判定单元：还用于获取元素e_i，当e_i∈S时，令S_-＝S\{e_i}， 则聚合值R_S-由零点聚合函数ZerosAggr(mpk，S_-)确定；当时，令S_-＝S\{e_i}， 则聚合值R_S-不能由任何多项式时间算法确定，所述多项式时间算法包括： ZerosAggr(mpk，S_-)；

所述第二判定单元：还用于获取元素e_i，当时，令S₊＝S∪{e_i}，则聚 合值由极点聚合函数PolesAggr(mpk，S₊)确定，当e_i∈S时，令S₊＝S∪{e_i}，则 聚合值不能由任何多项式时间算法确定，所述多项式时间算法包括： PolesAggr(mpk，S₊)

本发明的上述技术方案的有益效果如下：

上述方案中，通过将集合U中的每个元素e_i转化为密码学空间内的随机点 v_i，并根据所述随机点v_i确定子集S中的每个元素e_i'对应的随机点v_i'，且根据 所述随机点v_i'构造函数f_S(x)，再引入一个随机秘密γ，根据所述函数f_S(x)确定 f_S(γ)，并根据所述随机秘密γ确定公开参数mpk，最后将所述公开参数mpk作 为输入，并通过密码学方法对f_S(γ)进行处理，生成所述集合S的密码学表示。 这样，将集合中所有元素以密码学的方式表示成密码学随机空间中的随机数或 随机向量，所述随机数或随机向量能够用于密码学中集合与集合、集合与元素 及元素与元素之间关系的判定。本发明构造的集合聚合算法支持任意元素数目 的集合聚合，即，对要聚合的集合元素的数目没有限制，且本发明提供的构造 方法还为后续的密码学研究奠定了基础，由于现代数学体制就是建立在集合论 基础上，集合基本判定问题的解决必然导致一系列相关密码学问题的解决，特 别是在安全(单方、两方、多方)计算领域，对基于隐私的数据检索、保密数 据库的关键字检索、群组加密、谓词加密、属性基加密、密码学访问控制等。

附图说明

图1为本发明实施例提供的集合成员关系判定的流程示意图；

图2为本发明实施例提供的非集合成员关系判定的流程示意图；

图3为本发明实施例提供的集合成员关系判定的密码学构造系统的结构 示意图。

具体实施方式

为使本发明要解决的技术问题、技术方案和优点更加清楚，下面将结合附 图及具体实施例进行详细描述。

本发明针对现有的无法对集合成员关系进行密码学表示的问题，提供一种 集合成员关系判定的密码学构造方法及系统。

实施例一

本发明实施例中，对于给定的任意大小的集合U＝{e₁，…，e_n}及所述集合U的 子集S，通过本发明提供的构造方法确定集合S的聚合函数，并通过所述聚合 函数将所述集合S的所有元素聚合成为一个或多个密码学随机数或随机向量， 将产生所述聚合函数的集合聚合算法过程定义如下：

在一个密码系统中，PK表示一组公共信息空间，任意集合和一个密码空间C，该集合聚合算法能够在无法获取随机秘密γ(随机秘密γ在 密码学运算过程保密)的情况下，依靠公共参数mpk，输出集合S的聚合值， 集合聚合算法是一个多项式时间(确定或非确定)算法， 满足式(1)：

Aggregate(mpk,S)＝R_S       式(1)

式(1)中，mpk∈PK，公开参数mpk对任何人都可公开，保证产生所述聚 合函数的过程可公开处理。

本发明实施例中，所述聚合函数Aggregate(mpk,S)是一个压缩函数，能将集 合中的所有元素压缩成确定长度的随机数或者随机向量R_S，也就是说聚合函 数输出的聚合值R_S为定长的输出，通常情况下，聚合函数的输出结果仅为代 数群下一个元素，R_S作为密码学中的随机数或随机向量是不可猜测的，且所 述随机点或随机向量可以为d(d≥1)维空间随机点或随机向量。所述集合聚 合算法支持任意元素数目的集合聚合，即，对要聚合的集合元素的数目没有限 制。本发明提供的构造方法还为后续的密码学研究奠定了基础，由于现代数学 体制就是建立在集合论基础上，集合基本判定问题的解决必然导致一系列相关 密码学问题的解决，特别是在安全(单方、两方、多方)计算领域，对基于隐 私的数据检索、保密数据库的关键字检索、群组加密、密码学访问控制等。

本发明实施例中，根据所述随机点v_i'能够选用不同函数(所述函数也可以 称之为曲线)来构造不同的聚合函数从而实现不同的元素与元素、元素与集合、 集合与集合之间的操作，例如，所述函数包括：零点多项式、极点多项式、拉 格朗日插值多项式、牛顿插值多项式、埃尔米特插值多项式、伯恩斯坦多项式、 斐波那契多项式、二项式型多项式或相应代数曲线等。

本发明实施例中，零点多项式函数f_S(x)及极点多项式函数f_S(x)的构造过 程如下：

将集合S中每个元素e_i'对应的随机点v_i'作为H(x)的零点构造零点多项式 函数f_S(x)；或者

将集合S中每个元素e′_i对应的随机点v′_i作为H(x)的极点构造极点多项式 函数f_S(x)；

其中，H(x)＝P(x)/Q(x)是一个有理多项式，表示两个多项式P(x)和Q(x)相 除，对于一个变量z，当P(z)＝0时，P(x)的根z称为H(x)的零点，当Q(z)＝0时， Q(x)的根z被称为H(x)的极点。

本发明实施例中，当所述函数f_S(x)为零点多项式时，该聚合函数称为零 点聚合函数ZerosAggr(mpk，S)，将该零点聚合函数定义如下：

对于给定的一个集合U＝{e₁，…，e_n}、所述集合U的一个子集和一个p阶循环群G以及群的两个生成元g,h，其中，p是一个大素数，如果 存在一个多项式时间算法ZerosAggr，该算法输出满足式(2)：

$G_S=\mathrm{ZerosAggr}(\mathrm{mpk},S)=g^{\gamma ·{\Pi }_{e_i^{\prime }\in S}(\gamma +v_i^{\prime })}$      式(2)

则将该多项式时间算法称为零点聚合函数，所述零点聚合函数的具体构造 过程包括：

1)随机化阶段

可以通过抗碰撞哈希函数将集合U{e₁，…，e_n}中的每个元素e_i转化为一维 平面的随机点v_i，v_i的部分信息被公布在公开参数mpk中，v_i满足 其中，表示模p下的n个整数，每个元素e_i由任意长度二进制串表示。

2)函数生成阶段

根据随机点v_i，确定子集S中的每个元素e_i'对应的随机点v_i'，其中， v_i'＝hash(e_i')，并将所述随机点v_i'作为多项式的(负)根构造零点多项式函数f_S(x)， f_S(x)表示为式(3)：

$f_S\left(x\right)=x(x+{v_1}^{\prime })...(x+{v_m}^{\prime })=x·\underset{{e_i}^{\prime }\in S}{\Pi }(x+{v_i}^{\prime })\mathrm{mod}p$       式(3)

3)秘密点确定阶段

引入一个随机秘密γ，并使用已构造的零点多项式函数f_S(x)确定 $f_S\left(\gamma \right)=\gamma {\Pi }_{{e_i}^{\prime }\in S}(\gamma +{v_i}^{\prime }).$

4)密码学处理阶段

通过密码学方法对f_S(γ)进行处理，具体地，令集合S中元素数目为m，先 确定系数a_k，将f_S(γ)转换为其中，k∈[0,m]，其中，表示模p下的整数；同时，为了保证γ的秘密性，利用离 散对数将曲线f_S(γ)转化为零点聚合函数为式(4)：

$g^{f_S\left(\gamma \right)}=g^{\gamma {\Pi }_{{e_i}^{\prime }\in S}(\gamma +{v_i}^{\prime })}=g^{{\Sigma }_{k=0}^m{a}_k{\gamma }^{k+1}}$       式(4)

式(4)中，g是p阶循环群G的生成元，根据式(4)，输入公开参数mpk， 确定最终的零点聚合函数，如式(5)所示：

$G_s=g^{{\Sigma }_{k=0}^m{a}_k{\gamma }^{(k+1)}}={\Pi }_{k=1}^{m+1}{g_k}^{a_{k-1}}$        式(5)

本发明实施例中，当所述函数f_S(x)为极点多项式时，该聚合函数称为极 点聚合函数PolesAggr(mpk，S)，将所述极点聚合函数定义如下：

对于给定一个集合U＝{e₁,…,e_n}、集合U的一个子集及一个 p阶循环群G，其中，p是一个大素数，如果存在一个多项式时间算法PolesAggr 输出聚合值H_S，则称该算法是极点聚合函数，所述极点聚合函数表示为式(6)：

$H_S=\mathrm{PolesAggr}(\mathrm{mpk},S)=h^{\frac{1}{{\Pi }_{{e_i}^{\prime }\in S}(\gamma +{v_i}^{\prime })}}$        式(6)

该极点聚合函数的具体构造过程包括：

1)随机化阶段

通过抗碰撞哈希函数将集合U＝{e₁,…,e_n}中的每个元素e_i转化为一维平面 的随机点v_i，v_i满足其中，表示模p下的n 个整数，每个元素e_i由任意长度二进制串表示。

2)函数生成阶段

根据随机点v_i，确定子集S中的每个元素e_i'对应的随机点v_i'，v_i'＝hash(e_i')， 并将所述随机点v_i'作为多项式的(负)根构造极点多项式函数g_S(x)，g_S(x)表示为 式(7)：

$g_S\left(x\right)=\frac{1}{(x+{v_1}^{\prime })...(x+{v_m}^{\prime })}=\frac{1}{{\Pi }_{{e_i}^{\prime }\in S}(x+{v_i}^{\prime })}$       式(7)

3)秘密点确定阶段

引入一个随机秘密γ，并使用已构造的曲线或多项式函数g_S(x)确定 $g_S\left(\gamma \right)=\frac{1}{{\Pi }_{{e_i}^{\prime }\in S}(\gamma +{v_i}^{\prime })}\mathrm{mod}p.$

4)密码学处理阶段

通过密码学方法对g_S(γ)进行处理，输入公共参数mpk，h是p阶循环群G的生成元，输出极点聚合函数为

为计算所述极点聚合函数，定义采用递归的方法 确定极点聚合函数的聚合值如式(8)所示：

$\left(\begin{array}{cc}{B}_{i,i}=h_i& \forall i\in [1,m]\\ B_{i,j}={(B_{i,j}/B_{i+1,j+1})}^{\frac{1}{v_{j+1}^{\prime }-{v_i}^{\prime }}}& i\in [1,m-1],j\in [2,m]\end{array}\right)$      式(8)

本发明实施例中，通过所述零点聚合函数或者极点聚合函数能够将集合S 的所有元素以密码学的方式表示成密码学随机空间中的随机数或随机向量，所 述随机数或随机向量能够用于密码学中元素与元素之间“等于”和“不等于” 关系、元素和集合之间“属于”和“不属于”关系，集合与集合之间“包含”和“非 包含”关系的判定。

本发明实施例中，对于元素和集合之间“属于”关系的判定，为了保证聚 合函数算法的安全，以零点聚合函数为例，对零点聚合函数的安全性进行定义， 对于给定元素e_i∈U及子集定义G_S-如式(9)所示

$G_{S-}=G_{S\backslash \left\{e_i\right\}}=g^{\frac{f_S\left(\gamma \right)}{\gamma +v_i}}=g^{\frac{\gamma {\Pi }_{{e_i}^{\prime }\in S}(\gamma +{v_i}^{\prime })}{\gamma +v_i}}$     式(9)

如果同时满足下述两个条件：

1)对任意e_i∈S计算G_S-都是容易的，即G_S-是可由零点聚合函数 $\mathrm{ZerosAggr}(\mathrm{mpk},S_{-})=g^{\gamma {\Pi }_{{e_i}^{\prime }\in S,{e_i}^{\prime }\ne e_i}(\gamma +{v_i}^{\prime })}$计算的；

2)对任意计算G_S-都是困难的，即G_S-是不能由任何多项式时间算法 (包括ZerosAggr(mpk,S_-))计算的。

则称集合S上的零点聚合函数是安全的，能够保证元素与集合之间属于关 系判定的安全性。

本发明实施例中，对于元素和集合之间“不属于”关系的判定，为了保证 聚合函数算法的安全，以极点聚合函数为例，对极点聚合函数的安全性进行定 义，对于给定元素e_i∈U和子集定义如果 同时满足下述两个条件：

1)对任意计算H_S+都是容易的，即H_S+是可由极点聚合函数 $\mathrm{PolseAggr}(\mathrm{mpk},S_{+})=h^{\frac{1}{{\Pi }_{{e_i}^{\prime }\in S}(x+{v_i}^{\prime })}·\frac{1}{(\gamma +v_i)}}$计算的；

2)对任意e_i∈S计算H_S+都是困难的，即H_S+是不能由任何多项式时间算法 (包括PolesAggr(mpk,S₊))计算的。

则称集合S上的极点聚合函数是安全的，能够保证元素与集合之间不属于 关系判定的安全性。

本发明实施例中，为了实现对集合成员关系的判定，首先介绍一下承诺的 概念，承诺是密码学的一个基本概念，包括建立承诺和验证承诺两个过程，在 建立承诺后，任何人不能猜测出承诺中的秘密，但是如果具备特定的秘密值(称 为线索)，可以验证承诺和隐藏在其中的秘密是一致的。

本发明实施例中，判定元素和集合“属于”和“不属于”关系是建立在通 常的双线性系统基础上，令该双线性映射系统表示为S＝{p,G,G_T,e(·,·)}，其中， G和G_T是二个阶为素数p的乘法循环群，元素g和h是G的生成元，那么就有 双线性映射该双线性映射系统具有以下性质：

1)双线性：对任意的a,b属于使得e(g^a,h^b)＝e(g,h)^ab；

2)非退化性：e(g,h)≠1；

3)可计算性：存在多项式时间内算法可快速计算e(g,h)。

元素和集合“属于”关系的密码学判定算法实现方法具体为：

参看图1所示，本发明实施例中，对于给定任意一个集合S,先调用集合S 的极点聚合函数1PolesAggr(mpk,S)计算集合S的聚合值H_S，再引入一个随机秘 密k，构造对所述聚合值H_S的承诺和g^k；对于给定一个 元素e,若满足e∈S，根据零点聚合函数的安全性定义，令S_-＝S\{e}2，此时调 用零点聚合函数3ZerosAggr(mpk,S_-)能够计算出式(10)：

$G_{S-}=\mathrm{ZerosAggr}(\mathrm{mpk},S_{-})=G_{S\backslash \left\{e\right\}}=g^{f_{S-}\left(\gamma \right)}=g^{\frac{f_S\left(\gamma \right)}{\gamma +v}}=g^{\frac{\gamma {\Pi }_{e_i\in S}(\gamma +v_i)}{\gamma +v}}$    式(10)

式(10)中，v＝hash(e)，故能恢复秘密，恢复出的一个特定的秘密值由 式(11)计算：

$e(G_{S-},H_S)=e(g^{f_{S-}\left(\gamma \right)},h^{g_S\left(\gamma \right)k})=e\left(g^{\frac{\gamma {\Pi }_{e_i\in S}(\gamma +v_i)}{\gamma +v},h^{\frac{k}{{\Pi }_{e_i\in S}(\gamma +v_i)}}}\right)=e{(g,h)}^{\frac{\gamma ·k}{\gamma +v}}$    式(11)

并通过等式验证承诺5，其中，直接来源于mpk； 反之，若根据零点聚合函数的安全性定义，恢复出一个特定的秘密值是 计算困难的，从而验证承诺5。本发明提供的元素与集合之间“属于”关系的 判定算法使得判定过程高效而准确，既提高了判定的效率，同时还保证了判定 的安全性和一致性。

本发明实施例中，元素和集合“不属于”关系的密码学判定算法实现方法 具体为：

参看图2所示，对于给定任意一个集合S,先调用集合S的零点聚合函数 3ZerosAggr(mpk,S)计算集合S的聚合值R_S，再引入一个随机秘密k，构造对所 述聚合值R_S的承诺和g^k；给定一个元素e,若满足根据极点聚合函数的安全性定义，令S₊＝S∪{e}6，能够调用极点聚合函数1 PolesAggr(mpk，S+)计算出式(12)：

$H_{S+}=\mathrm{PolseAggr}(\mathrm{mpk},S_{+})=H_{S\cup \left\{e\right\}}=h^{g_{S+}\left(\gamma \right)}=h^{g_S\left(\gamma \right)·\frac{1}{\gamma +v}}=h^{\frac{1}{{\Pi }_{k=s}^r(\gamma +v_k)}·\frac{1}{(\gamma +v)}}$    式(12)

式(12)中，v＝hash(e)，故能恢复秘密4，恢复出的一个特定的秘密值由 式(13)计算：

$e(G_S,H_{S+})=e(g^{f_S\left(\gamma \right)k},h^{g_{S+}\left(\gamma \right)})=e(g^{\mathrm{k\gamma }{\Pi }_{e_i\in S}(\gamma +v_i)},h^{\frac{1}{{\Pi }_{e_i\in S}(\gamma +v_i)}·\frac{1}{(\gamma +v)}})=e{(g,h)}^{\frac{\gamma ·k}{\gamma +v}}$    式(13) 并通过等式验证承诺5，其中，直接来源于mpk；反之， 若e∈S，根据极点聚合函数的安全性定义，恢复出一个特定的秘密值是计算困 难的，从而验证承诺5，通过密码学协议具有可验证的功能，协议结束之后， 协议执行者可以验证关系判定结果的正确性。本发明提供的元素与集合之间 “不属于”关系的判定算法使得判定过程高效而准确，既提高了判定的效率， 同时还保证了判定的安全性和一致性。

本发明实施例中，例如，还可以通过类似的密码学实现方法验证两个集合 是否相等，以及一个集合是否包含于另一个集合中，或一个集合与另一个集合 不相交交(也被称为完全不包含)等关系。

实施例二

本发明还提供一种集合成员关系判定的密码学构造系统的具体实施方式， 由于本发明提供的集合成员关系判定的密码学构造系统与前述集合成员关系 判定的密码学构造方法的具体实施方式相对应，该集合成员关系判定的密码学 构造系统可以通过执行上述方法具体实施方式中的流程步骤来实现本发明的 目的，因此上述集合成员关系判定的密码学构造方法具体实施方式中的解释说 明，也适用于本发明提供的集合成员关系判定的密码学构造系统的具体实施方 式，在本发明以下的具体实施方式中将不再赘述。

参看图3所示，本发明实施例还提供一种集合成员关系判定的密码学构造 系统，包括：

随机化单元101：用于获取给定任意集合U＝{e₁，…，e_n}，将集合U中的每个 元素e_i转化为密码学空间内的随机点v_i；

函数生成单元102：用于获取给定集合根据所述随机点 v_i确定集合S中的每个元素e_i'对应的随机点v_i'，并根据所述随机点v_i'构造函数 f_S(x)；

秘密点确定单元103：用于引入一个随机秘密γ，根据所述函数f_S(x)确定 f_S(γ)，并根据所述随机秘密γ确定公开参数mpk；

密码学处理单元104：用于通过密码学方法，以所述公开参数mpk作为输 入对f_S(γ)进行处理生成所述集合S的密码学表示。

本发明实施例所述的集合成员关系判定的密码学构造系统，通过将集合U 中的每个元素e_i转化为密码学空间内的随机点v_i，并根据所述随机点v_i确定子 集S中的每个元素e_i'对应的随机点v_i'，且根据所述随机点v_i'构造函数f_S(x)，再 引入一个随机秘密γ，根据所述函数f_S(x)确定f_S(γ)，并根据所述随机秘密γ确 定公开参数mpk，最后将所述公开参数mpk作为输入，并通过密码学方法对fS(_γ) 进行处理，生成所述集合S的密码学表示。这样，将集合中所有元素以密码学 的方式表示成密码学随机空间中的随机数或随机向量，所述随机数或随机向量 能够用于密码学中集合与集合、集合与元素及元素与元素之间关系的判定。

在前述集合成员关系判定的密码学构造系统的具体实施方式中，可选地， 可选地，所述密码学处理单元包括：

处理模块：用于通过密码学方法以所述公开参数mpk作为输入对f_S(γ)进行 处理生成所述集合S的聚合函数Aggregate(mpk,S)，当所述函数f_S(x)为零点多项 式时，该聚合函数称为零点聚合函数ZerosAggr(mpk，S)，当所述函数f_S(x)为极点 多项式时，该聚合函数称为极点聚合函数PolesAggr(mpk，S)；

压缩模块：用于通过所述聚合函数将所述集合S压缩成确定长度的随机数 或随机向量R_S，R_S是所述聚合函数Aggregate(mpk,S)的聚合值，且R_S的长度与 所述集合S中元素个数无关。

在前述集合成员关系判定的密码学构造系统的具体实施方式中，可选地， 可选地，所述系统还包括：

第一判定单元：用于通过所述聚合函数构造密码学判定算法对元素与元素 之间等于和不等于关系进行判定；和/或

第二判定单元：用于通过所述聚合函数构造密码学判定算法对元素与集合 之间属于和不属于关系进行判定；和/或

第三判断单元：用于通过所述聚合函数构造密码学判定算法对集合与集合 之间包含和不包含关系进行判定。

在前述集合成员关系判定的密码学构造系统的具体实施方式中，可选地， 可选地，所述第二判定单元：还用于获取元素e_i，当e_i∈S时，令S_-＝S\{e_i}， 则聚合值R_S-由零点聚合函数ZerosAggr(mpk，S_-)确定；当时，令S_-＝S\{e_i}， 则聚合值R_S-不能由任何多项式时间算法确定，所述多项式时间算法包括： ZerosAggr(mpk，S)；

所述第二判定单元：还用于获取元素e_i，当时，令S₊＝S∪{e_i}，则聚 合值R_S+由极点聚合函数PolesAggr(mpk，S₊)确定，当e_i∈S时，令S₊＝S∪{e_i}，则 聚合值R_S+不能由任何多项式时间算法确定，所述多项式时间算法包括： PolesAggr(mpk，S₊)。

以上所述是本发明的优选实施方式，应当指出，对于本技术领域的普通技 术人员来说，在不脱离本发明所述原理的前提下，还可以作出若干改进和润饰， 这些改进和润饰也应视为本发明的保护范围。