Method and System for Cryptographic Decision-making of Set Membership

Abstract

A cryptographic decision-making of set membership is a method or system which make a secure decision-making for positive membership e∈S or negative membership e.Math.S in an unforgeable and non-repudiation way for any element e and a set S. The proposed method of the present invention comprises: acquire a set U={e.sub.1, . . . , e.sub.n} and map each element e.sub.i in U into a random point v.sub.i in a cryptography space; acquire a set S={e′.sub.1, . . . , e′.sub.m}⊂U, determine a random point v′.sub.i corresponding to each element e′.sub.i in the set S, and construct a function ƒ.sub.S(x) according to all random points v′.sub.i; introduce a random secret γ to generate ƒ.sub.S(γ) by using the function ƒ.sub.S(x), and produce a public parameter mpk according to the random secret γ; and generate the cryptographic representation of set S by using the function ƒ.sub.S(γ) and the public parameter mpk. In the embodiments, we provide two kinds of cryptographic representations of set, including Poles-based Aggregation and Zeros-based Aggregation, to make the decision on positive membership e.sub.i∈S and negative membership e.sub.i.Math.S.

Claims

1. A cryptographic construction method for determining a set membership, comprising: acquiring any given set U={e.sub.1, . . . , e.sub.n}, and transforming each element e.sub.i in the set U into a random point v.sub.i in a cryptographic space; acquiring a given set S={e′.sub.1, . . . , e′.sub.m}⊂U, determining a random point v′.sub.i corresponding to each element e′.sub.i in the set S according to the random point v.sub.i, and constructing a function ƒ.sub.S(x) according to the random point v′.sub.i; introducing a random secret γ, determining a function ƒ.sub.S(γ) according to the function ƒ.sub.S(x), and determining a public parameter mpk according to the random secret γ; and processing the function ƒ.sub.S(γ) by using the public parameter mpk as an input to generate a cryptographic representation of the set S via a cryptographic method.

2. The cryptographic construction method according to claim 1, wherein the random point comprises a random number or a random vector; constructing a function ƒ.sub.S(x) according to the random point v′.sub.i comprises: constructing a zeros-based polynomial ƒ.sub.S(x) by setting the random point v′.sub.i corresponding to each element e′.sub.i in the set S as a zero of the polynomial H(x); or constructing a poles-based polynomial ƒ.sub.S(x) by setting the random point v′.sub.i corresponding to each element e′.sub.i in the set S as a pole of the polynomial H(x); wherein H(x) is a rational polynomial with a form H(x)=P(x)/Q(x), which is the quotient of two polynomial P(x) and Q(x); for a variable z, the root z of P(x) is called a zero of H(x) if P(z)=0, and the root z of Q(x) is called a pole of H(x) if Q(z)=0; the constructed function also comprises a Lagrange interpolation polynomial, Newton interpolation polynomials, Hermite interpolation polynomials, Bernstein polynomials and Fibonacci polynomials, Binomial polynomials or corresponding algebraic curves constructed from the random point v′.sub.i.

3. The cryptographic construction method according to claim 1, wherein the processing the function ƒ.sub.S(γ) by using the public parameter mpk as an input to generate a cryptographic representation of the set S via a cryptographic method comprises: processing the function ƒ.sub.S(γ) by using the public parameter mpk as an input to generate an aggregation function Aggregate(mpk,S) of the set S via cryptographic method, wherein the aggregation function is called a zeros-based aggregation function ZerosAggr(mpk,S) if the function ƒ.sub.S(x) is a zeros-based polynomial, or the aggregation function is called a poles-based aggregation function PolesAggr(mpk,S) if the function ƒ.sub.S(x) is a poles-based polynomial; and compressing the set S into a constant-size random number or random vector R.sub.S by means of the aggregation function, wherein R.sub.S is an aggregated value outputted by the aggregation function Aggregate(mpk,S), and the size of R.sub.S is independent of the number of elements in the set S.

4. The cryptographic construction method according to claim 3, after the compressing the set S into a constant-size random number R.sub.S by means of the aggregation function, further comprising: constructing a cryptographic determination algorithm by means of the aggregation function for determining equality and inequality relationships between elements; and/or constructing a cryptographic determination method by means of the aggregation function for determining positive and negative affiliation memberships between elements and the set; and/or constructing a cryptographic determination method by means of the aggregation function for determining positive and negative containment relationships between the sets.

5. The cryptographic construction method according to claim 4, wherein the constructing a cryptographic determination algorithm by means of the aggregation function for determining a positive affiliation membership between elements and the set comprises: acquiring an element e.sub.i, and when e.sub.i∈S, setting S.sub.−=S\{e.sub.i}, then determining the aggregated value R.sub.S.sub.− by the zeros-based aggregation function ZerosAggr(mpk,S.sub.−); and when e.sub.i .Math.S, setting S.sub.−=S\{e.sub.i}, then determining the aggregated value R.sub.S.sub.− by none of polynomial-time algorithms, the polynomial-time algorithms comprise ZerosAggr(mpk,S.sub.−); the constructing a cryptographic determination algorithm by means of the aggregation function for determining a negative affiliation membership between elements and the set comprises: acquiring an element e.sub.i, when e.sub.i .Math.S, setting S.sub.+=S∪{e.sub.i}, then determining the aggregated value R.sub.S.sub.+ by the pole-based aggregation function PoiesAggr(mpk,S.sub.+); and when e.sub.i∈S, setting S.sub.+=S∪{e.sub.i}, then determining the aggregated value R.sub.S.sub.+ by none of polynomial-time algorithms, the polynomial-time algorithms comprise PolesAggr(mpk,S.sub.+).

6. The cryptographic construction method according to claim 5, wherein the constructing a cryptographic determination algorithm by means of the aggregation function for determining a positive affiliation membership between elements and the set comprises: constructing a commitment on the aggregated value R.sub.S according to the outputted aggregated value R.sub.S of the set S from the poles-based aggregation function PolesAggr(mpk,S); for the element e.sub.i, when e.sub.i ∈S, verifying the commitment according to the determined aggregated value R.sub.S.sub.− outputted by the zeros-based aggregation function ZerosAggr(mpk,S.sub.−); and when e.sub.i.Math.S, verifying the commitment by none of polynomial-time algorithms; the constructing a cryptographic determination algorithm by means of the aggregation function for determining a negative affiliation membership between elements and the set comprises: constructing a commitment on the aggregated value R.sub.S according to the outputted aggregated value R.sub.S of the set S from the zeros-based aggregation function ZerosAggr(mpk,S); for the element e.sub.i, when e.sub.i .Math.S, verifying the commitment according to the determined aggregated value R.sub.S.sub.− outputted by the poles-based aggregation function PolesAggr(mpk,S.sub.+); and when e.sub.i.Math.S, verifying the commitment by none of polynomial-time algorithms.

7. A cryptographic construction system for determining a set membership, comprising: a randomizing unit, which is configured to acquire any given set U={e.sub.1, . . . , e.sub.n} and transform each element e.sub.i in the set U into a random point v.sub.i in a cryptographic space; a function generating unit, which is configured to acquire a given set S={e′.sub.1, . . . , e′.sub.m}⊂U, determine a random point v′.sub.i corresponding to each element e′.sub.i in the set S according to the random point v.sub.i, and construct a function ƒ.sub.S(x) according to the random point v′.sub.i; a secret point determining unit, which is configured to introduce a random secret γ, determine a function ƒ.sub.S(γ) according to the function ƒ.sub.S(x), and determine a public parameter mpk according to the random secret γ; and a cryptographic processing unit, which is configured to process the function ƒ.sub.S(γ) by using the public parameter mpk as an input to generate a cryptographic representation of the set S via a cryptographic method.

8. The cryptographic construction system according to claim 7, wherein the cryptographic processing unit comprises: a processing module, which is configured to process the function ƒ.sub.S(γ) by using the public parameter mpk as an input to generate an aggregation function Aggregate(mpk,S) of the set S via cryptographic method, wherein the aggregation function is called a zeros-based aggregation function ZerosAggr(mpk,S) if the function ƒ.sub.S(x) is a zeros-based polynomial, or the aggregation function is called a poles-based aggregation function PolesAggr(mpk,S) if the function ƒ.sub.S(x) is a poles-based polynomial; and a compressing module, which is configured to compress the set S into a constant-size random number or random vector R.sub.S by means of the aggregation function, wherein R.sub.S is an aggregated value outputted by the aggregation function Aggregate(mpk,S), and the size of R.sub.S is independent of the number of elements in the set S.

9. The cryptographic construction system according to claim 8, further comprising: a first determination unit, which is configured to construct a cryptographic determination algorithm by means of the aggregation function for determining equality and inequality relationships between elements; and/or a second determination unit, which is configured to construct a cryptographic determination algorithm by means of the aggregation function for determining positive and negative affiliation memberships between elements and the set; and/or a third determination unit, which is configured to construct a cryptographic determination algorithm by means of the aggregation function for determining positive and negative containment relationships between the sets.

10. The cryptographic construction system according to claim 9, wherein the second determination unit is further configured to acquire an element e.sub.i, and when e.sub.i ∈S, set S.sub.−=S\{e.sub.i}, then determine the aggregated value R.sub.S.sub.− by the zeros-based aggregation function ZerosAggr(mpk,S.sub.−); and when e.sub.i .Math.S, set S.sub.−=S\{e.sub.i}, then determine the aggregated value R.sub.S.sub.− by none of polynomial-time algorithms, the polynomial-time algorithms comprise ZerosAggr(mpk,S.sub.−); and the second determination unit is further configured to acquire an element e.sub.i, when e.sub.i .Math.S, set S.sub.+=S∪{e.sub.i}, then determine the aggregated value R.sub.S.sub.+ by the pole-based aggregation function PoiesAggr(mpk,S.sub.+); and when e.sub.i∈S, set S.sub.+=S∪{e.sub.i}, then determine the aggregated value R.sub.S.sub.+ by none of polynomial-time algorithms, the polynomial-time algorithms comprise PoiesAggr(mpk,S.sub.+).

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0057] FIG. 1 is a system diagram illustrating cryptographic decision-making of positive membership in accordance with the embodiment of the invention;

[0058] FIG. 2 is a system diagram illustrating cryptographic decision-making of negative membership in accordance with the embodiment of the invention;

[0059] FIG. 3 is a structural diagram of cryptosystem illustrating decision-making of membership in accordance with the embodiments of the invention.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

[0060] In order that the invention may be more clearly understood, embodiments thereof will now be described, by way of example only, with reference to the accompanying drawings, in detail.

[0061] The presented invention aims at the issue that the set-membership cannot be expressed and decided in cryptography in the literature at present, and provide the cryptographic methods of secure decision-making of set-memberships.

[0062] An embodiment of the invention is described as follows:

[0063] (1) Aggregation Function

[0064] In this embodiment, the core notion is aggregation function based on cryptographic representation of subsets. Given a set U, an aggregation function is a cryptographic function to compress the information of any subset S⊂U into a constant-size value. The output of aggregation function is called the cryptographic representation of subset. This function is stated as follows:

[0065] Let PK denote the public key space over a group G and U={e.sub.1,L,e.sub.n}, the function Aggregate: PK×2.sup.U.fwdarw.G is a deterministic polynomial-time algorithm satisfying:

Aggregate(mpk,S)=R.sub.S,  (1)

where mpk is the public key in PK, S⊂U, and R.sub.S is an element in G.

[0066] Note that, the aggregation function is an open function because it merely takes as input the public key and does not require any secret information for its operation.

[0067] The aggregation function serves as the foundation for making cryptographic decisions on set memberships, i.e., positive membership e∈S and negative membership e.Math.S. More exactly, we construct two aggregation functions, ZerosAggr and PolesAggr, for decision-making on positive membership (e∈S) and negative membership (e.Math.S), respectively.

[0068] Before we present the two aggregation functions, we first give the definition of zeros and poles in a rational polynomial function as follows:

[0069] H(x) is a rational polynomial with a form H(x)=P(x)/Q(x), which is the quotient of two polynomial P(x) and Q(x); for a variable z, the root z of P(x) is called a zero of H(x) if P(z)=0, and the root z of Q(x) is called a pole of H(x) if Q(z)=0;

[0070] Based on this definition, there is provided a construction method for two aggregation functions, Zeros-based aggregation ZerosAggr and Poles-based aggregation PolesAggr.

[0071] (2) Construction of Zeros-Based Aggregation Function

[0072] Firstly, the function ZerosAggr is constructed according to four following phases:

[0073] 1) Randomizing Phase

[0074] Let G be a multiplicative cyclic group of prime order p and g is a generator of G. Given a set U={e.sub.1,L,e.sub.n}, each element e.sub.i in U is converted into a random point v.sub.i in one dimensional space. The collision-resistant Hash function hash is used to realize this conversation, that is,

(v.sub.1,L,v.sub.n)=(hash(e.sub.1),L,hash(e.sub.n))∈¢.sup.n.sub.p  (2)

Where, ¢.sup.n.sub.p denotes the n integers under module p and each element e.sub.i is represented by the arbitrary length binary string. We do not limit the size of U because the number of elements is usually far less than the size of ¢.sup.n.sub.p (e.g., p>2.sup.256 for a secure elliptic curve).

[0075] 2) Function-Generating Phase

[0076] Given a subset S={e′.sub.1,L,e′.sub.m}⊂U, a zeros-based polynomial ƒ.sub.S(x) could be derived from all random points (v′.sub.1,L,v′.sub.n)=(hash(e′.sup.1),L,hash(e′.sub.n)) which are considered as the (negative) zeros of polynomial. Exactly, the polynomial ƒ.sub.S(x) is defined as:

[00001]$\begin{array}{cc}{f}_S\left(x\right)=x\left(x+v_1^{\prime }\right).Math..Math.\mathrm{.Math.}.Math..Math.\left(x+v_m^{\prime }\right)=x.Math.\underset{e_i^{\prime }\in S}{.Math.}.Math..Math.\left(x+v_i^{\prime }\right).Math.\mathrm{mod}.Math..Math.p.& \left(3\right)\end{array}$

[0077] 3) Secret-Determining Phase

[0078] A random secret γ is introduced to generate ƒ.sub.S(γ) by using the polynomial ƒ.sub.S(x), that is,

ƒ.sub.S(γ)=γΣ.sub.e′.sub.i.sub.∈S(γ+v′.sub.i)mod p.  (4)

And then produces the public parameter mpk=(g.sub.1,g.sub.2,L,g.sub.m)=(g.sup.γ,g.sup.γ2,L,g.sup.γ.sup.m) from γ.

[0079] 4) Cipher-Processing Phase

[0080] In this phase, the zeros-based representation of set S is generated by using the function ƒ.sub.S(γ) and the public parameter mpk. Firstly, the zeros-based representation of set S is defined as

[00002]$\begin{array}{cc}{g}^{f_S\left(\gamma \right)}=g^{\gamma .Math..Math.\underset{e_i^{\prime }\in S}{.Math.}.Math.\left(\gamma +v_i^{\prime }\right)}\in G,& \left(5\right)\end{array}$

where, g is the generator of group G.

[0081] Next ƒ.sub.S(x)=xΠ.sub.e′.sub.i.sub.∈S(x+v′.sub.i)=Σ.sub.k=0.sup.ma.sub.kx.sup.k+1, where the coefficient a.sub.k can be computed only if all elements in S are known. According to Equation (5), the zeros-based aggregation value is also able to computed by using the public parameter mpk={g.sub.i=g.sup.γ.sup.i}.sub.i∈[1,m] as follows:

G.sub.S=gΣ.sub.k=0.sup.ma.sub.kγ.sup.(k+1)=Π.sub.k=1.sup.m+1g.sub.k.sup.a.sup.k−1.  (6)

Note that, when S=Ø, the output of this function is ZerosAggr(mpk,Ø)=g.sub.1=g.sup.γ.

[0082] In this embodiment, a function is called the Zeros-based Aggregation (in short, ZerosAggr) function since the hash values of all elements in S are used for the (negative) zeros in the polynomial ƒ.sub.S(x). The Zeros-based Aggregation is defined as follows:

[0083] Given a subset S={e.sub.1,L,e.sub.n}⊂U and a cyclic group G, an algorithm is called Zeros-based Aggregation function if there exists a polynomial-time algorithm that outputs

[00003]$G_S=\mathrm{ZerosAggr}\left(\mathrm{mpk},S\right)=g^{\gamma .Math.\underset{e_i^{\prime }\in S}{.Math.}.Math.\left(\gamma +v_i\right)},$

where, mpk={g.sub.i=g.sup.γ.sup.i}.sub.i∈[1,|U|] is the public parameter, g is a generator in G, v.sub.i=hash(e.sub.i) and γ is a secret.

[0084] (3) Construction of Poles-Based Aggregation Function

[0085] Secondly, the poses-based aggregation function PolesAggr is constructed according to four following phases:

[0086] 1) Randomizing Phase

[0087] Let G be the same cyclic group of prime order p in ZerosAggr and h is a generator of G. Given a set U={e.sub.1,L,e.sub.n}, the collision-resistant Hash function hash is used to realize the mapping from elements to random points, that is,

(v.sub.1,L,v.sub.n)=(hash(e.sub.1),L,hash(e.sub.n))∈¢.sup.n.sub.p.  (7)

[0088] 2) Function-Generating Phase

[0089] Given a subset S={e′.sub.1,L,e′.sub.m}⊂U, a poles-based polynomial g.sub.S(x) could be derived from all points (v′.sub.1,L,v′.sub.n)=(hash(e′.sub.1),L,hash(e′.sub.n)) which are considered as the (negative) poles of polynomial. Exactly, the polynomial g.sub.S(x) is defined as:

[00004]$\begin{array}{cc}{g}_S\left(x\right)=\frac{1}{\left(x+v_i^{\prime }\right).Math..Math.\mathrm{.Math.}.Math..Math.\left(x+v_m^{\prime }\right)}=\frac{1}{\underset{e_i^{\prime }\in S}{.Math.}.Math.\left(x+v_i^{\prime }\right)}.Math.\mathrm{mod}.Math..Math.p.& \left(8\right)\end{array}$

[0090] 3) Secret-Determining Phase

[0091] A random secret γ is introduced to generate g.sub.S(γ), that is,

g.sub.S(γ)=Π.sub.e′.sub.i.sub.∈S(γ+v′.sub.i).sup.−1 mod p.  (9)

And then produces the public parameter mpk=(h.sub.1,h.sub.2,L,h.sub.m)=(h.sup.1/γ+v′.sup.1,h.sup.1/γ+v′.sup.2,L,h.sup.1/γ+v′.sup.m) from γ.

[0092] 4) Cipher-Processing Phase

[0093] The poles-based representation of set S is defined as

[00005]$\begin{array}{cc}{H}_S=h^{g_S\left(\gamma \right)}=h^{\frac{1}{\underset{e_i^{\prime }\in S}{.Math.}.Math.\left(x+v_i^{\prime }\right)}}\in G,& \left(10\right)\end{array}$

where, h is the generator of cyclic group G.

[0094] We provide a fast recursive method to realize the PolesAggr function from the public parameter

[00006]$\mathrm{mpk}={\left\{h_i=h^{\frac{1}{y+v_i}}\right\}}_{e_i\in U}.$

Firstly, let us see the aggregation between two elements: given h.sub.i and h.sub.j, it is easy to obtain the equation

[00007]$\begin{array}{cc}{\left(h_j/h_i\right)}^{\frac{1}{v_i^{\prime }-v_j^{\prime }}}={\left(h^{\frac{1}{\gamma +v_j^{\prime }}/}.Math.h^{\frac{1}{\gamma +v_i^{\prime }}}\right)}^{\frac{1}{v_i^{\prime }-v_j^{\prime }}}=h^{\frac{1}{\left(\gamma +v_i^{\prime }\right).Math.\left(\gamma +v_j^{\prime }\right)}},& \left(11\right)\end{array}$

where v.sub.i≠v.sub.j is a precondition for this equation for avoiding error with dividing by zero. Next, we expand this equation to multi-value cases. Set

[00008]$B_{i,j}=h^{\frac{1}{\underset{k=i}{\overset{j}{.Math.}}.Math..Math.\left(\gamma +v_k^{\prime }\right)}}=h^{\frac{1}{\gamma +v_i^{\prime }}.Math.L.Math.\frac{1}{\gamma +v_j^{\prime }}},$

The poles-based aggregation value

[00009]$H_S=B_{1,m}=h^{\frac{1}{\underset{e_i^{\prime }\in S}{\overset{}{.Math.}}.Math.\left(x+v_i^{\prime }\right)}}$

can be computed by

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

[0095] In this embodiment, a function is called the Poles-based Aggregation (in short, PolesAggr) function since the hash values of all elements in S are used for the (negative) poles in the polynomial g.sub.S(x). The Poles-based Aggregation is defined as follows:

[0096] Given a subset S={e.sub.1,L,e.sub.m}⊂U and a cyclic group G, an algorithm is called Poles-based Aggregation function if there exists a polynomial-time algorithm that outputs

[00011]$H_S=\mathrm{PolesAggr}\left(\mathrm{mpk},S\right)=h^{\frac{1}{\underset{e_i^{\prime }\in S}{.Math.}.Math.\left(\gamma +v_i\right)}},$

where,

[00012]$\mathrm{mpk}={\left\{h_i=h^{\frac{1}{y+v_i}}\right\}}_{e_i\in U}$

is the public parameter, h is a generator in G, v.sub.i=hash(e.sub.i) and γ is a secret.

[0097] In this embodiment, the information of the set S is compressed and represented as a random number (or vector) in a cryptographic space by zeros-based aggregation function or poles-based aggregation function. Next, the aggregated value can decided the memberships in a cryptographic approach, such as: ‘equal’ and ‘unequal’ between two elements, ‘inclusion’ and ‘exclusion’ between two sets, and ‘positive’ and ‘negative’ membership whether one element is in a set of elements.

[0098] (4) Security of Zeros-Based Aggregation Function

[0099] The accuracy and reliability of decision-making of ‘positive’ membership depends on the security of the zeros-based aggregation function. In this embodiment, the security of zeros-based aggregation function satisfies the following requirements:

[0100] Given an element e.sub.i∈U and a subset S⊂U, let S.sub.−=S\{e.sub.i} and

[00013]$\begin{array}{cc}{G}_{S-}=G_{S.Math.\backslash .Math.\left\{e_i\right\}}=g^{\frac{f_S\left(\gamma \right)}{\gamma +v_i}}=g^{\frac{\gamma .Math.\underset{e_i^{\prime }\in S}{.Math.}.Math.\left(\gamma +v_i^{\prime }\right)}{\gamma +v_i}}.& \left(13\right)\end{array}$

A function on S is called the secure zeros-based aggregation if it has the following two properties: [0101] Easy to compute G.sub.S− for e.sub.i∈S, that is, the value G.sub.S.sub.− can be computed by

[00014]$\mathrm{ZerosAggr}\left(\mathrm{mpk},S_{-}\right)=g^{\gamma .Math.\underset{e_i^{\prime }\in S,e_i^{\prime }\ne e_i}{.Math.}.Math.\left(\gamma +v_i^{\prime }\right)}$

within a polynomial-time; [0102] Hard to compute G.sub.S− for e.sub.i.Math.S, that is, any PPT algorithm (including ZerosAggr(mpk,S.sub.−)) computing G.sub.S.sub.− succeeds with negligible probability.

[0103] These two properties can ensure the security of decision-making of positive membership.

[0104] (5) Security of Poles-Based Aggregation Function

[0105] The accuracy and reliability of decision-making of ‘negative’ membership depends on the security of the poles-based aggregation function. In this embodiment, the security of poles-based aggregation function satisfies the following requirements:

[0106] Given an element e.sub.i∈U and a subset S⊂U, let S.sub.+=S\{e.sub.i} and

[00015]$\begin{array}{cc}{H}_{S+}=H_{S.Math..Math.\left\{e_i\right\}}=h^{g_S\left(\gamma \right).Math.\frac{1}{\gamma +v_i}}=h^{\frac{1}{\underset{e_i^{\prime }\in S}{\overset{}{.Math.}}.Math..Math.\left(x+v_i^{\prime }\right)}.Math.\frac{1}{{}^{\left(\gamma +v_i\right)}}}& \left(14\right)\end{array}$

[0107] A function on S is called the secure poles-based aggregation if it has the following two properties: [0108] Easy to compute H.sub.S+ for e.sub.i.Math.S, that is, the value H.sub.S+ can be computed by

[00016]$\mathrm{PolesAggr}\left(\mathrm{mpk},S_{+}\right)=h^{\frac{1}{\underset{e_i^{\prime }\in S}{\overset{}{.Math.}}.Math..Math.\left(x+v_i^{\prime }\right)}.Math.\frac{1}{{}^{\left(\gamma +v_i\right)}}}$

within a polynomial-time; [0109] Hard to compute H.sub.S+ for e.sub.i∈S, that is, any PPT algorithm (including PolesAggr(mpk,S.sub.+)) computing H.sub.S+ succeeds with negligible probability.

[0110] These two properties can ensure the security of decision-making of negative membership.

[0111] (6) Cryptographic Decision-Making of Positive Membership

[0112] In order to achieve the decision-making of positive membership, this invention introduces the concept of commitment. Commitment, which contains two processes: commitment-generating and commitment-verifying, is a basic concept in cryptography. No one can guess the secret in the commitment after the commitment is built, but we can verify the consistency between the commitment and its hidden secret if we obtain some specific values (called clues).

[0113] In this embodiment, the cryptographic decision-making of positive and negative membership is built on the general bilinear pairing system that can be indicated as S={p,G,G.sub.T,e(•,•)}. In this system, G and G.sub.T are two multiplicative cyclic groups of prime order p, and elements g and h are the generators of G.sub.T and then the bilinear pairing can be indicated as e: G×G a G.sub.T. This system should have the following properties:

[0114] 1) Bilinear: For any a,b belong to ¢*.sub.p, it can get e(g.sup.a,h.sup.b)=e(g,h).sup.ab;

[0115] 2) Non-degenerate: e(g,h)≠1;

[0116] 3) Computable: There is a polynomial-time algorithm to calculate e(g,h).

[0117] FIG. 1 is a flow diagram that implementing cryptographic decision-making of positive membership, described as follows:

[0118] For any given set S, the poles-based aggregate function 1 PolesAggr(mpk,S) is invoked to calculate the aggregation value H.sub.S of set S. And then, a random secret k is introduced to construct the value H.sub.S's commitment

[00017]$H_S=h^{g_s\left(\gamma \right).Math.k}=h^{\frac{k}{{}^{\underset{r_i\in S}{\overset{}{.Math.}}.Math..Math.\left(\gamma +v_i\right)}}}.Math..Math.\mathrm{and}.Math..Math.g^{\gamma .Math..Math.k}.$

[0119] For a given element e satisfying e.Math.S, let S.sub.−=S\{e} 2 according to the security definition of zeros-based aggregation function.

[0120] The zeros-based aggregation function 3 ZerosAggr(mpk,S.sub.−) is invoked to calculate the aggregation value

[00018]$\begin{array}{cc}{G}_{s-}=\mathrm{ZerosAggr}\left(\mathrm{mpk},S_{-}\right)=G_{S.Math.\backslash .Math.\left\{e\right\}}=g^{f_{S-}\left(\gamma \right)}=g^{\frac{f_S\left(\gamma \right)}{\gamma +v}}=g^{\frac{\gamma .Math.\underset{e_i\in S}{.Math.}.Math.\left(\gamma +v_i\right)}{\gamma +v}}.& \left(15\right)\end{array}$

Where, v=hash(e) and v.sub.i=hash(e.sub.i).

[0121] The following secret value is recovered 4 from

[00019]$\begin{array}{cc}e\left(G_{S-},H_S\right)=e\left(g^{{f_S}_{-}\left(\gamma \right)},h^{g_S\left(\gamma \right).Math.k}\right)=e\left(g^{\frac{\gamma .Math.\underset{e_i\in S}{.Math.}.Math.\left(\gamma +v_i\right)}{\gamma +v}},h^{\frac{k}{\underset{e_i\in S}{.Math.}.Math.\left(\gamma +v_i\right).Math.}}\right)={e\left(g,h\right)}^{\frac{\gamma .Math.k}{\gamma +v}}.& \left(16\right)\end{array}$

[0122] The above commitment is verified 5 by using

[00020]${e\left(g,h\right)}^{\frac{\gamma .Math..Math.k}{\gamma +v}}=e\left(g^{\gamma .Math..Math.k},h^{\frac{1}{\gamma +v}}\right),$

where is

[00021]$h^{\frac{1}{\gamma +v}}$

directly derived from mpk.

[0123] Conversely, if e.Math.S, according to the security definition of zeros-based aggregation function, it is computably difficult to recover the particular value

[00022]${e\left(g,h\right)}^{\frac{\gamma .Math.k}{\gamma +v}},$

therefore the commitment verification 5 cannot be passed.

[0124] In summary, the above-mentioned method makes more efficient and precise for decision-making of positive membership. That is, it not only improves the efficiency of decision-making process, but also ensures the security and consistency of decision-making.

[0125] (7) Cryptographic Decision-Making of Negative Membership

[0126] FIG. 2 is a flow diagram that implementing cryptographic decision-making of negative membership, described as follows:

[0127] For any given set S, the zeros-based aggregate function 3 ZerosAggr(mpk,S) is invoked to calculate the aggregation value G.sub.S of set S. And then, a random secret k is introduced to construct the value G.sub.S's commitment

[00023]$G_s=g^{f_s\left(\gamma \right).Math..Math.k}=g^{k.Math..Math.{\mathrm{\gamma \Pi }}_{e_i\in S}\left(\gamma +v_i\right)}$

and g.sup.γk.

[0128] For a given element e satisfying e.Math.S, let S.sub.+=S∪{e} 6 according to the security definition of poles-based aggregation function.

[0129] The poles-based aggregation function 1 PolesAggr(mpk,S+) is invoked to calculate the aggregation value

[00024]$\begin{array}{cc}{H}_{S_{+}}=\mathrm{PolesAggr}\left(\mathrm{mpk},S_{+}\right)=H_{S.Math.\left\{e\right\}}=h^{g_{S_{+}\left(\gamma \right)}}=h^{g_S\left(\gamma \right).Math.\frac{1}{\gamma +v}}=h^{\frac{1}{\underset{k=s}{\overset{r}{.Math.}}.Math..Math.\left(\gamma +v_k\right)}.Math.\frac{1}{{}^{\left(\gamma +v\right)}}}& \left(17\right)\end{array}$

Where, v=hash(e) and v.sub.i=hash(e.sub.i).

[0130] The following secret value is recovered 4 from

[00025]$\begin{array}{cc}e\left(G_s,H_{S+}\right)=e\left(g^{f_S\left(\gamma \right).Math.k},h^{g_{S+}\left(\gamma \right)}\right)=e\left(g^{k.Math..Math.\gamma .Math.\underset{q\in S}{.Math.}.Math..Math.\left(\gamma +v_i\right)},h^{\frac{1}{\underset{e_i\in s}{\overset{}{.Math.}}.Math..Math.\left(\gamma +v_i\right)}.Math.\frac{1}{{}^{\left(\gamma +v\right)}}}\right)={e\left(g,h\right)}^{\frac{\gamma .Math.k}{\gamma +v}}& \left(18\right)\end{array}$

[0131] The above value is verified 5 by using

[00026]${e\left(g,h\right)}^{\frac{\gamma .Math..Math.k}{\gamma +v}}=e\left(g^{\gamma .Math..Math.k},h^{\frac{1}{{}^{\gamma +v}}}\right),$

where

[00027]$h^{\frac{1}{{}^{\gamma +v}}}$

is directly derived from mpk.

[0132] Conversely, if e∈S, according to the security definition of poles-based aggregation function, it is computably difficult to recover the particular value

[00028]${e\left(g,h\right)}^{\frac{\gamma .Math.k}{\gamma +v}},$

therefore the verification 5 cannot be passed.

[0133] In summary, the above-mentioned method makes more efficient and precise for decision-making of negative membership. That is, it not only improves the efficiency of decision-making process, but also ensures the security and consistency of decision-making.

[0134] In this embodiment of the invention, for instance, it can take some similar cryptographic implementation to verify other relationships, such as the equation relationship between two sets, the inclusion relationship between a set and another set, or the disjoint relationship (also known as not totally inclusion) of two sets.

[0135] Another embodiment of the invention is described as follows:

[0136] The invention also provides a specific embodiment of cryptographic system of secure decision-making of membership. Considering that the corresponding relation between the construction of this system and the above-mentioned embodiment of decision-making method of membership, the embodiment of cryptographic system can execute the above-mentioned decision-making method of membership to achieve the purpose of the invention. Therefore, the explanation of implementation of cryptographic method of decision-making of membership also applied to the implementation of cryptographic system of decision-making of membership. We do not repeat to explain in the following specific embodiment of the invention.

[0137] FIG. 3 is a structural diagram of cryptographic system of decision of membership on set, which includes: [0138] Randomizing Unit 101, which is configured to acquire any given set U={e.sub.1, . . . , e.sub.n} and transform each element e.sub.i in the set U into a random point v.sub.i in a cryptographic space; [0139] Function-Generating Unit 102, which is configured to acquire a given set S={e′.sub.1, . . . , e′.sub.m}⊂U, determine a random point v′.sub.i corresponding to each element e′.sub.i in the set S according to the random point v.sub.i, and construct a function ƒ.sub.S(x) according to the random point v′.sub.i; [0140] Secret-determining Unit 103, which is configured to introduce a random secret γ, determine a function ƒ.sub.S(γ) according to the function ƒ.sub.S(x), and determine a public parameter mpk according to the random secret γ; and [0141] Cipher-Processing Unit 104, which is configured to process the function ƒ.sub.S(γ) by using the public parameter mpk as an input to generate a cryptographic representation of the set S via a cryptographic method.

[0142] During the procedure described above, all elements in a given set might be represented as a random number or a random vector in the cryptographic space, which can be used in cryptographic decision-making of membership between the set and the set, the set and the element, or the element and the element.

[0143] In this embodiment, optionally, the cipher-processing unit comprising:

[0144] Processing module, which is configured to process the function ƒ.sub.S(γ) by using the public parameter mpk as an input to generate an aggregation function Aggregate(mpk,S) of the set S via cryptographic method, wherein the aggregation function is called a zeros-based aggregation function ZerosAggr(mpk,S) if the function ƒ.sub.S(x) is a zeros-based polynomial, or the aggregation function is called a poles-based aggregation function PolesAggr(mpk,S) if the function ƒ.sub.S(x) is a poles-based polynomial; and

[0145] Compressing module, which is configured to compress the set S into a constant-size random number or random vector R.sub.S by means of the aggregation function, wherein R.sub.S is an aggregated value outputted by the aggregation function Aggregate(mpk,S), and the size of R.sub.S is independent of the number of elements in the set S.

[0146] According to one or more embodiments of the present invention, the constant-size random number or random vector R.sub.S is used to generate the cryptographic decision-making device, includes:

[0147] The First Decision-Making Unit, which is configured to construct a cryptographic determination algorithm by means of the aggregation function for determining equality and inequality relationships between elements; and/or

[0148] The Second Decision-Making Unit, which is configured to construct a cryptographic determination algorithm by means of the aggregation function for determining positive and negative affiliation memberships between elements and the set; and/or

[0149] The Third Decision-Making Unit, which is configured to construct a cryptographic determination algorithm by means of the aggregation function for determining positive and negative containment relationships between the sets.

[0150] In the foregoing specification, optionally, the embodiments of the invention can construct the second decision device that realizes the cryptographic system of decision-making of membership. The following processes may perform the decision-making of membership:

[0151] the second determination unit is further configured to acquire an element e.sub.i, and when e.sub.i∈S, set S=S\{e.sub.i}, then determine the aggregated value R.sub.S.sub.− by the zeros-based aggregation function ZerosAggr(mpk,S.sub.−); and when e.sub.i.Math.S, set S.sub.−=S\{e.sub.i}, then determine the aggregated value R.sub.S.sub.− by none of polynomial-time algorithms, the polynomial-time algorithms comprise ZerosAggr(mpk,S.sub.−); and

[0152] the second determination unit is further configured to acquire an element e.sub.i, when e.sub.i.Math.S, set S.sub.+=S∪{e.sub.i}, then determine the aggregated value R.sub.S.sub.+ by the pole-based aggregation function PolesAggr(mpk,S.sub.+); and when e.sub.i∈S, set S.sub.+=S∪{e.sub.i}, then determine the aggregated value R.sub.S.sub.+ by none of polynomial-time algorithms, the polynomial-time algorithms comprise PolesAggr(mpk,S.sub.+).

[0153] The preferred embodiment of the present invention is described above. It should be pointed out that the general technical individual of technical field can also make some improvement and polishing, without departing from the principles of the present invention, which should be regarded as the scope of protection.