Network system, server and information terminal for list matching

RELATED APPLICATIONS

p-0002The present patent application claims a right of priority under 35 U.S.C. §119 from Japanese Patent Application No. 2001-307976 filed Oct. 3, 2001 and Japanese Patent Application No. 2002-191591 filed Jul. 1, 2002.

FIELD OF THE INVENTION

p-0003The present invention relates to a method for list matching on a network, in which a common part among lists held by two or more participants is extracted.

BACKGROUND

p-0004Information exchanges via a network include list matching, in which only a common part among lists held by two or more participants is computed and extracted. A specific application of the list matching is a match making service, in which the list matching is performed on a database (list) describing a profile of a member including an interest, and members having common interests are introduced to each other. Besides, the list matching may be utilized by a plurality of financial institutes to query a list of specific users (black list, for example) to find users listed by the plurality of financial institutes.

p-0005Recently, as the network environment, such as Internet, has become widespread, privacy protection on the network has become more important, and thus, the list matching has become required to extract the common part without disclosing the contents of the list held by each participant.

p-0006In the past, to implement the list matching on the network, there has been a method of providing a TTP (Trusted Third Party) server to manage the lists to be subject to the list matching and compute the common part on the TTP server. In this case, the list information confidentiality depends on the security of the TTP server.

p-0007In addition, a peer-to-peer service not requiring a specific server has become widespread recently, and thus, the list matching may be performed without the TTP server. In order to ensure the security in such a case, there is disclosed a protocol involving a cryptography referred to as an oblivious polynomial evaluation (OPE) in the following Literature 1. <ul><li id="ul0001-0001" num="0007">Literature 1: Naor, M. and Pinkas, B, “Oblivious Transfer and Polynomial Evaluation,” in proc. of STOC, 1999.</li></ul>

p-0008In Literature 1, there is described the following protocol:

p-0009It is assumed that Alice and Bob, the list holders, have list AL={a₁, . . . , a_n} and BL={b₁, . . . , b_n}, respectively;

p-00101. Alice and Bob prepare nth order polynomials P_A(x) and P_B(x), respectively, in secret;

p-00112. Alice uses the OPE to compute [P_B(a₁)]_i=1ⁿ, and Bob also uses the OPE to compute [P_A(b₁)]_i=1ⁿ; and

p-00123. Alice opens [P_A(a₁)+P_B(a_i)]_i=1ⁿ, and Bob opens [P_A(b₁)+P_B(b₁)]_i=1ⁿ.

p-0013According to this method, with respect to a known item in a list, a third party cannot estimate the presence or absence of the common item in another list.

p-0014As described above, in the case of the information exchange through the list matching, if the system includes the TTP server to manage the list to be subject to the list matching, the list information confidentiality depends on the security of the TTP server. Therefore, if the security of the TTP server is broken, confidential information in the list will be leaked.

p-0015Besides, according to the protocol involving the OPE used for the peer-to-peer list matching disclosed in Literature 1, it is possible to prevent a third party from, with respect to a known item in a list, estimating the presence or absence of the common item in another list. However, one list holder can falsify an open value to make the other list holder believe in a mismatch, while he/she exclusively knowing the common part with the other.

p-0016Besides, methods for performing computation with an argument kept in secret among a plurality of parties and extracting the computation result for the argument include a method referred to as a distributed secret computation (multiparty protocol). The protocol involving the OPE is also included in the distributed secret computation. The distributed secret computation is described in, for example, the following Literature 2. <ul><li id="ul0002-0001" num="0017">Literature 2: Ben-Or, Goldwasser, and Wigderson, “Completeness theorems for non-cryptographic fault-tolerant distributed computation,” STOC, ACM, 1988.</li></ul>

p-0017To extract a common part from a plurality of lists by means of list matching, a comparison computation for each item is essential. Thus, for two lists each containing n items, n²comparison computations are needed. Such a comparison computation can be easily programmed.

p-0018However, the distributed secret computation essentially involves addition and multiplication of two values, and therefore, it is difficult to include therein a branch instruction or the like required for the comparison computation. Thus, the peer-to-peer list matching using the distributed secret computation has been difficult in terms of efficiency in processing.

SUMMARY OF THE INVENTION

p-0019Thus, the present invention provides methods, apparatus and systems to ensure the security in information exchange and to provide list matching with higher efficiency and practicality.

p-0020In addition, this invention aims to provide a secure method for peer-to-peer list matching using the distributed secret computation.

p-0021This invention, which attains the objects, provides a list matching method of extracting a common item among a plurality of lists by using a computer, characterized in that lists to be processed are read out from a memory, a polynomial having roots equivalent to the items of the list is generated for each of the read-out lists, the generated polynomials are added, and a list containing an item constituted by a root of a polynomial resulting from the addition is generated and output.

p-0022More specifically, first, for each list, a polynomial having the roots whose value is obtained by adding the value of item in the list to the value of the one-way hash function applied to the value of item, is generated. Then, the result list is generated by adding the said polynomials. Among the roots of the results polynomial, only the roots that consist of the value and its hash function are extracted as the common items of the given lists.

p-0023In addition, this invention provides a list matching method of extracting a common item among a plurality of lists held by a plurality of information terminals constituting a network, which satisfies the following requirements. That is, each of the information terminals holding a list generates a polynomial having the roots equivalent to the items of the list. Then, the information terminals adds the respective polynomials to the polynomial received from a preceding information terminal and passes a polynomial resulting from the addition to a subsequent information terminal in a predefined order. In addition, a last information terminal in this order generates a list containing an item equivalent to the roots of the received polynomial.

p-0024Here, the last information terminal can inform the other information terminals of the generated list or information on the items of the list.

p-0025In addition, this invention provides a list matching method of extracting the common items among a plurality of lists held by a plurality of information terminals constituting a network, which satisfies the following requirements. That is, each of the information terminals holding a list generates a polynomial having roots equivalent to the items of the list. Then, the polynomials generated by the information terminals are added through a distributed secret computation involving a plurality of servers on the network arranged to be commonly used by the information terminals. In addition, the information terminal restores a polynomial resulting from the addition of the polynomials generated by the information terminals based on the result of the addition by the servers, and generates a list containing an item equivalent to a root of the reproduced polynomial.

p-0026In addition, this invention provides a list matching method of extracting common items among a plurality of lists held by a plurality of information terminals interconnected via a network, which satisfies the following requirements. That is, each of the information terminals holding a list generates a bivariate polynomial based on a first polynomial having roots equivalent to the items of the list and a second polynomial whose order corresponds to the predetermined number of servers on the network and distributes the bivariate polynomial to the servers according to the second polynomial. Then, the servers add the polynomials transmitted from the information terminals, the polynomials being the bivariate polynomial distributed to the information terminals, and send back the addition result to the information terminals. Then, the information terminal restores a polynomial resulting from the addition of the polynomials describing the lists held by the information terminals based on the result of the addition by the servers, and generates a list containing items equivalent to the roots of the restored polynomial.

p-0027Furthermore, another list matching method according to this invention is characterized in that a predetermined information terminal obtains open information generated based on a polynomial having the roots equivalent to the items of the list held by another terminal apparatus, verifies the open information obtained from the another information terminal, and, based on the open information of the another information terminal having passed the verification and the polynomial having the roots equivalent to the items of the list held by the terminal itself, determines a common item among the list used to generate the open information and the list held by the terminal itself.

p-0028Advantageously, only when the open information obtained from the another information terminal passes the verification, the predetermined information terminal generates predetermined information based on the polynomial generated from the list held by the terminal itself and the open information and exchanges the information with the another information terminal. Then, based on the predetermined information exchanged, the predetermined information terminal determines the common item among the list used to generate the open information and the list held by the terminal itself.

p-0029Furthermore, this invention is implemented as a network system configured as follows. That is, the network system comprises a server and a plurality of client terminals interconnected via a network. The client terminal adds a polynomial describing a list to be subject to list matching to a polynomial received from another client terminal via the network and transmits a polynomial resulting from the addition to another client terminal or the server. The server receives a polynomial resulting from the addition of all the polynomials generated by the plurality of client terminals and generates a list containing an item equivalent to a root of the polynomial.

BRIEF DESCRIPTION OF THE DRAWINGS

p-0030<figref idrefs="DRAWINGS">FIG. 1</figref> shows an example of a polynomial having roots equivalent to items in a list, which is a characteristic function used in an embodiment;

p-0031<figref idrefs="DRAWINGS">FIG. 2</figref> is a flow chart for illustrating a procedure of configuring the characteristic function polynomial from the list;

p-0032<figref idrefs="DRAWINGS">FIG. 3</figref> is a flow chart for illustrating a procedure of reproducing the polynomial to obtain a common item to lists;

p-0033<figref idrefs="DRAWINGS">FIG. 4</figref> shows a whole configuration of a system according to a first embodiment, in which list matching is performed at a TTP server on a network;

p-0034<figref idrefs="DRAWINGS">FIG. 5</figref> shows a advantageous system configuration of a match making server and client terminal shown in <figref idrefs="DRAWINGS">FIG. 4</figref>;

p-0035<figref idrefs="DRAWINGS">FIG. 6</figref> shows a whole configuration of a system according to a second embodiment, in which list matching is performed based on a peer-to-peer method, illustrating requests for secret distributed computation to servers;

p-0036<figref idrefs="DRAWINGS">FIG. 7</figref> shows the whole configuration of the system according to the second embodiment, in which list matching is performed based on the peer-to-peer method, illustrating the list matching based on results of the computation by the servers;

p-0037<figref idrefs="DRAWINGS">FIG. 8</figref> shows a advantageous system configuration of a network terminal and server shown in <figref idrefs="DRAWINGS">FIG. 6</figref>;

p-0038<figref idrefs="DRAWINGS">FIG. 9</figref> is a diagram illustrating a polynomial Q_i(x, y)=F_Xi(x)+F_Yi(y);

p-0039<figref idrefs="DRAWINGS">FIG. 10</figref> is a flow chart for illustrating a method for forming a bivariate polynomial Q_i(x, y);

p-0040<figref idrefs="DRAWINGS">FIG. 11</figref> is a flow chart for illustrating a method for forming a (k−1)th order polynomial F_Xi(x);

p-0041<figref idrefs="DRAWINGS">FIG. 12</figref> shows a whole configuration of a system that performs the list matching according to a third embodiment;

p-0042<figref idrefs="DRAWINGS">FIG. 13</figref> shows a functional configuration of the network terminal and the TTP server according to the third embodiment;

p-0043<figref idrefs="DRAWINGS">FIG. 14</figref> illustrates an algorithm executed in the network terminal and the TTP server and a flow of information;

p-0044<figref idrefs="DRAWINGS">FIG. 15</figref> illustrates a protocol of the list matching according to this embodiment;

p-0045<figref idrefs="DRAWINGS">FIG. 16</figref> is a diagram for illustrating a method for verifying an occurrence of an exception using a transaction certificate with a time limit;

p-0046<figref idrefs="DRAWINGS">FIG. 17</figref> schematically shows the match making service according to this invention; and

p-0047<figref idrefs="DRAWINGS">FIG. 18</figref> is a schematic diagram showing an example of a hardware configuration of a computer suitable for implementing the server and the information terminal of the system according to this invention.

DESCRIPTION OF REFERENCE NUMBERS

p-0048<ul><li id="ul0003-0001" num="0000"><ul><li id="ul0004-0001" num="0049"><b>101</b> . . . CPU (Central Processing Unit)</li><li id="ul0004-0002" num="0050"><b>103</b> . . . Main Memory</li><li id="ul0004-0003" num="0051"><b>105</b> . . . Hard Disk</li><li id="ul0004-0004" num="0052"><b>106</b> . . . Network Interface</li><li id="ul0004-0005" num="0053"><b>400</b> . . . Match Making Server</li><li id="ul0004-0006" num="0054"><b>411</b>, <b>412</b>-<b>41</b><i>m </i>. . . Client Terminal</li><li id="ul0004-0007" num="0055"><b>501</b>, <b>511</b> . . . Application Software</li><li id="ul0004-0008" num="0056"><b>502</b>, <b>512</b> . . . Network Protocol</li><li id="ul0004-0009" num="0057"><b>503</b>, <b>513</b> . . . Network Interface</li><li id="ul0004-0010" num="0058"><b>611</b>-<b>61</b><i>m </i>. . . Network Terminal</li><li id="ul0004-0011" num="0059"><b>621</b>-<b>62</b><i>k </i>. . . Server</li><li id="ul0004-0012" num="0060"><b>801</b>, <b>811</b> . . . Application Software</li><li id="ul0004-0013" num="0061"><b>802</b>, <b>812</b> . . . Network Protocol</li><li id="ul0004-0014" num="0062"><b>803</b>, <b>813</b> . . . Network Interface</li><li id="ul0004-0015" num="0063"><b>1200</b> . . . Network Terminal</li><li id="ul0004-0016" num="0064"><b>1201</b> . . . Commitment Generation Unit</li><li id="ul0004-0017" num="0065"><b>1202</b> . . . Commitment Verifying Unit</li><li id="ul0004-0018" num="0066"><b>1203</b> . . . Matching Unit</li><li id="ul0004-0019" num="0067"><b>1204</b> . . . Matching Result Output Unit</li><li id="ul0004-0020" num="0068"><b>1205</b> . . . Exception Processing Request Unit</li><li id="ul0004-0021" num="0069"><b>1206</b> . . . Exception Processing Result Output Unit</li><li id="ul0004-0022" num="0070"><b>1210</b> . . . TTP Server</li><li id="ul0004-0023" num="0071"><b>1211</b> . . . Exception Processing Execution Unit</li></ul></li></ul>

DETAILED DESCRIPTION OF THE INVENTION

p-0049Now, the present invention will be described in detail with reference to embodiments shown in the accompanying drawings.

p-0050This invention proposes that, for information exchange based on list matching, a list to be subject to the list matching is represented by a multi-dimensional function (referred to as a characteristic function, hereinafter).

p-0051A list containing a predetermined item can be represented by a characteristic function by substituting a numerical value for the item and forming the polynomial having the numerical value as a root (hereinafter, “polynomial having a root equivalent to an item” means that the polynomial has, as the root thereof, the numerical value substituting for the item in the list). Thus, to describe n items in a list, it is required to define an nth order polynomial.

p-0052<figref idrefs="DRAWINGS">FIG. 1</figref> shows an example of a polynomial having roots equivalent to items in a list, which is a characteristic function.

p-0053As shown in <figref idrefs="DRAWINGS">FIG. 1</figref>, representing polynomials describing lists L₁and L₂by F_Y1(y) (indicated by a solid line in the drawing) and F_Y2(y) (indicated by a broken line in the drawing), respectively, a polynomial F_Y(y)=F_Y1(y)+F_Y2(y) (indicated by a thick solid line in the drawing), which is the sum of the two polynomials, also has a root which is a common item to the polynomials, as shown at a coordinate point A. This means that the addition of the polynomials describing the lists L₁and L₂provides the polynomial having the common item as the root. Considering the polynomial in a prime number finite field Z/Zp, the Barlekamp algorithm can be used to factorize a univariate multi-dimensional polynomial to determine the root thereof. Thus, a one-to-one relation can be established in forming the polynomial from the list and in restoring the list from the polynomial. Here, the Barlekamp algorithm is described, for example, in Literature 3. <ul><li id="ul0005-0001" num="0077">Literature 3: Donald E. Knuth, Seminumerical Algorithms, the art of computer programming, Addison-Wesley, 1998.</li></ul>

p-0054There is a problem in that the sum polynomial may have a root other than the common root as shown at a coordinate point B in <figref idrefs="DRAWINGS">FIG. 1</figref>. To distinguish the root from the common root, a one-way hash function MD5 is used. That is, a list item <b>1</b> is not directly used for the root of the polynomial, but a list item <b>1</b>∥MD5 (1), which additionally includes an operation result of the hash function MD5, is used for the root (the symbol ∥ means a coupling of character strings). Thus, after the addition of the polynomials, the operation result of the hash function MD5 will be held by the root of the sum polynomial. Therefore, when restoring the list, by verifying whether the operation result of the hash function is held by a root or not, it can be distinguished whether the root is produced from a list item or accidentally produced in the course of the addition of the polynomials.

p-0055<figref idrefs="DRAWINGS">FIG. 2</figref> is a flow chart for illustrating a procedure of configuring the characteristic function polynomial from the list, and <figref idrefs="DRAWINGS">FIG. 3</figref> is a flow chart for illustrating a procedure of restoring the polynomial to obtain a common item to lists. In this case, for example, processings are performed by a program-controlled CPU in a typical computer apparatus, and the list L and the function F(x), which are to be processed, are stored in a cache memory or main memory in the CPU. <figref idrefs="DRAWINGS">FIG. 18</figref> is a schematic diagram showing an example of a hardware configuration of such a computer apparatus.

p-0056The computer apparatus shown in <figref idrefs="DRAWINGS">FIG. 18</figref> comprises a CPU (Central Processing Unit) <b>101</b>, which is operation means, a main memory <b>103</b> connected to the CPU <b>101</b> via an M/B (motherboard) chip set <b>102</b> and a CPU bus, a video card <b>104</b> connected to the CPU <b>101</b> via the M/B chip set <b>102</b> and an AGP (Accelerated Graphics Port), a hard disk <b>105</b>, a network interface <b>106</b> and an USB port <b>107</b> which are connected to the M/B chip set <b>102</b> via a PCI (Peripheral Component Interconnect) bus, and a Floppy® disk drive <b>109</b> and a keyboard/mouse <b>110</b> which are connected to the M/B chip set <b>102</b> via the PCI bus, a bridge circuit <b>108</b> and a low-speed bus such as an ISA (Industry Standard Architecture) bus.

p-0057Here, <figref idrefs="DRAWINGS">FIG. 18</figref> only shows the hardware configuration of the computer apparatus implementing this embodiment as an example, and other various configurations are possible as far as this embodiment can be implemented. For example, instead of providing the video card <b>104</b>, only a video memory may be provided and image data may be processed in the CPU <b>101</b>. Alternatively, a drive for a CD-ROM (Compact Disc Read Only Memory) or DVD-ROM (Digital Versatile Disc Read Only Memory) may be connected to the apparatus via an interface such as an ATA (AT Attachment).

p-0058Referring to <figref idrefs="DRAWINGS">FIG. 2</figref>, the CPU <b>101</b> first defines a function F(x)=1 and a variable q=1 (step <b>201</b>), and loads an item l_iin the list L to be processed from the main memory <b>103</b>. Here, a relation of l_i′=l_i∥MD(l_i) is defined (step <b>202</b>). Then, the CPU <b>101</b> redefines a function F(x)=F(x)*(x−l_i′) (mod p) and increments the variable q by 1 (step <b>203</b>). The steps <b>202</b> and <b>203</b> are repeated until the value q reaches the number n of the items in the list L, and then, the obtained function F(x) is output (steps <b>204</b>, <b>205</b>).

p-0059In this way, the characteristic function F(x) is formed from the list L.

p-0060Referring to <figref idrefs="DRAWINGS">FIG. 3</figref>, the CPU <b>101</b> first loads the nth order function F(x) to be processed from the main memory <b>103</b> (step <b>301</b>), and factorizes the function F(x) using the Barlekamp algorithm (step <b>302</b>). Then, based on the result of the factorization, the CPU <b>101</b> obtains relations of g_i=(x−l_i′) and l_i′=l∥MD (step <b>303</b>). For all the factors (x−l_i′), an item l_i′ which satisfies a relation of MD=MD5(l_i) (that is, an item l_i′ which satisfies a relation of l_i′=l_i∥MD5(l_i)) is extracted (step <b>304</b>, <b>305</b>). Then, a list L is generated from the obtained item l_i′ (step <b>306</b>), and the obtained list L is output (step <b>307</b>).

p-0061In this way, the list L is reproduced from the characteristic function F(x).

p-0062In terms of security, such a list matching is required to meet the following requirements:

p-0063(1) an item commonly appearing in the lists of all the list holders is defined as a common part; and

p-0064(2) a list holder can only know the common part in contents of a list of another list holder.

p-0065According to this definition, the list holders can know whether, only for the items included in their respective lists, each item is common to the other participants or not.

p-0066As described above, if a list is represented as a polynomial (characteristic function) having a root equivalent to each item in the list, such polynomials can be summed to provide a polynomial having a root equivalent to a common item to the lists, and thus, the common item to the lists can be obtained from the polynomial resulting from the calculation. That is, the common item to the list can be extracted only through addition without the need for a comparison computation including a branch instruction. Thus, as described later, it is possible to configure a system which computes a common item by the participants sequentially adding polynomials equivalent to their respective lists or a system which computes a common item using the distributed secret computation, and the list matching can be implemented on the network with high security.

p-0067Now, an embodiment of the network system that performs the list matching using as the protocol the above-described method of computing the common item by representing the list by the characteristic function will be described.

p-0068A system that performs a list matching computation at a TTP server provided on a network and a system that performs the peer-to-peer list matching will be described herein.

p-0069<figref idrefs="DRAWINGS">FIG. 4</figref> shows a whole configuration of the system that performs the list matching at the TTP server on the network.

p-0070Referring to <figref idrefs="DRAWINGS">FIG. 4</figref>, a network system according to this embodiment comprises client terminals of list holders (participants) and a match making server (TTP server) that performs the list matching computation. In the example in <figref idrefs="DRAWINGS">FIG. 4</figref>, client terminals <b>411</b>, <b>412</b>-<b>41</b><i>m </i>of m participants and one match making server <b>400</b> are interconnected via the network.

p-0071The match making server <b>400</b> according to this embodiment may be a work station, personal computer or other computer apparatus, for example. The client terminals <b>411</b>, <b>412</b>-<b>41</b><i>m </i>may be a computer apparatus, such as a personal computer, or an information communication terminal, such as a PDA (Personal Digital Assistant) and a cellular phone, for example. The lists to be subject to the list matching are stored in storage means, such as a magnetic disk and semiconductor memory. Typically, the match making server <b>400</b> and the client terminals <b>411</b>, <b>412</b>-<b>41</b><i>m </i>may be the computer apparatus shown in <figref idrefs="DRAWINGS">FIG. 18</figref>.

p-0072<figref idrefs="DRAWINGS">FIG. 5</figref> shows a advantageous system configuration of the match making server <b>400</b> and the client terminal <b>411</b>, <b>412</b>-<b>41</b><i>m </i>shown in <figref idrefs="DRAWINGS">FIG. 4</figref>.

p-0073As shown in <figref idrefs="DRAWINGS">FIG. 5</figref>, the match making server <b>400</b> comprises application software <b>501</b>, a network protocol <b>502</b> and a network interface <b>503</b>, and each of the client terminals <b>411</b>, <b>412</b>-<b>41</b><i>m </i>comprises application software <b>511</b>, a network protocol <b>512</b> and a network interface <b>513</b>.

p-0074The CPU <b>101</b> controlled by the application software <b>501</b>, <b>511</b> performs processings including generation of a list to be processed, formation of a characteristic function polynomial from the list, addition of polynomials and decryption of the list from the polynomial. And, the CPU <b>101</b> controls the network interface <b>503</b>, <b>513</b> via the network protocol <b>502</b>, <b>512</b>. The match making server <b>400</b> and the client terminal <b>411</b>, <b>412</b>-<b>41</b><i>m </i>communicate with each other by means of the network interface <b>503</b>, <b>513</b> through a network line <b>520</b>.

p-0075The CPU <b>101</b> controlled by the application software <b>511</b> of the client terminal <b>411</b>, <b>412</b>-<b>41</b><i>m </i>implements a function of outputting a list of common items received from the match making server <b>400</b> according to the protocol described later or information on the list through display means (liquid crystal display, for example) or audio output means provided in the client terminal <b>411</b>, <b>412</b>-<b>41</b><i>m. </i>

p-0076The system configuration of the match making server <b>400</b> and the client terminals <b>411</b>, <b>412</b>-<b>41</b><i>m </i>according to this embodiment is not limited to that shown in <figref idrefs="DRAWINGS">FIG. 5</figref>. For example, a network OS (operating system) may be provided between the application software <b>501</b>, <b>511</b> and the network protocol <b>502</b>, <b>512</b>.

p-0077In the network system configured as described above, the list matching is performed according to the following protocol.

p-00781. The client terminal <b>411</b> composes a polynomial F₁(x) from its list L₁. It also generates a list R₁containing random items and composes a polynomial F_R1(X) therefrom. Then, it transmits in secret the polynomial F_R1(x) to the match making server <b>400</b> and transmits in secret a polynomial F_1,2(x)=F₁(x)+F_R1(x) to the client terminal <b>412</b>.

p-00792. The client terminal <b>41</b><i>i </i>(i=2, . . . , m−1) transmits in secret to the client terminal <b>41</b><i>i+</i>1 a polynomial F_i,i+1(x)=F_i−1,i(x)+F_i(x), which is the sum of a polynomial F_i−1,i(x) transmitted from the client terminal <b>41</b><i>i−</i>1 and a polynomial F_i(x) describing the list Li of its own.

p-00803. The client terminal <b>41</b><i>m </i>transmits in secret to the match making server <b>400</b> a polynomial F_m,M(x)−F_m−1,m(x)+F_m(x), which is the sum of a polynomial F_m−1,m(x) transmitted from the client terminal <b>41</b><i>m−</i>1 and a polynomial F_m(x) describing the list L_mof its own.

p-00814. The match making server <b>400</b> decrypts the list of the common items to the clients from a polynomial F_M(x)=F_m,M(x)−F_R1(x), which is obtained by subtracting the polynomial F_R1(X) from the polynomial F_m,M(x) transmitted from the client terminal <b>41</b><i>m</i>, and notifies the client terminals <b>411</b>, <b>412</b>-<b>41</b><i>m </i>of the list.

p-0082In this way, the polynomials describing the lists of the participants are added through the client terminals <b>411</b>, <b>412</b>-<b>41</b><i>m </i>and then, the list of the common parts can be obtained at the match making server <b>400</b>. Alternatively, the match making server <b>400</b> may transmit the polynomial F_M(x) equivalent to the list of the common parts to the client terminals <b>411</b>, <b>412</b>-<b>41</b><i>m </i>as it is, and the list of the common parts may be decrypted at each of the client terminals <b>411</b>, <b>412</b>-<b>41</b><i>m</i>. Besides, such a service may be contemplated that only the number of the common items among the lists is transmitted to the client terminals <b>411</b>, <b>412</b>-<b>41</b><i>m. </i>

p-0083The order of the client terminals <b>411</b>, <b>412</b>-<b>41</b><i>m </i>can be arbitrarily set, and may be changed each time the list matching is performed. However, it is essential that all the client terminals <b>411</b>, <b>412</b>-<b>41</b><i>m </i>having the list to be processed are involved. Further, the number of the lists to be processed may change each time the list matching is performed. For example, in the case where four client terminals <b>411</b>, <b>412</b>-<b>41</b><i>m </i>are connected to the match making server <b>400</b>, all the four client terminals <b>411</b>, <b>412</b>-<b>41</b><i>m </i>may be involved in the list matching, or two of the client terminals <b>411</b>, <b>412</b>-<b>41</b><i>m </i>may be involved in the list matching.

p-0084With the network system described above, security is ensured in the following two respects.

p-0085First, the match making server <b>400</b> can know only the polynomial resulting from the addition.

p-0086Second, the client terminals <b>411</b>, <b>412</b>-<b>41</b><i>m </i>cannot know the polynomials of the other participants.

p-0087The participants will know whether, only for the items included in their respective lists, each item is common to the other participants or not. Therefore, it is possible to prevent a specific list holder from knowing the common part with another list holder without disclosing the items of his/her own.

p-0088Now, the system that performs the peer-to-peer list matching without the use of the TTP server will be described.

p-0089<figref idrefs="DRAWINGS">FIGS. 6 and 7</figref> show a whole configuration of such a system. In the drawings, operations in the protocol described later are described.

p-0090The network system according to this embodiment requires a plurality of servers to be involved in secret distribution. Unlike the match making server <b>400</b> described above, the servers are only involved in the computations of the polynomials, and cannot acquire any information about the lists. Referring to <figref idrefs="DRAWINGS">FIGS. 6 and 7</figref>, in the network system according to this embodiment, network terminals <b>611</b>-<b>61</b><i>m </i>of m list holders (participants) and k servers <b>621</b>-<b>62</b><i>k </i>involved in the secret distribution are interconnected via the network.

p-0091The network terminals <b>611</b>-<b>61</b><i>m </i>according to this embodiment may be a computer apparatus, such as a personal computer, or an information communication terminal, such as a PDA (Personal Digital Assistant) and a cellular phone, for example. The lists to be subject to the list matching are stored in storage means, such as a magnetic disk and semiconductor memory. The servers <b>621</b>-<b>62</b><i>k </i>may be a work station, personal computer or other computer apparatus, for example. Typically, the network terminals <b>611</b>-<b>61</b><i>m </i>and the servers <b>621</b>-<b>62</b><i>k </i>may be the computer apparatus shown in <figref idrefs="DRAWINGS">FIG. 18</figref>.

p-0092<figref idrefs="DRAWINGS">FIG. 8</figref> shows a advantageous system configuration of the network terminals <b>611</b>-<b>61</b><i>m </i>and the servers <b>621</b>-<b>62</b><i>k </i>shown in <figref idrefs="DRAWINGS">FIG. 6</figref>.

p-0093As shown in <figref idrefs="DRAWINGS">FIG. 8</figref>, each of the network terminals <b>611</b>-<b>61</b><i>m </i>comprises application software <b>801</b>, a network protocol <b>802</b> and a network interface <b>803</b>, and each of the servers <b>621</b>-<b>62</b><i>k </i>comprises application software <b>811</b>, a network protocol <b>812</b> and a network interface <b>813</b>.

p-0094The CPU <b>101</b> controlled by the application software <b>801</b>, <b>811</b> performs processings including generation of a list to be processed, formation of a characteristic function polynomial from the list, addition of polynomials and reproduction of the list from the polynomial. And, the CPU <b>101</b> controls the network interface <b>803</b>, <b>813</b> via the network protocol <b>802</b>, <b>812</b>. The network terminals <b>611</b>-<b>61</b><i>m </i>and the servers <b>621</b>-<b>62</b><i>k </i>communicate with each other by means of the network interface <b>803</b>, <b>813</b> through a network line <b>820</b>.

p-0095The CPU <b>101</b> controlled by the application software <b>801</b> of the network terminal <b>611</b>-<b>61</b><i>m </i>implements a function of outputting a list of common items based on the polynomial reproduced according to the protocol described later through display means (liquid crystal display, for example) or audio output means provided in the network terminal <b>611</b>-<b>61</b><i>m. </i>

p-0096The system configuration of the network terminals <b>611</b>-<b>61</b><i>m </i>and the servers <b>621</b>-<b>62</b><i>k </i>according to this embodiment is not limited to that shown in <figref idrefs="DRAWINGS">FIG. 7</figref>. For example, a network OS (operating system) may be provided between the application software <b>801</b>, <b>811</b> and the network protocol <b>802</b>, <b>812</b>.

p-0097Now, background arts for implementing the list matching according to the secret distribution in the system according to this embodiment will be described.

p-0098According to the common key cryptography system, one secret key is split into shares to be held by several servers. One famous common key cryptography system is the Shamir's (t, k) threshold cryptography scheme, in which one piece of secret information is split into shares to be held by k servers, and the original key can be restored by t of the k servers cooperating with each other. In this scheme, a (t−1)th polynomial on a field F is first defined as follows: <br /><i>f</i>(<i>x</i>)=<i>f</i>₀<i>+f</i>₁<i>*x+f</i>₂*^x2<i>+ . . . +f</i>_t−1<i>*x</i>^t−1  (equation 1).

p-0099A secret information holder substitutes the secret information for f₀in the equation 1, and determines randomly the remaining f_k. Then, the holder sends (k, f(k)) to the servers k as split information. Only after k pieces of split information is collected, coefficients of the polynomial (equation 1) can be uniquely determined, and thus, f₀can be determined.

p-0100The Shamir's (t, k) threshold cryptography scheme is described in the following Literature 4. <ul><li id="ul0006-0001" num="0125">Literature 4: Shamir, A., “How to Share a Secret”, CACM 22, 1979.</li></ul>

p-0101The Oblivious Transfer (OT, hereinafter) is a protocol between two persons, an information sender S (sender) and a chooser C, in which the chooser selectively obtains predetermined several pieces of information among from a plurality of pieces of information held by the sender. Here, the following two requirements have to be satisfied.

p-0102(1) Privacy of the chooser: the sender cannot know which are chosen by the chooser.

p-0103(2) Privacy of the sender: the chooser cannot get information other than that he/she has chosen.

p-0104One basic OT is the 1-out-of-2-OT, in which the sender has two pieces of information, and the chooser chooses any one thereof. As a typical protocol for implementing the same, there is a protocol using the ElGamal encryption as described below. In the protocol described below, the information pieces held by the sender are denoted by I₀, I₁, and it is assumed that a chooser's selected value b∈{0, 1}, and [b]=NOT b.

p-01051. S→C: Random number r.

p-01062. C→S: K_b=gx, K_[b]=r/Ab.

p-01073. S: Check that K₀*K₁=r.

p-01084. S→C: {EI1, IE2}, where EI1=(g^h, I₀*K₀^h), EI2=(g^h, I₁*K₁^h).

p-01095. C: Decrypt I_b.

p-0110This protocol is described in the following Literature 5, for example. <ul><li id="ul0007-0001" num="0136">Literature 5: Bellare, M. and Micali, S., “Non-interactive oblivious transfer and applications,” in proc. CRYPTO'89, 1990.</li></ul>

p-0111The above-described basic OT requires encryption and decryption between the sender and the chooser. In particular, the sender has to encrypt all the information, and this is a heavy burden. Thus, it can be contemplated that a plurality of servers is provided between the sender and the chooser, and the secret information is distributed among the servers, thereby reducing the burden to the sender. The distributed OT is the one that implements the contemplation. A protocol of the distributed OT is as follows. Here, in the protocol described below, the k servers are denoted by P₁, . . . , P_k.

p-01121. S: Create a first order formula F_Y(y)=(I₁−I₀)y+I₀and a (k−1)th order formula F_X(x) with a constant term being 0, and define a bivariate polynomial Q(x, y)=F_X(x)+F_Y(y).

p-01132. S→P_i: Send Q(i, y) (Q denotes an univariate polynomial).

p-01143. C: Create a (k−1)th order formula S(x) with a constant term being b.

p-01154. C→P_i: Send a coordinate (i, S(i)).

p-01165. P_i→C: Return Q(i, S(i)).

p-01176. C: Receive Q(i, S(i)) from k servers to restore a (k−1)th order formula G(x)=Q(x, S(x)), thereby determining a value of G(0)=Q(0, S(0))=Q(0, b)=F_Y(b).

p-0118This protocol is described in the following Literature 6, for example. <ul><li id="ul0008-0001" num="0145">Literature 6: Naor, M. and Pinkas, B., “Distributed Oblivious,” in proc. of Asiacrypt, 2000.</li></ul>

p-0119Based on the technical background described above, in the network system configured as shown in <figref idrefs="DRAWINGS">FIGS. 6 to 8</figref>, the list matching is performed according to the protocol described below.

p-01201. Formation of characteristic function and transformation of the same into bivariate function:

p-0121The network terminal <b>61</b><i>i </i>(i=1, . . . , m) composes an (n+1)th order polynomial F_Yi(y) so that F_Yi(l_i,h)=0 where h=1, . . . , n. (Since the polynomial is of the (n+1)th order, it can has (n+1) roots. The last one root is “id_i”, which is a character string of the ID of S_i, and if the number of items in the list of the network terminal <b>61</b><i>i </i>is less than n, all of the remaining roots are assumed to be “id_i”.) Then, a (k−1)th order polynomial F_Xi(x) with a constant term being 0 is created, and a bivariate polynomial Q_i(x, y)=F_Xi(x)+F_Yi(y) is defined (see <figref idrefs="DRAWINGS">FIG. 6</figref>). <figref idrefs="DRAWINGS">FIG. 9</figref> is a diagram illustrating the polynomial Q_i(x, y)=F_Xi(x)+F_Yi(y).

p-0122<figref idrefs="DRAWINGS">FIG. 10</figref> is a flow chart for illustrating a method for generating the bivariate polynomial Q_i(x, y), and <figref idrefs="DRAWINGS">FIG. 11</figref> is a flow chart for illustrating a method for generating the (k−1)th order polynomial F_Xi(x).

p-0123Referring to <figref idrefs="DRAWINGS">FIG. 10</figref>, the (n+1) the order polynomial F_Y(y), which is previously stored in the main memory or the like, is read out (step <b>1001</b>), and the (k−1)th order polynomial F_X(x) is read out (step <b>1002</b>). Then, the read-out polynomials F_Y(y) and F_X(x) are added to generate the bivariate polynomial Q_i(x, y) (step <b>1003</b>).

p-0124Referring to <figref idrefs="DRAWINGS">FIG. 11</figref>, (k−1) random numbers are first generated (step <b>1101</b>), and the random numbers are used to generate the (k−1)th order polynomial F_X(x)=r₁*x+r₂*x²+ . . . +r_k−1*x^k−1(step <b>1102</b>).

p-01252. Distribution of characteristic function among servers:

p-0126The network terminal <b>61</b><i>i </i>(i=1, . . . , m) sends Q_i(j, y) to the server <b>62</b><i>j </i>(j=1, . . . , k) (Q_idenotes a univariate polynomial) (see <figref idrefs="DRAWINGS">FIG. 6</figref>).

p-01273. Addition of distributed values at servers:

p-0128The server <b>62</b><i>j </i>(j−1, . . . , k) adds all the Q_i(j, y) sent from the network terminals <b>61</b><i>i </i>(i=1, . . . , m) (see <figref idrefs="DRAWINGS">FIG. 6</figref>). That is,

p-0129<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mrow><mrow><msup><mi>Q</mi><mrow><mo>(</mo><mi>j</mi><mo>)</mo></mrow></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>j</mi><mo>,</mo><mi>y</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><msub><mi>Σ</mi><mi>i</mi></msub><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mrow><msub><mi>Q</mi><mi>i</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>j</mi><mo>,</mo><mi>y</mi></mrow><mo>)</mo></mrow></mrow><mo>.</mo></mrow></mrow></mrow></math></maths>

p-01304. Creation of restoration functions:

p-0131Each network terminal <b>61</b><i>i </i>(i=1, . . . , m) creates n (k−n−2)th order polynomials S_i,t(x) with a constant term being l_i,t, where t=1, . . . , n (see <figref idrefs="DRAWINGS">FIG. 7</figref>).

p-01325. Inquiry about distributed values on restoration functions to servers:

p-0133The network terminal <b>61</b><i>i </i>(i=1, . . . , m) sends n coordinates (j, S_i,t(j)), where t=1, . . . , n, to the server <b>62</b><i>j </i>(j=1, . . . , k) (see <figref idrefs="DRAWINGS">FIG. 7</figref>).

p-01346. Return of distributed values on restoration functions from servers:

p-0135The server <b>62</b><i>j </i>(j=1, . . . , k) returns values of Q^(j)(j, S_i,t(j)), where t=1, . . . , n, to the network terminal <b>61</b><i>i </i>(i=1, . . . , m) (see <figref idrefs="DRAWINGS">FIG. 7</figref>).

p-01367. Determination of correspondence of items:

p-0137The network terminal <b>61</b><i>i </i>(i=1, . . . , m) restores the polynomial Q^(j)(x, S_i,t(x)) from the k polynomials Q^(j)(j, S_i,t(j))<img id="CUSTOM-CHARACTER-00001" he="0.68mm" wi="0.68mm" file="US07979712-20110712-P00001.TIF" alt="custom character" img-content="character" img-format="tif" />@(j=1, . . . , k). Then, substituting x=0 for the polynomial,

p-0138<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mrow><mrow><mrow><msup><mi>Q</mi><mrow><mo>(</mo><mi>j</mi><mo>)</mo></mrow></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mn>0</mn><mo>,</mo><mrow><msub><mi>S</mi><mrow><mi>i</mi><mo>,</mo><mi>t</mi></mrow></msub><mo>⁡</mo><mrow><mo>(</mo><mn>0</mn><mo>)</mo></mrow></mrow></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><msup><mi>Q</mi><mrow><mo>(</mo><mi>j</mi><mo>)</mo></mrow></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><mn>0</mn><mo>,</mo><msub><mi>l</mi><mrow><mi>i</mi><mo>,</mo><mi>t</mi></mrow></msub></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><msub><mi>Σ</mi><mi>i</mi></msub><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><msub><mi>F</mi><mi>Yi</mi></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>l</mi><mrow><mi>i</mi><mo>,</mo><mi>t</mi></mrow></msub><mo>)</mo></mrow></mrow></mrow></mrow></mrow><mo>,</mo></mrow></math></maths><br /> where t=1, . . . , n is calculated (see <figref idrefs="DRAWINGS">FIG. 7</figref>). With respect to a certain t, if Σ_iF_Yi(l_i,t) is 0, all the list holders commonly have the item l_i,t, or if

p-0139<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mrow><msub><mi>Σ</mi><mi>i</mi></msub><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><msub><mi>F</mi><mi>Yi</mi></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>l</mi><mrow><mi>i</mi><mo>,</mo><mi>t</mi></mrow></msub><mo>)</mo></mrow></mrow></mrow></math></maths><br /> is not 0, the item l_i,tis not common.

p-0140In this way, the polynomials describing the lists of the participants are distributed among the plurality of servers <b>621</b>-<b>62</b><i>k </i>and added to each other, and based on the result of the addition, the list of common parts can be obtained at the network terminals <b>611</b>-<b>61</b><i>m </i>of the respective participants. In the case of the list matching using the secret distribution according to the above-described protocol, initially, communications are established among the network terminals <b>611</b>-<b>61</b><i>m </i>holding the list to be subject to the list matching, and servers <b>621</b>-<b>62</b><i>k </i>to be used are determined.

p-0141With the network system described above, security is ensured in the following two respects.

p-0142First, the servers <b>621</b>-<b>62</b><i>k </i>for secret distribution cannot get information on the polynomials of the list holders and the resulting polynomial unless all of the k servers are in collusion with each other.

p-0143Second, the network terminals <b>611</b>-<b>61</b><i>m </i>cannot know the polynomials of the other participants.

p-0144Here, an illegal act using the network terminal <b>611</b>-<b>61</b><i>m </i>can be contemplated in which one registers a constant of 0 as the list-describing function of his/her own to try to know the common parts to the other participants without disclosing the actual list. However, such an illegal act can be detected by checking the order of the distributed polynomials at the servers <b>621</b>-<b>62</b><i>k </i>for secret distribution when the network terminals <b>611</b>-<b>61</b><i>m </i>register the polynomials with the servers <b>621</b>-<b>62</b><i>k </i>for secret distribution in a distribution manner.

p-0145According to the above-described protocol, each list holder i knows his/her own characteristic function F_Yi(y). Therefore the list holder can retrieve the value of the sum function Σ_iF_Yi(y) for a point y0 other than roots of his/her characteristic function (that is, a certain list item) and subtract the value of his/her characteristic function therefrom, thereby knowing whether the item is common to another list holder or not if a relation of

p-0146<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mrow><mrow><mrow><msub><mi>Σ</mi><mi>i</mi></msub><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><msub><mi>F</mi><mi>Yi</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>y0</mi><mo>)</mo></mrow></mrow></mrow><mo>-</mo><mrow><msub><mi>F</mi><mi>Yi</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>y0</mi><mo>)</mo></mrow></mrow></mrow><mo>=</mo><mn>0</mn></mrow></math></maths><br /> is satisfied. To prevent this, information other than the roots can be made to be invalid by multiplying the sum function by a factor of a random number as described below.

p-0147First, in the step 2 in the protocol described above, a random number R_i(the same value for all the servers) is sent besides Q_i(j, y)

p-0148In the step 3, besides adding the polynomials Q_i(j, y), the random numbers R_isent from the network terminals <b>61</b><i>i </i>(i=1, . . . , m) are added. That is,

p-0149<maths id="MATH-US-00005" num="00005"><math overflow="scroll"><mrow><msup><mi>R</mi><mrow><mo>(</mo><mi>j</mi><mo>)</mo></mrow></msup><mo>=</mo><mrow><msub><mi>Σ</mi><mi>i</mi></msub><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><msub><mi>R</mi><mi>i</mi></msub><mo>.</mo></mrow></mrow></mrow></math></maths>

p-0150And, the former sum function is multiplied by a factor of the latter sum random number.

p-0151Involving such operations can prevent a list holder from retrieving any point other than the roots of his/her function.

p-0152According to this embodiment, each element in the list to be subject to the matching is a root of the characteristic function. Therefore, as a result of the addition of a plurality of characteristic functions, the sum characteristic function may have a root at a point where any of the characteristic functions has no root, as described above. Also as described above, in such a case, a one-way hash function can be used to distinguish, when reproducing the list, whether the root is produced from a list item or accidentally produced in the course of the addition of the polynomials.

p-0153However, according to this embodiment in which the peer-to-peer list matching is performed using secret distribution, the accidentally produced root is not a significant problem, and there is no need for the scheme using the hash function. This is because the list holders (participants), in principal, have to check whether the resulting function has a root at a point where their respective characteristic functions have a root. Thus, there is no problem at least in the case where two participants are involved.

p-0154In the case where three or more participants are involved, for example, in the case where a participant A has a list {A1, A2}, a participant B has a list {B1, B2} and a participant C has a list {C1, C2}, addition of the characteristic functions of A and B may, with a quite low probability, result in a sum function having a root C1. In this case, the C will erroneously determines that A and B also have the same element C1. The probability of occurrence of such an event can be determined as follows.

p-0155While the functions can be defined in any finite field, they are defined in the prime number field Z_pherein for simplicity. Assuming that p is a prime number of the order of 512 bit, a character string of 64 length can be represented as a root. Here, if the number n of elements in the list is on the order of 15, the characteristic function is of 16th order. Each of the characteristic functions has the ID of the holder of the its corresponding list as a root, and therefore, is unique without overlapping with the others. Therefore, the probability that the sum function of the functions of A and B has a root at a certain value y0 other than the roots of the functions of A and B is on the order of 16/(2⁵¹²), which can be substantially neglected.

p-0156Now, a system that usually performs the peer-to-peer list matching using the characteristic functions and, if a fault occurs, completes the list matching with the assistance of the TTP server will be described.

p-0157<figref idrefs="DRAWINGS">FIG. 12</figref> shows a whole configuration of such a system.

p-0158Referring to <figref idrefs="DRAWINGS">FIG. 12</figref>, with the network system according to this embodiment, the list matching can be implemented only through information exchange among network terminals <b>1200</b> each constituting a peer in the system. In addition, if a fault occurs in the information exchange among the network terminals <b>1200</b> (if a required information exchange is not accomplished or if erroneous information is exchanged), the problem can be solved by sending a request for an exception processing to a TTP server <b>1210</b>.

p-0159<figref idrefs="DRAWINGS">FIG. 13</figref> shows a functional configuration of the network terminal <b>1200</b> and the TTP server <b>1210</b> according to this embodiment.

p-0160The network terminal <b>1200</b> may be a computer apparatus, such as a personal computer, or an information communication terminal, such as a PDA (Personal Digital Assistant) and a cellular phone, for example (see <figref idrefs="DRAWINGS">FIG. 18</figref>). The lists to be subject to the list matching are stored in storage means, such as the hard disk <b>105</b> and main memory <b>103</b>. Referring to <figref idrefs="DRAWINGS">FIG. 13</figref>, the network terminal <b>1200</b> comprises a commitment generation unit <b>1201</b> that generates a commitment and a commitment open value, which are public information, a commitment verifying unit <b>1202</b> that obtains and verifies the public information of another network terminal <b>1200</b>, which is the partner in the list matching, a matching unit <b>1203</b> that performs the matching process on the commitment open value generated by the commitment generation unit <b>1201</b> and the commitment of the other network terminal <b>1200</b> verified in the commitment verifying unit <b>1202</b>, a matching result output unit <b>1204</b> that outputs the result of the list matching, an exception processing request unit <b>1205</b> that requests the TTP server <b>1210</b> for a processing, and an exception processing result output unit <b>1206</b> that outputs the processing result obtained from the TTP server <b>1210</b>.

p-0161The commitment generation unit <b>1201</b>, the commitment verifying unit <b>1202</b>, the matching unit <b>1203</b>, the matching result output unit <b>1204</b>, the exception processing request unit <b>1205</b> and the exception processing result output unit <b>1206</b> are virtual software blocks that are implemented by the program-controlled CPU <b>101</b> in the computer apparatus constituting the network terminal <b>1200</b>. While not shown in particular, the network terminal <b>1200</b> further comprises a transmitter/receiver unit implemented by the program-controlled CPU <b>101</b> and the network interface <b>106</b>.

p-0162The TTP server <b>1210</b> may be a work station, personal computer or other computer apparatus, for example (see <figref idrefs="DRAWINGS">FIG. 18</figref>), and comprises an exception processing execution unit <b>1211</b> that performs the list matching in response to the request from the exception processing request unit <b>1205</b> in the network terminal <b>1200</b>.

p-0163The exception processing execution unit <b>1211</b> is a virtual software block that is implemented by the program-controlled CPU <b>101</b> in the computer apparatus constituting the TTP server <b>1210</b>. Further, while not shown in particular, the TTP server <b>1210</b> further comprises a transmitter/receiver unit implemented by the program-controlled CPU <b>101</b> and the network interface <b>106</b>.

p-0164Now, with respect to the case where the list matching is performed between predetermined two network terminals <b>1200</b> each constituting a peer in the network system shown in <figref idrefs="DRAWINGS">FIG. 12</figref>, for example, the processing and a flow of information will be described.

p-0165In the following description, when individual network terminals <b>1200</b> need to be identified, indices u, v will be assigned to the reference numeral. The same applies to components of the network terminals <b>1200</b>. For example, they will be denoted as the network terminal <b>1200</b><i>v</i>, commitment generation unit <b>1201</b><i>u</i>, and the like.

p-0166Each network terminal <b>1200</b> has n pieces of data held in the database thereof. All pieces of data are assigned data numbers to be uniquely distinguished, and a set of the whole data numbers is denoted by L. A list of the data numbers of the n pieces of data held by a network terminal <b>1200</b><i>u </i>is represented, using an index u, as L_u={α_u,1, . . . , α_u,n}.The network terminal <b>1200</b><i>u </i>has a secret key K_ufor the public key cryptosystem. The TTP server <b>1210</b> has a secret key K_Tfor the public key cryptosystem algorithm E_T( ). The TTP server <b>1210</b> has a function (exception processing execution unit <b>1211</b>) of normally completing the protocol when a fault (exception) occurs as described above, which does not work in the normal process.

p-0167In this embodiment, the list matching (extraction of a common part among two lists) is defined as described below. That is, between arbitrary two network terminals <b>1200</b><i>u </i>and <b>1200</b><i>v </i>(u≠v), a common part L_u∩L_vto the secret lists thereof is shared. At this time, the followings are required:

p-0168(1) one of the network terminals does not reveal information except for the common part to the other; and

p-0169(2) an illegal act that only one of the network terminals tries to know the common part is prevented.

p-0170Now, an algorithm executed in the network terminal <b>1200</b> and the TTP server <b>1210</b> will be described.

p-0171<figref idrefs="DRAWINGS">FIG. 14</figref> illustrates the algorithm executed in the network terminal <b>1200</b> and the TTP server <b>1210</b> and a flow of information.

p-0172In this embodiment, to implement the list matching, the following six algorithm descriptions are used in the network terminal <b>1200</b>. <ul><li id="ul0009-0001" num="0000"><ul><li id="ul0010-0001" num="0200">C(L_u): This is a commitment generation algorithm executed in the commitment generation unit <b>1201</b><i>u</i>. When the list L_uheld by the network terminal <b>1200</b><i>u </i>is input, a commitment come and a commitment open value open_uare output.</li><li id="ul0010-0002" num="0201">V(com_v): This is a commitment verifying algorithm executed in the commitment verifying unit <b>1202</b><i>u</i>. When a commitment com_vfrom the network terminal <b>1200</b><i>v </i>is input, a verification result {0, 1} is output (an input resulting in the output of “1” will be referred to as a “legal commitment”, hereinafter).</li><li id="ul0010-0003" num="0202">M(open_u, com_v): This is a matching algorithm executed in the matching unit <b>1203</b><i>u</i>. When the commitment open value open, of the network terminal <b>1200</b><i>u </i>and a legal commitment com, of the network terminal <b>1200</b><i>v </i>are input, an answering message ans_u,vis output.</li><li id="ul0010-0004" num="0203">D(ans_v,u, com_v, L_u, K_u, open_u): This is a result output algorithm executed in the matching result output unit <b>1204</b><i>u </i>When the answering message ans_v,ufrom the network terminal <b>1200</b><i>v </i>to the network terminal <b>1200</b><i>u</i>, the legal commitment com_v, and the list L_u, the secret key K_uand the commitment open value open_uof the network terminal <b>1200</b><i>u </i>are input, a common part to the lists L_uand L_vexpressed by the following formula 1 (or also denoted as {tilde over ( )}L_u,v) or an error message is output (an input ans_v,uresulting in the output of the common part will be referred to as a “legal answering message”, hereinafter). <br /><i>{tilde over (L)}</i>_u,v(=<i>L</i>_u<i>∩L</i>_v)  (Formula 1)</li><li id="ul0010-0005" num="0204">P(com_v, L_u): This is an exception processing request generation algorithm executed in the exception processing request unit <b>1205</b><i>u</i>. When the legal commitment com, of the network terminal <b>1200</b><i>v </i>and the list L_uof the network terminal <b>1200</b><i>u </i>are input, an exception processing request message ereq_v,uis output.</li><li id="ul0010-0006" num="0205">W(eans_v,u, K_u): This is an exception processing result generation algorithm executed in the exception processing result output unit <b>1206</b><i>u</i>. When an exception request answering message eans_v,uis input, the common part {tilde over ( )}L_u,v(=L_u∩L_v) to the lists L_uand Lv is output.</li></ul></li></ul>

p-0173In addition, in this embodiment, the following algorithm executed in the exception processing execution unit <b>1211</b> in the TTP server <b>1210</b> is used. <ul><li id="ul0011-0001" num="0000"><ul><li id="ul0012-0001" num="0207">T(ereq_v,u, K_T): This is an exception processing algorithm. When the exception processing request message ereq_v,uand the secret key K_Tof the TTP server <b>1210</b> are input, the exception processing answering message eans_v,uor error is output (the exception processing request message ereq_v,uresulting in the output of the exception processing answering message eans_v,uwill be referred to as a “legal exception processing request message”, hereinafter).</li></ul></li></ul>

p-0174Details of these algorithms will be described later.

p-0175According to the definitions of the list matching and algorithms described above, the list matching according to this embodiment can be formulated as follows.

p-01761. Servers Open Commitments

p-0177Initially, the commitment generation unit <b>1201</b> of the network terminal <b>1200</b> uses the commitment generation algorithm C to generate the commitment and commitment open value ({com_u, open_u}=C(L_u), in the case of the network terminal <b>1200</b><i>u</i>) of the list thereof (L_u, in the case of the network terminal <b>1200</b><i>u</i>), and broadcasts the generates commitment (com) to the other network terminals <b>1200</b>, that is, whole of the network system. The commitment open value (open) is kept secret.

p-0178The commitment is opened to all the network terminals <b>1200</b>. The size of the commitment is independent of the number of the network terminals <b>1200</b> involved in the system, and therefore, the commitment needs not be changed when another network system <b>1200</b> is added to the system. Thus, the commitment may be provided to the network terminals <b>1200</b> in any manner so far as the network terminals can arbitrarily obtain the commitment, rather than by the network terminals <b>1200</b> exchanging the commitments with each other by broadcasting. For example, the commitment may be registered with a database provided in the network and opened to the public, or such a database may be stored in a mass recording medium, such as CD-ROM (Compact Disc Read Only Memory) and DVD-ROM (Digital Versatile Disc Read Only Memory), and distributed.

p-01792. The following processes are performed between arbitrary network terminals <b>1200</b>. For simplicity, a process flow for the network terminals <b>1200</b><i>u </i>and <b>1200</b><i>v </i>will be described. (b) is a procedure needed only when exception occurs. As described below, since both of the network terminals <b>1200</b><i>u </i>and <b>1200</b><i>v </i>perform the similar processes, the network terminals <b>1200</b><i>u </i>and <b>1200</b><i>v </i>initially communicate with each other, and then, the processes are started after the two ascertain that the list matching is to be performed between them.

p-0180(a) Normal Process

p-0181i. Verification of Commitment

p-0182The commitment verifying unit <b>1202</b><i>u </i>of the network terminal <b>1200</b><i>u </i>uses the commitment verifying algorithm V on the commitment com_vof the network terminal <b>1200</b><i>v</i>, which is the partner in the list matching, to verify whether the commitment results in the relation of V(com_v)=1, thereby confirming that the commitment com_vis the legal commitment. If the commitment com, results in the relation of V(com_v)=0, the subsequent process is not performed on the network terminal <b>1200</b><i>v </i>(therefore, no list exchange occurs). The network terminal <b>1200</b><i>v </i>also performs the similar process on the commitment com_u.

p-0183ii. Generation of Answering Message

p-0184The matching unit <b>1203</b><i>u </i>of the network terminal <b>1200</b><i>u </i>uses the commitment open value open_uthereof and the matching algorithm M on the legal commitment com_vof the network terminal <b>1200</b><i>v </i>to compute an answering message ans_u,v=M(open_u, com_v), and transmits the answering message to the network terminal <b>1200</b><i>v</i>, which is the partner in the list matching. The network terminal <b>1200</b><i>v </i>also performs the similar process on the commitment com_u.

p-0185iii. Result Output

p-0186The matching result output unit <b>1204</b><i>u </i>of the network terminal <b>1200</b><i>u </i>receives the answering message ans_v,ufrom the network terminal <b>1200</b><i>v</i>. If the answering message ans_v,uis not received, the exception processing process described later is performed. The matching result output unit <b>1204</b><i>u </i>uses the list L_u, secret key K_uand commitment open value open_uthereof, the legal commitment com_vof the network terminal <b>1200</b><i>v </i>and the result output algorithm D on the answering message ans_v,ureceived from the network terminal <b>1200</b><i>v </i>to compute the result res_v,u=D(ans_v,u, com_v, L_u, K_u, open_u). If the answering message ans_v,uis the legal answering message, the result res_v,uis the common part (L_u∩L_v) among the list L_uof the network terminal <b>1200</b><i>u </i>and the list L_vof the network terminal <b>1200</b><i>v</i>. If the result res_v,uis an error, the exception processing process is performed. The network terminal <b>1200</b><i>v </i>also performs the similar process on the answering message ans_u,v.

p-0187(b) Exception Processing Process

p-0188i. Exception Processing Request

p-0189If an exception that the network terminal <b>1200</b><i>u </i>cannot compute the common part to the lists occurs, that is, if the answering message ans_v,uis not transmitted from the network terminal <b>1200</b><i>v </i>or an erroneous answering message ans_v,uis transmitted therefrom, the result output unit <b>1205</b><i>u </i>of the network terminal <b>1200</b><i>u </i>uses the list L_uthereof, the legal commitment com, of the network terminal <b>1200</b><i>v </i>and the exception processing request generation algorithm P to compute the exception processing request message ereq_v,u=P(com_v, L_u) and transmits the same to the TTP server <b>1210</b>.

p-0190ii. Exception Processing

p-0191After receiving the exception processing request message ereq_v,u, the TTP server <b>1210</b> confirms that the exception occurs through a prescribed procedure. If the exception is not confirmed, the TTP server returns an error to the network terminal <b>1200</b><i>u</i>. If the exception is confirmed, the exception processing execution unit <b>1211</b> uses the exception processing algorithm T and the secret key K_Tto compute the exception processing answering message eans_v,u=T(ereq_v,u, K_T) Then, the TTP server <b>1210</b> transmits the computed exception processing answering message eans_v,uto the network terminal <b>1200</b><i>u. </i>

p-0192iii. Exception Processing Result Output

p-0193The exception processing result output unit <b>1206</b><i>u </i>of the network terminal <b>1200</b><i>u </i>uses, as the inputs, the exception processing answering message eans_v,ureceived from the TTP server <b>1210</b> and the secret key K_Tof the network terminal <b>1200</b><i>u </i>to compute the exception processing result eres_v,u=W(eans_v,u, K_u), and outputs the same. The exception processing result eres_v,uis the common part (L_u∩L_v) among the list L_uof the network terminal <b>1200</b><i>u </i>and the list Lv of the network terminal <b>1200</b><i>v. </i>

p-0194In the operation described above, by opening the commitment to the list thereof, each network terminal <b>1200</b> can assure the other network terminal that it does not falsify the list in the list matching. In addition, the commitment includes information that enables the TTP server <b>1210</b> to compute the common part to the lists for preventing one of the network terminals from suffering a disadvantage when the exception occurs. At the start of the normal process, each network terminal <b>1200</b> can use the commitment verifying algorithm V to check that “the commitment is properly configured, and if anything should occur, the problem can be solved by the TTP server <b>1210</b>”.

p-0195In addition, to make the falsification of the list difficult, the answering message is computed using the opened commitment as the input. Therefore, information about the list of the network terminal <b>1200</b>, which is the partner in the list matching, cannot be illegally obtained by list falsification. Furthermore, it is provided that, when one of the network terminals <b>1200</b> arbitrarily interrupts the protocol without transmitting the answering message or transmits a message computed illegally, the TTP server <b>1210</b> can compute the common part to the lists based on the information included in the commitment and exception processing request message. Thus, one network terminal <b>1200</b> cannot exclusively get the information about the common part to the lists in an illegal manner.

p-0196Now, a protocol for implementing the list matching in the system according to this embodiment will be described.

p-0197First of all, parameters used in this protocol will be described.

p-0198Reference symbol G_qdenotes a group of an order q (q denotes a prime number) for which the Decisional Diffice-Hellman (DDH) assumption holds true, and reference symbols g and h denote random elements of the group G_q. Here, the value of log_gh is unknown. Reference symbol H(•) denotes an ideal one-way hash function, and the commitment for α∈Z_qis expressed as π(α, r)=g^αh^r(r∈_RZ_q). Here, x∈_RG means that “x is an element randomly extracted from the group G”. The ElGamal encryption E_y(m, r) on the group G_qis defined as follows: <br /><i>E</i>_y(<i>m,r</i>)=(<i>g</i>^r<i>,my</i>^r)(<i>r∈</i>_R<i>Z</i>_q).

p-0199In this equation, reference symbol m denotes a plaintext (message) and reference symbol y denotes a public key. Decryption by the secret key associated with the public key y is expressed as D_y(that is, D_y(E_y(m, r))=m). It is known that, if m is limited to the elements of the group G_q, the encryption is semantically secure under the DDH assumption. The ElGamal encryption has the following characteristics: <br />(<i>E</i>_y(<i>m,r</i>))^k=((<i>g</i>^r)^k,(<i>my</i>^r)^k)=<i>E</i>_y(<i>m</i>^k<i>,kr</i>); and<br /><i>E</i>_y(<i>m,r</i>)×<i>E</i>_y(<i>m′,r′</i>)=(<i>g</i>^r<i>g</i>^r<i>′,my</i>^r(<i>m′y</i>^r′))=<i>E</i>_y(<i>mm′,r+r</i>′).

p-0200Hereinafter, E(m, r) will be appropriately expressed as E(m) by omitting the random number r as required in the context.

p-0201The protocol implemented in this embodiment is defined on any group GF(q) for which the discrete logarithm problem becomes difficult in terms of computational complexity. Specific examples of the group GF(q) include:

p-0202(1) a group formed on a prime field of an order p: a group GF(q) formed with a generator g, g denoting an element of the order q on the finite field Z_p, and p denoting a large prime number satisfying a relation of q|p−1;

p-0203(2) a group formed by associating a multiplication on the prime field of the order p with an addition on a curve, such as an elliptic curve, on any finite field; and

p-0204(3) a group formed by substituting a power of a prime number p′ for the prime number p and performing an operation on an extension field GF(p′) instead of a remainder operation with a modulus of the prime number p.

p-0205Now, an existing basic protocol used in this embodiment will be described.

p-0206OPE using the ElGamal encryption:

p-0207It is assumed that the information exchange is accomplished between two parties A and B. The public key of the party A is denoted by y.

p-0208It is assumed that the party A has a secret value α(∈Z_q), and the party B has a secret polynomial f_B(x) expressed as the following formula 2.

p-0209<maths id="MATH-US-00006" num="00006"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>f</mi><mi>B</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><msub><mi>b</mi><mi>i</mi></msub><mo>⁢</mo><msup><mi>x</mi><mi>i</mi></msup><mo>⁢</mo><mstyle><mspace width="1.9em" height="1.9ex" /></mstyle><mo>⁢</mo><mrow><mo>(</mo><mrow><mi>mod</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>q</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>2</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0210This protocol has properties: <ul><li id="ul0013-0001" num="0000"><ul><li id="ul0014-0001" num="0245">the party A can get a value g^fB(α)without the party B knowing the value α; and</li><li id="ul0014-0002" num="0246">the party A cannot get any information about the polynomial f_B(x) except for the value g^fB(α).</li></ul></li></ul>

p-0211Contents of the protocol will be described below.

p-02121. The party A ElGamal-encrypts a value expressed as the following formula 3 into a value expressed as the following formula 4 using a random number r_i(∈RZ_q), where i=1, . . . , n. <br />α²  (Formula 3)<br /><i>c</i>_i<i>=E</i>_y(<i>g</i>^α^{<sup2>i</sup2>}<i>,r</i>_i)  (Formula 4)

p-0213The party A transmits the values c₁, . . . , c_nto the party B.

p-02142. The party B selects a random number r0(∈_RZ_q) and performs the computation expressed as the following formula 5.

p-0215<maths id="MATH-US-00007" num="00007"><math overflow="scroll"><mtable><mtr><mtd><mrow><mover><mi>c</mi><mo>^</mo></mover><mo>=</mo><mrow><mrow><mrow><msub><mi>E</mi><mi>y</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><msup><mi>g</mi><msub><mi>b</mi><mn>0</mn></msub></msup><mo>,</mo><msub><mi>r</mi><mn>0</mn></msub></mrow><mo>)</mo></mrow></mrow><mo>×</mo><mrow><munderover><mo>∏</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msubsup><mi>C</mi><mi>i</mi><msub><mi>b</mi><mi>i</mi></msub></msubsup></mrow></mrow><mo>=</mo><mrow><msub><mi>E</mi><mi>y</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><msup><mi>g</mi><mrow><msub><mi>f</mi><mi>B</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>a</mi><mo>)</mo></mrow></mrow></msup><mo>,</mo><mi>τ</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>5</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0216where

p-0217<maths id="MATH-US-00008" num="00008"><math overflow="scroll"><mrow><mi>τ</mi><mo>=</mo><mrow><msub><mi>r</mi><mn>0</mn></msub><mo>+</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><msub><mi>b</mi><mi>i</mi></msub><mo>⁢</mo><msub><mi>r</mi><mi>i</mi></msub><mo>⁢</mo><mstyle><mspace width="2.8em" height="2.8ex" /></mstyle><mo>⁢</mo><mrow><mo>(</mo><mrow><mi>mod</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>q</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></math></maths>

p-0218The party B transmits a cryptogram <br />^ (also expressed as ^<i>c</i>, hereinafter)  (Formula 6)

p-0219to the party A.

p-02203. The party A decrypts the cryptogram ^c to obtain the value g^fB(α).

p-0221Certification Protocol 1:

p-0222Reference symbols m₀, m₁denote elements of the group G_q, and a cryptogram expressed as ^c₁=(c₁, c₂)=E_y(m₁, β)=(g^β, m₁y^β) is the ElGamal cryptogram of the element m₁with the public key y. Here, it is to be certified that with respect to common inputs (g, y, m₀, ^c), a discrete logarithm a of the plaintext m₁corresponding to the cryptogram ^c to the plaintext m₀is known. That is, a non-interactive certification of knowledge expressed as (e, s, t)=PKa{(α, β): (c₁=gβ)<img id="CUSTOM-CHARACTER-00002" he="1.44mm" wi="2.46mm" file="US07979712-20110712-P00002.TIF" alt="custom character" img-content="character" img-format="tif" />(c₂=m₁yβ)<img id="CUSTOM-CHARACTER-00003" he="0.68mm" wi="0.68mm" file="US07979712-20110712-P00001.TIF" alt="custom character" img-content="character" img-format="tif" />(m₁=m₀α)} can be configured in the following manner.

p-02231. Select random numbers r₁, r₂∈_RZ_q.

p-02242. Compute the non-interactive certification (e, s, t) using the following formulas 7. <br /><i>e=H</i>(<i>g∥y∥m</i>₀<i>∥ĉ∥g</i>^r^{<sub2>1</sub2>}<i>∥y</i>^r^{<sub2>1</sub2>}<i>m</i>₀^r^{<sub2>2</sub2>})<br /><i>s=r</i>₁<i>−eβ</i><br /><i>t=r</i>₂<i>−e</i>α(mod <i>q</i>)  (Formula 7)

p-0225The verifier accepts the certification when the following formula 8 holds true. <br /><i>e=H</i>(<i>g∥y∥m</i>₀<i>∥ĉ∥g</i>^s<i>c</i>₁^e<i>∥y</i>^s<i>m</i>₀^t<i>c</i>₂^e)  (Formula 8)

p-0226Certification Protocol 2:

p-0227Reference symbols m₁, m₂, m′₁, m′₂denote elements of the group G_q, and cryptograms expressed as <br />^<i>c</i>₁=(<i>c</i>_1,1<i>,c</i>_1,2)=<i>E</i>_y(<i>m′</i>₁,β₁)=(<i>g</i>^β^{<sub2>1</sub2>}<i>,m′</i>₁<i>y</i>^β^{<sub2>1</sub2>})<br />^<i>c</i>₂=(<i>c</i>_2,1<i>,c</i>_2,2)=<i>E</i>_y(<i>m′</i>₂,β₂)=(<i>g</i>^β^{<sub2>2</sub2>}<i>,m′</i>₂<i>y</i>^β^{<sub2>2</sub2>})

p-0228are the ElGamal cryptograms of the elements m′₁, m′₂, respectively, with the public key y. Here, it is to be certified that with respect to common inputs (g, y, m₁, m2, ^c₁, ^c₂), discrete logarithms of the plaintexts m′₁, m′₂corresponding to the cryptograms ^c₁, ^c₂to the plaintexts m₁, m₂, respectively, are equal to each other. That is, a non-interactive certification of knowledge expressed as (e, s, t, u)=PK{(α, β₁, β₂): {(c_i,1=g^β^{<sub2>i</sub2>})<img id="CUSTOM-CHARACTER-00004" he="0.68mm" wi="0.68mm" file="US07979712-20110712-P00001.TIF" alt="custom character" img-content="character" img-format="tif" />(c_i,2=m′_iy^β^{<sub2>1</sub2>})<img id="CUSTOM-CHARACTER-00005" he="0.68mm" wi="0.68mm" file="US07979712-20110712-P00001.TIF" alt="custom character" img-content="character" img-format="tif" />(m′₁=m₁^α)}_i=1,2} can be configured in the following manner.

p-02291. Select random numbers r₁, r₂, r₃∈_RZ_q.

p-02302. Compute the non-interactive certification (e, s, t, u) using the following formulas 9. <br /><i>e=H</i>(<i>g∥y∥m</i>₁<i>∥m</i>₂<i>∥ĉ</i>₁<i>∥ĉ</i>₂<i>∥g</i>^r^{<sub2>1</sub2>}<i>∥g</i>^r^{<sub2>2</sub2>}<i>∥y</i>^r^{<sub2>1</sub2>}<i>m</i>₁^r^{<sub2>3</sub2>}<i>∥y</i>^r^{<sub2>2</sub2>}<i>m</i>₂^r^{<sub2>3</sub2>})<br /><i>s=r</i>₁<i>−eβ</i>₁<br /><i>t=r</i>₂<i>−eβ</i>₂<br /><i>u=r</i>₃<i>−e</i>α(mod <i>q</i>)  (Formula 9)

p-0231The verifier accepts the certification when the following formula 10 holds true. <br /><i>e=H</i>(<i>g∥y∥m</i>₁<i>∥m</i>₂<i>∥ĉ</i>₁<i>∥ĉ</i>₂<i>∥g</i>^s<i>c</i>_1,1^e<i>∥g</i>^t<i>c</i>_2,1^e<i>∥y</i>₁^s<i>m</i>₁^u<i>c</i>_1,2^e<i>∥y</i>₂^t<i>m</i>₂^u<i>c</i>_2,2^e)  (Formula 10)

p-0232A non-interactive certification expressed as PK{(α, {β_i}_i=1ⁿ): {(c_i,1=gβⁱ)<img id="CUSTOM-CHARACTER-00006" he="0.68mm" wi="0.68mm" file="US07979712-20110712-P00001.TIF" alt="custom character" img-content="character" img-format="tif" />(c_i,2=m′_iyβⁱ)<img id="CUSTOM-CHARACTER-00007" he="0.68mm" wi="0.68mm" file="US07979712-20110712-P00001.TIF" alt="custom character" img-content="character" img-format="tif" />(m′_i=miα)}_i=1ⁿ} can be readily configured by expanding this approach.

p-0233Certification Protocol 3:

p-0234Reference symbols m₀denotes an element of the group G_q, and a cryptogram expressed as ^ci=(c_i,1, c_i,2)=(gβ¹, m_iyβⁱ) is the ElGamal cryptogram of the element m_iwith the public key y. Here, it is to be certified that with respect to common inputs (g, y, m₀, ĉ₁, . . . , ĉ_n), there exists a discrete logarithm a satisfying a function expressed as the following formula 11, without disclosing the discrete logarithm α. <br />(<i>m</i>₀<i>,D</i>_y(<i>ĉ</i>₁),<i>D</i>_y(<i>ĉ</i>₂), . . . ,<i>D</i>_y(<i>ĉ</i>_n))=(<i>m</i>₀<i>,m</i>₀^α<i>,m</i>₀^α^{<sup2>2</sup2>}<i>, . . . ,m</i>₀^α^{<sup2>n</sup2>})  (Formula 11)

p-0235That is, a non-interactive certification of knowledge expressed as the following formula 12 can be configured in the following manner. Here, for simplicity, it is assumed that (c_0,1, c_0,2)=E_y(m₀, 0)=(1, m₀), β₀=0.

p-0236<maths id="MATH-US-00009" num="00009"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mo>(</mo><mrow><mi>e</mi><mo>,</mo><msubsup><mrow><mo>{</mo><msub><mi>s</mi><mi>i</mi></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>,</mo><mi>t</mi></mrow><mo>)</mo></mrow><mo>=</mo><mrow><mi>PK</mi><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mo>(</mo><mrow><mi>a</mi><mo>,</mo><msubsup><mrow><mo>{</mo><msub><mi>β</mi><mi>i</mi></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></mrow><mo>)</mo></mrow><mo>:</mo><msubsup><mrow><mo>{</mo><mrow><mrow><mo>(</mo><mrow><msub><mi>c</mi><mrow><mi>i</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>=</mo><msup><mi>g</mi><msub><mi>β</mi><mi>i</mi></msub></msup></mrow><mo>)</mo></mrow><mo>⩓</mo><mrow><mo>(</mo><mrow><msub><mi>c</mi><mrow><mi>i</mi><mo>,</mo><mn>2</mn></mrow></msub><mo>=</mo><mrow><msub><mi>m</mi><mi>i</mi></msub><mo>⁢</mo><msup><mi>y</mi><msub><mi>β</mi><mi>i</mi></msub></msup></mrow></mrow><mo>)</mo></mrow><mo>⩓</mo><mrow><mo>(</mo><mrow><msub><mi>m</mi><mi>i</mi></msub><mo>=</mo><msubsup><mi>m</mi><mn>0</mn><msup><mi>a</mi><mi>i</mi></msup></msubsup></mrow><mo>)</mo></mrow></mrow><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></mrow><mo>}</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>12</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-02371. Select random numbers r₁, r₂∈_RZ_q.

p-02382. Compute the non-interactive certification (e, s₁, . . . , s_n, t) using the following formulas 13.

p-0239<maths id="MATH-US-00010" num="00010"><math overflow="scroll"><mtable><mtr><mtd><mtable><mtr><mtd><mrow><msubsup><mrow><mrow><mi>e</mi><mo>⁢</mo><mi /><mo>=</mo><mrow><mrow><mi>H</mi><mo>(</mo><mrow><mi>g</mi><mo>⁢</mo><mrow><mo></mo><mi>y</mi><mo></mo></mrow><mo>⁢</mo><msub><mi>m</mi><mn>0</mn></msub></mrow><mo></mo></mrow><mo>⁢</mo><mrow><mo>{</mo><mrow><msub><mover><mi>c</mi><mo>^</mo></mover><mi>i</mi></msub><mo>,</mo><mrow><msup><mi>g</mi><msub><mi>r</mi><mi>i</mi></msub></msup><mo>⁢</mo><msubsup><mi>c</mi><mrow><mi>i</mi><mo>,</mo><mn>1</mn></mrow><mi>w</mi></msubsup></mrow><mo>,</mo><mrow><msup><mi>y</mi><msub><mi>r</mi><mi>i</mi></msub></msup><mo>⁢</mo><msubsup><mi>c</mi><mrow><mi>i</mi><mo>,</mo><mn>2</mn></mrow><mi>w</mi></msubsup></mrow></mrow><mo>)</mo></mrow></mrow></mrow><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>s</mi><mi>i</mi></msub><mo>⁢</mo><mi /><mo>=</mo><mrow><msub><mi>r</mi><mi>i</mi></msub><mo>+</mo><mrow><mrow><mi>e</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><msub><mi>β</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>⁢</mo><mi>a</mi></mrow><mo>-</mo><msub><mi>β</mi><mi>i</mi></msub></mrow><mo>)</mo></mrow></mrow><mo>⁢</mo><mrow><mo>(</mo><mrow><mi>mod</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>q</mi></mrow><mo>)</mo></mrow><mo>⁢</mo><mrow><mo>(</mo><mrow><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>,</mo><mi>n</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi>t</mi><mo>⁢</mo><mi /><mo>=</mo><mrow><mi>w</mi><mo>-</mo><mrow><mi>ea</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>mod</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>q</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mtd></mtr></mtable></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>13</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0240The verifier accepts the certification when the following formula 14 holds true.

p-0241<maths id="MATH-US-00011" num="00011"><math overflow="scroll"><mtable><mtr><mtd><mrow><mi>e</mi><mo>=</mo><mrow><mi>H</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>g</mi><mo>⁢</mo><mrow><mo></mo><mi>y</mi><mo></mo></mrow><mo>⁢</mo><msub><mi>m</mi><mn>0</mn></msub><mo>⁢</mo><msubsup><mrow><mo></mo><mrow><mo>{</mo><mrow><msub><mi>c</mi><mi>i</mi></msub><mo>,</mo><mrow><msup><mrow><msup><mi>g</mi><msub><mi>s</mi><mn>1</mn></msub></msup><mo>⁡</mo><mrow><mo>(</mo><msub><mi>c</mi><mrow><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow><mo>,</mo><mn>1</mn></mrow></msub><mo>)</mo></mrow></mrow><mi>t</mi></msup><mo>⁢</mo><msub><mi>c</mi><mrow><mi>i</mi><mo>,</mo><msup><mn>1</mn><mi>e</mi></msup></mrow></msub></mrow><mo>,</mo><mrow><msup><mrow><msup><mi>y</mi><msub><mi>s</mi><mn>1</mn></msub></msup><mo>⁡</mo><mrow><mo>(</mo><msub><mi>c</mi><mrow><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow><mo>,</mo><mn>2</mn></mrow></msub><mo>)</mo></mrow></mrow><mi>t</mi></msup><mo>⁢</mo><msub><mi>c</mi><mrow><mi>i</mi><mo>,</mo><msup><mn>2</mn><mi>e</mi></msup></mrow></msub></mrow></mrow><mo>)</mo></mrow><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></mrow><mo>)</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>14</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0242<figref idrefs="DRAWINGS">FIG. 15</figref> illustrates a protocol of the list matching according to this embodiment, which is implemented by the basic protocol described above. The following description will be made with reference to <figref idrefs="DRAWINGS">FIG. 15</figref>. Here, numbers shown within parentheses in this drawing correspond to the numbers in the following procedure, respectively.

p-0243[1] For the list L_u={α_u,1, . . . , α_u,n}, the network terminal <b>1200</b><i>u </i>computes a characteristic function expressed as the following formula 15. <br /><i>f</i>_u(<i>x</i>)=Π_α_{<sub2>u,1</sub2>}_∈L_{<sub2>A</sub2>}(α_u,1<i>−x</i>)/α_u,1(mod <i>q</i>)  (Formula 15)

p-0244Here, the characteristic function expressed as the following formula 16 has a constant term of 1 and all the elements of the list L_uas the roots.

p-0245<maths id="MATH-US-00012" num="00012"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>f</mi><mi>u</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mn>1</mn><mo>+</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mrow><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>⁢</mo><msup><mi>x</mi><mn>1</mn></msup></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mn>16</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0246[2] The network terminal <b>1200</b><i>u </i>creates a commitment {c_u,1=g^au,lh^bu,l}_l=1ⁿfor an efficient {a_u,l}_l=1ⁿ. Here, the following formula 17 is defined.

p-0247<maths id="MATH-US-00013" num="00013"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>w</mi><mi>u</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mrow><msub><mi>b</mi><mrow><mi>u</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>⁢</mo><msup><mi>x</mi><mn>1</mn></msup><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mrow><mo>(</mo><mrow><mi>mod</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>q</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>17</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0248[3] By applying the OPE approach using the ElGamal encryption, according to the OPE adopting the item α_u,1in the list (α_u,1∈L_u) as the input, the network terminal <b>1200</b><i>u </i>verifies whether the item α_u,iis a root of the polynomial f_v(x) of the network terminal <b>1200</b><i>v</i>. For this purpose, the following processings are performed on all the items α_u,i∈L_u(i=1, . . . , n).

p-0249(a) Select elements g_u,i, h_u,i∈G_q. Here, values t_g^{(u, i)}=log_gg_u,iand t_h^{(u, i)}=log_hh_u,iare only known to the network terminal <b>1200</b><i>u. </i>

p-0250(b) Compute the following formulas 18 (reference symbol y_Tdenotes the public key of the TTP server <b>1210</b>).

p-0251<maths id="MATH-US-00014" num="00014"><math overflow="scroll"><mtable><mtr><mtd><msubsup><mrow><mo>{</mo><mrow><msubsup><mi>ψ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>g</mi><mrow><mi>u</mi><mo>,</mo><msup><mi>i</mi><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><msup><mi>i</mi><mi>j</mi></msup></mrow></msub></msup></mrow></msub><mo>)</mo></mrow></mrow></mrow><mo>}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mn>18</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0252<maths id="MATH-US-00015" num="00015"><math overflow="scroll"><msubsup><mrow><mo>{</mo><mrow><msubsup><mi>ψ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>h</mi><mrow><mi>u</mi><mo>,</mo><msup><mi>i</mi><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><msup><mi>i</mi><mi>j</mi></msup></mrow></msub></msup></mrow></msub><mo>)</mo></mrow></mrow></mrow><mo>}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></math></maths><maths id="MATH-US-00015-2" num="00015.2"><math overflow="scroll"><msubsup><mrow><mo>{</mo><mrow><msubsup><mi>ψ</mi><mi>c</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>c</mi><mrow><mi>u</mi><mo>,</mo><msup><mi>i</mi><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><msup><mi>i</mi><mi>j</mi></msup></mrow></msub></msup></mrow></msub><mo>)</mo></mrow></mrow></mrow><mo>}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></math></maths><maths id="MATH-US-00015-3" num="00015.3"><math overflow="scroll"><mrow><msubsup><mi>ψ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>T</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msup><mi>g</mi><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub></msup><mo>)</mo></mrow></mrow></mrow></math></maths>

p-0253In addition, a certification pk_u,i,lfor showing that the computations have been properly conducted is created. φ_t(^u,*,*), which can be reproduced at the TTP server <b>1210</b>, enables verification that the TTP server <b>1210</b> can solve a problem when the problem occurs.

p-0254(c) Create a certification pk_u,i,2for showing that the item α_u,isatisfies the equation f_u(α_u,i)=0. This certification is effected by using the following formula 19 to certify of the knowledge of the discrete logarithm for h in the following formula 20.

p-0255<maths id="MATH-US-00016" num="00016"><math overflow="scroll"><mtable><mtr><mtd><msubsup><mrow><mo>{</mo><msubsup><mi>ψ</mi><mi>c</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mn>19</mn></mrow><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><mrow><msub><mi>D</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>g</mi><mo>×</mo><mrow><munderover><mo>∏</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msubsup><mi>ψ</mi><mi>c</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup></mrow></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><msup><mi>g</mi><mrow><msub><mi>f</mi><mi>u</mi></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow></mrow></msup><mo>⁢</mo><msup><mi>h</mi><mrow><msub><mi>w</mi><mi>u</mi></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow></mrow></msup></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>20</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0256(d) Compose public information d_u,iassociated with the item α_u,ias expressed by the following formula 21.

p-0257<maths id="MATH-US-00017" num="00017"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>d</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>=</mo><mrow><mo>(</mo><mrow><msub><mi>g</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>,</mo><msub><mi>h</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>,</mo><msubsup><mrow><mo>{</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msubsup><mi>ψ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>,</mo><msubsup><mrow><mo>{</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msubsup><mi>ψ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>,</mo><msubsup><mrow><mo>{</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msubsup><mi>ψ</mi><mi>c</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>,</mo><msubsup><mi>ψ</mi><mi>t</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><mrow><mi>p</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>k</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mn>1</mn></mrow></msub></mrow><mo>,</mo><mrow><mi>p</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>k</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mn>2</mn></mrow></msub></mrow></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mn>21</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0258Thus, the commitment com_uto be opened is expressed a the following formula 22.

p-0259<maths id="MATH-US-00018" num="00018"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>com</mi><mi>u</mi></msub><mo>=</mo><mrow><mo>(</mo><mrow><msubsup><mrow><mo>{</mo><msub><mi>c</mi><mrow><mi>u</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>}</mo></mrow><mrow><mn>1</mn><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>⁢</mo><mrow><mo></mo><msubsup><mrow><mo>{</mo><msub><mi>d</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mn>22</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0260[4] The network terminal <b>1200</b><i>v</i>, which has received the commitment com_uof the network terminal <b>1200</b><i>u</i>, performs the following processings, where i=1, . . . , n.

p-0261(a) Verify the certifications pk_u,i,1and pk_u,i,2included in the public information d_u,i.

p-0262(b) Using the following formulas 23, compute φ_g^(u,v,i)and φ_h^(u,v,i).

p-0263<maths id="MATH-US-00019" num="00019"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msubsup><mi>φ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><mrow><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>g</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow></mrow><mo>×</mo><mrow><munderover><mo>∏</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msup><mrow><mo>(</mo><msubsup><mi>ψ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><msub><mi>a</mi><mrow><mi>v</mi><mo>,</mo><mi>j</mi></mrow></msub></msup></mrow></mrow><mo>=</mo><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>g</mi><mrow><mi>u</mi><mo>,</mo><msup><mi>i</mi><mrow><msub><mi>f</mi><mi>u</mi></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow></mrow></msup></mrow></msub><mo>)</mo></mrow></mrow></mrow></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><msubsup><mi>φ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><mrow><munderover><mo>∏</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msup><mrow><mo>(</mo><msubsup><mi>ψ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><msub><mi>b</mi><mrow><mi>v</mi><mo>,</mo><mi>j</mi></mrow></msub></msup></mrow><mo>=</mo><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>h</mi><mrow><mi>u</mi><mo>,</mo><msup><mi>i</mi><mrow><msub><mi>w</mi><mi>u</mi></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow></mrow></msup></mrow></msub><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>23</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0264(c) Raise φ_g^(u,v,i)to ξ₁^(u,v,i)-th power to conceal the information not involved in determining whether the item α_u,iis a root of the polynomial f_v( ), as expressed by the following formula 24.

p-0265<maths id="MATH-US-00020" num="00020"><math overflow="scroll"><mtable><mtr><mtd><mrow><msubsup><mi>μ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><msup><mrow><mo>(</mo><msubsup><mi>φ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><msubsup><mi>ξ</mi><mn>1</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></msup></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>24</mn></mrow><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><msup><mrow><mo>(</mo><msub><mi>h</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow><msubsup><mi>ξ</mi><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></msup><mo>⁢</mo><mrow><mo>(</mo><mrow><msubsup><mi>ξ</mi><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>∈</mo><msub><mi>Z</mi><mi>q</mi></msub></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mn>25</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0266On the other hand, information that enables the network terminal <b>1200</b><i>u </i>to verify, using only the opened commitment com_v, whether these processings are properly conducted is created. At first, the function φ_n^(u,v,i)is multiplied by a function expressed by the following formula 25 to conceal the information associated with w_v(α_u,i). Then, a certification showing that these processings are properly conducted is created as expressed by the following formulas 26.

p-0267<maths id="MATH-US-00021" num="00021"><math overflow="scroll"><mtable><mtr><mtd><mtable><mtr><mtd><mrow><msup><mi>ρ</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo>=</mo><mrow><mo>(</mo><mrow><msup><mi>v</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo>,</mo><msubsup><mi>μ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mi>λ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mi>λ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><msup><mi>s</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup></mrow><mo>)</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msup><mi>v</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo>⁢</mo><mi /><mo>=</mo><mrow><mrow><mo>(</mo><msub><mi>h</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow><mo>⁢</mo><msubsup><mi>ξ</mi><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>V</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mi>μ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><mi /><mo>=</mo><mrow><mrow><mo>(</mo><mrow><mrow><mo>(</mo><msub><mi>h</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow><mo>⁢</mo><msubsup><mi>ξ</mi><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>V</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>×</mo><msubsup><mi>φ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow><mo>)</mo></mrow><mo>⁢</mo><msubsup><mi>ξ</mi><mn>1</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mi>λ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><mi /><mo>=</mo><mrow><mrow><mo>(</mo><msubsup><mi>φ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><mo>⁢</mo><msubsup><mi>ξ</mi><mn>3</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>vi</mi></mrow><mo>)</mo></mrow></msubsup></mrow></mrow></mtd></mtr></mtable></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>26</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0268Thus, an answering message is expressed by the following formula 27.

p-0269<maths id="MATH-US-00022" num="00022"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>ans</mi><mrow><mi>u</mi><mo>,</mo><mi>v</mi></mrow></msub><mo>=</mo><msubsup><mrow><mo>{</mo><mrow><msubsup><mi>μ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><msup><mi>ρ</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup></mrow><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>27</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0270[5] The network terminal <b>1200</b><i>u</i>, which has received the answering message ans_u,v, performs the following processings, where i=1, . . . , n.

p-0271(a) verify the certification ρ^(u,v,i)using the commitment com_vof the network terminal <b>1200</b><i>u</i>. Specifically, the following formulas 28 are computed and it is verified whether the formula 29 holds true.

p-0272<maths id="MATH-US-00023" num="00023"><math overflow="scroll"><mtable><mtr><mtd><mtable><mtr><mtd><mrow><mrow><msup><mover><mi>ⅇ</mi><mo>~</mo></mover><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo>⁢</mo><mi /><mo>=</mo><mrow><mrow><mi>H</mi><mo>(</mo><mrow><msub><mi>com</mi><mi>u</mi></msub><mo>⁢</mo><mrow><mo></mo><msup><mi>v</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo></mo></mrow><mo>⁢</mo><msubsup><mi>μ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow><mo></mo></mrow><mo>⁢</mo><msubsup><mi>μ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><mrow><mo></mo><msubsup><mi>λ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo></mo></mrow><mo>⁢</mo><msubsup><mi>λ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></mrow><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mi>σ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><mi /><mo>=</mo><mrow><mrow><msub><mi>D</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msup><mrow><mo>(</mo><msubsup><mi>μ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><mrow><mn>1</mn><mo>/</mo><msubsup><mi>t</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></msup><mo>)</mo></mrow></mrow><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>[</mo><mrow><mo>=</mo><msup><mi>g</mi><mrow><msubsup><mi>ξ</mi><mn>1</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>×</mo><mrow><msub><mi>f</mi><mi>v</mi></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow></mrow></mrow></msup></mrow><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mi>σ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><mi /><mo>=</mo><mrow><mrow><msub><mi>D</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msup><mrow><mo>(</mo><msubsup><mi>μ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><mrow><mn>1</mn><mo>/</mo><msubsup><mi>t</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></msup><mo>)</mo></mrow></mrow><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>[</mo><mrow><mo>=</mo><msup><mi>h</mi><mrow><msubsup><mi>ξ</mi><mn>1</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>×</mo><mrow><mo>(</mo><mrow><mrow><msub><mi>w</mi><mi>v</mi></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow></mrow><mo>+</mo><msubsup><mi>ξ</mi><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></mrow></mrow></msup></mrow><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mi>τ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><mi /><mo>=</mo><mrow><mrow><msub><mi>D</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msup><mrow><mo>(</mo><msubsup><mi>λ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><mrow><mn>1</mn><mo>/</mo><msubsup><mi>t</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></msup><mo>)</mo></mrow></mrow><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>[</mo><mrow><mo>=</mo><msup><mi>g</mi><mrow><msubsup><mi>ξ</mi><mn>3</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>×</mo><mrow><msub><mi>f</mi><mi>v</mi></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow></mrow></mrow></msup></mrow><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mi>τ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><mi /><mo>=</mo><mrow><mrow><msub><mi>D</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msup><mrow><mo>(</mo><msubsup><mi>λ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><mrow><mn>1</mn><mo>/</mo><msubsup><mi>t</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></msup><mo>)</mo></mrow></mrow><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>[</mo><mrow><mo>=</mo><msup><mi>h</mi><mrow><msubsup><mi>ξ</mi><mn>3</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>×</mo><mrow><mo>(</mo><mrow><mrow><msub><mi>w</mi><mi>v</mi></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow></mrow><mo>+</mo><msubsup><mi>ξ</mi><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></mrow></mrow></msup></mrow><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msup><mi>η</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo>⁢</mo><mi /><mo>=</mo><mrow><msup><mrow><mo>(</mo><msup><mi>v</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo>)</mo></mrow><mrow><mn>1</mn><mo>/</mo><msubsup><mi>t</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></msup><mo>×</mo><mrow><munderover><mo>∏</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><msubsup><mi>C</mi><mrow><mi>v</mi><mo>,</mo><mi>j</mi></mrow><msubsup><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>j</mi></mrow><mi>j</mi></msubsup></msubsup><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>[</mo><mrow><mo>=</mo><mrow><msup><mi>g</mi><mrow><msub><mi>f</mi><mi>v</mi></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow></mrow></msup><mo>⁢</mo><msup><mi>h</mi><mrow><mo>(</mo><mrow><mrow><msub><mi>w</mi><mi>v</mi></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow></mrow><mo>+</mo><msubsup><mi>ξ</mi><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></mrow></msup></mrow></mrow><mo>]</mo></mrow></mrow></mrow></mrow></mtd></mtr></mtable></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>28</mn></mrow><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><mrow><msubsup><mi>τ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><msubsup><mi>τ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow><mo>=</mo><mrow><msup><mrow><mo>(</mo><msup><mi>η</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo>)</mo></mrow><msup><mi>S</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup></msup><mo>⁢</mo><msup><mrow><mo>(</mo><mrow><msubsup><mi>σ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><msubsup><mi>σ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow><mo>)</mo></mrow><msup><mover><mi>e</mi><mo>~</mo></mover><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup></msup></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>29</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0273(b) Perform the exception processing if the verification is not passed. If α_g^(u,v,i)=1, the equation of f_v(α_u,i))=0 holds true, and therefore, it is proved that the relation of α_u,i∈L_vis established. To the contrary, if α_g^(u,v,i)≠1, the relation expressed by the following formula 30 is resulted. <br />α_u,i<i>∉L</i>_v  (Formula 30)

p-0274[6] When an exception occurs, the network terminal <b>1200</b><i>u </i>uses a value expressed by the following formula 31 included in the commitment com, of the network terminal <b>1200</b><i>v </i>to perform the exception processing. Specifically, the following formulas 32 are computed.

p-0275<maths id="MATH-US-00024" num="00024"><math overflow="scroll"><mtable><mtr><mtd><mrow><msubsup><mi>ψ</mi><mi>t</mi><mrow><mo>(</mo><mrow><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>T</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msup><mi>g</mi><msub><mi>a</mi><mrow><mi>v</mi><mo>,</mo><mi>i</mi></mrow></msub></msup><mo>)</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>31</mn></mrow><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mtable><mtr><mtd><mrow><msubsup><mi>κ</mi><mn>1</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><mrow><mo>(</mo><msubsup><mi>ψ</mi><mi>t</mi><mrow><mo>(</mo><mrow><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><mo>×</mo><msup><mi>g</mi><mrow><mo>-</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>j</mi></mrow></msub></mrow></msup><mo>⁢</mo><mrow><msubsup><mi>y</mi><mi>u</mi><mrow><mi>z</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></mrow></msubsup><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>[</mo><mrow><mo>=</mo><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>T</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><msup><mi>g</mi><mrow><msub><mi>a</mi><mrow><mi>v</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>-</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>j</mi></mrow></msub></mrow></msup><mo>⁢</mo><msubsup><mi>y</mi><mi>u</mi><mrow><mi>z</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></mrow></msubsup></mrow><mo>)</mo></mrow></mrow></mrow><mo>]</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mi>κ</mi><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><msup><mi>g</mi><msup><mi>z</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msup></msup></mrow></mtd></mtr></mtable></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>32</mn></mrow><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>ereq</mi><mrow><mi>v</mi><mo>,</mo><mi>u</mi></mrow></msub><mo>=</mo><msubsup><mrow><mo>{</mo><mrow><msubsup><mi>κ</mi><mn>1</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mi>κ</mi><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup></mrow><mo>}</mo></mrow><mrow><mi>i</mi><mo>,</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow></mrow><mi>n</mi></msubsup></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>33</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0276Then, a value expressed by the following formula 33 is transmitted to the TTP server <b>1210</b>. The TTP server <b>1210</b> decrypts κ₁to obtain the following formula 34.

p-0277<maths id="MATH-US-00025" num="00025"><math overflow="scroll"><mtable><mtr><mtd><mrow><msubsup><mrow><mo>{</mo><mrow><mrow><msub><mi>D</mi><msub><mi>y</mi><mi>T</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msubsup><mi>κ</mi><mn>1</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow></mrow><mo>,</mo><mrow><mo>(</mo><msubsup><mi>κ</mi><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow></mrow><mo>}</mo></mrow><mrow><mi>i</mi><mo>,</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow></mrow><mi>n</mi></msubsup><mo>=</mo><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>T</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msup><mi>g</mi><mrow><msub><mi>a</mi><mrow><mi>v</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>-</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>j</mi></mrow></msub></mrow></msup><mo>)</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>34</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0278This formula represents the ElGamal encryption using the public key y_uof the network terminal <b>1200</b><i>u</i>, which is semantically secure so that any information indicating the common part to the lists L_u, L_vis not leaked to the TTP server <b>1210</b>. The TTP server <b>1210</b> raises the result of the formula 34 to {tilde over ( )}z^(u,v,i,j)-th power for randomizing, and transmits the result, specifically, expressed by the following formula 35, to the network terminal <b>1200</b><i>u</i>. The network terminal <b>1200</b><i>u </i>decrypts this, and if the decryption results in 1, it can be determined as the common part.

p-0279<maths id="MATH-US-00026" num="00026"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>eans</mi><mrow><mi>v</mi><mo>,</mo><mi>u</mi></mrow></msub><mo>=</mo><msubsup><mrow><mo>{</mo><msup><mrow><mo>(</mo><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>T</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msup><mi>g</mi><mrow><msub><mi>a</mi><mrow><mi>v</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>-</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>j</mi></mrow></msub></mrow></msup><mo>)</mo></mrow></mrow><mo>)</mo></mrow><msup><mover><mi>z</mi><mo>~</mo></mover><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msup></msup><mo>}</mo></mrow><mrow><mi>i</mi><mo>,</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow></mrow><mi>n</mi></msubsup></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>35</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0280Next, details of the algorithms used in this embodiment will be described.

p-0281In the following description, reference symbol YT denotes a public key of the TTP server <b>1210</b>. <ul><li id="ul0015-0001" num="0000"><ul><li id="ul0016-0001" num="0318">Commitment generation algorithm C</li></ul></li></ul>

p-0282Input: the list L_u0held by the network terminal <b>1200</b><i>u </i>

p-0283Output: the commitment com, and the commitment open value open_u0

p-0284Processing:

p-0285(1) For the list L_u, a polynomial as expressed by the following formula 36 is created.

p-0286<maths id="MATH-US-00027" num="00027"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>eans</mi><mrow><mi>v</mi><mo>,</mo><mi>u</mi></mrow></msub><mo>=</mo><msubsup><mrow><mo>{</mo><msup><mrow><mo>(</mo><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>T</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msup><mi>g</mi><mrow><msub><mi>a</mi><mrow><mi>v</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>-</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>j</mi></mrow></msub></mrow></msup><mo>)</mo></mrow></mrow><mo>)</mo></mrow><msup><mover><mi>z</mi><mo>~</mo></mover><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msup></msup><mo>}</mo></mrow><mrow><mi>i</mi><mo>,</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow></mrow><mi>n</mi></msubsup></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>36</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0287Here, coefficients are represented by the following formula 37.

p-0288<maths id="MATH-US-00028" num="00028"><math overflow="scroll"><mtable><mtr><mtd><msubsup><mrow><mo>{</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>l</mi></mrow></msub><mo>}</mo></mrow><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>37</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0289(2) Values b_u,l, where l=1, . . . , n, are selected, and the following formula 38 is computed. <br /><i>c</i>_u,1<i>=g</i>^a^{<sub2>u,l</sub2>}<i>h</i>^b^{<sub2>u,l</sub2>}  (Formula 38)

p-0290Here, the following formula 39 is defined.

p-0291<maths id="MATH-US-00029" num="00029"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>w</mi><mi>u</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><msubsup><mi>Σ</mi><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>⁢</mo><msub><mi>b</mi><mrow><mi>u</mi><mo>,</mo><mi>l</mi></mrow></msub><mo>⁢</mo><msup><mi>x</mi><mn>1</mn></msup><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mrow><mo>(</mo><mrow><mi>mod</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>q</mi></mrow><mo>)</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>39</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0292(3) The following formula 40 is computed.

p-0293<maths id="MATH-US-00030" num="00030"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msubsup><mrow><mo>{</mo><msub><mi>d</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>⁢</mo><msub><mi>d</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub></mrow><mo>=</mo><mrow><mo>(</mo><mrow><msub><mi>g</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>,</mo><msub><mi>h</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>,</mo><msubsup><mrow><mo>{</mo><msubsup><mi>ψ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>,</mo><msubsup><mrow><mo>{</mo><msubsup><mi>ψ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>,</mo><msubsup><mrow><mo>{</mo><msubsup><mi>ψ</mi><mi>c</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>,</mo><msubsup><mi>ψ</mi><mi>t</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><mrow><mi>p</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>k</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mn>1</mn></mrow></msub></mrow><mo>,</mo><mrow><mi>p</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>k</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mn>2</mn></mrow></msub></mrow></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mn>40</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0294Values in this formula is computed as expressed by the following formulas 41.

p-0295<maths id="MATH-US-00031" num="00031"><math overflow="scroll"><mtable><mtr><mtd><mtable><mtr><mtd><mrow><msubsup><mi>t</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><mrow><msubsup><mi>t</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><mi /><mo>∈</mo><msub><mi>Z</mi><mi>q</mi></msub></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mrow><msub><mi>g</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>⁢</mo><mi /><mo>=</mo><msup><mi>g</mi><msubsup><mi>t</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></msup></mrow><mo>,</mo><mrow><msub><mi>h</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>=</mo><msup><mi>h</mi><msubsup><mi>t</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></msup></mrow></mrow></mtd></mtr><mtr><mtd><msubsup><mrow><mo>{</mo><mrow><msubsup><mi>ψ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><mi /><mo>=</mo><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msubsup><mi>g</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><msubsup><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mi>j</mi></msubsup></msubsup><mo>)</mo></mrow></mrow></mrow><mo>}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></mtd></mtr><mtr><mtd><msubsup><mrow><mo>{</mo><mrow><msubsup><mi>ψ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><mi /><mo>=</mo><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msubsup><mi>h</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><msubsup><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mi>j</mi></msubsup></msubsup><mo>)</mo></mrow></mrow></mrow><mo>}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></mtd></mtr><mtr><mtd><msubsup><mrow><mo>{</mo><mrow><msubsup><mi>ψ</mi><mi>c</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><mi /><mo>=</mo><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msubsup><mi>c</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><msubsup><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mi>j</mi></msubsup></msubsup><mo>)</mo></mrow></mrow></mrow><mo>}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></mtd></mtr><mtr><mtd><mrow><mo>{</mo><mrow><msubsup><mi>ψ</mi><mi>c</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><mi /><mo>=</mo><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>T</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msup><mi>g</mi><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub></msup><mo>)</mo></mrow></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mi>p</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>k</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mn>1</mn></mrow></msub></mrow><mo>⁢</mo><mi /><mo>=</mo><mrow><mi>PK</mi><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mo>(</mo><msubsup><mrow><mo>{</mo><msub><mi>γ</mi><mi>j</mi></msub><mo>}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>)</mo></mrow><mo>:</mo><mrow><msubsup><mrow><mo>(</mo><mrow><mrow><msub><mi>D</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msubsup><mi>ψ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow></mrow><mo>=</mo><msubsup><mi>g</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><msub><mi>γ</mi><mi>j</mi></msub></msubsup></mrow><mo>)</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>⩓</mo><msubsup><mrow><mo>(</mo><mrow><mrow><msub><mi>D</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msubsup><mi>ψ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow></mrow><mo>=</mo><msubsup><mi>h</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><msub><mi>γ</mi><mi>j</mi></msub></msubsup></mrow><mo>)</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>⩓</mo></mrow></mrow></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi /><mo>⁢</mo><mrow><msubsup><mrow><mo>(</mo><mrow><mrow><msub><mi>D</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msubsup><mi>ψ</mi><mi>c</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow></mrow><mo>=</mo><msubsup><mi>c</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><msub><mi>γ</mi><mi>j</mi></msub></msubsup></mrow><mo>)</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>⩓</mo><mrow><mo>(</mo><mrow><mrow><msub><mi>D</mi><msub><mi>y</mi><mi>T</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msubsup><mi>ψ</mi><mi>t</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow></mrow><mo>=</mo><msup><mi>g</mi><msub><mi>γ</mi><mi>j</mi></msub></msup></mrow><mo>)</mo></mrow></mrow><mo>}</mo></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mi>p</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>k</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mn>2</mn></mrow></msub></mrow><mo>⁢</mo><mi /><mo>=</mo><mrow><mi>PK</mi><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mo>(</mo><mi>δ</mi><mo>)</mo></mrow><mo>:</mo><msubsup><mrow><mo>(</mo><mrow><mrow><mrow><msub><mi>D</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msubsup><mi>ψ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow></mrow><mo>=</mo><msubsup><mi>g</mi><mi>u</mi><msup><mi>δ</mi><mi>j</mi></msup></msubsup></mrow><mo>,</mo></mrow><mo>)</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></mrow><mo>}</mo></mrow></mrow></mrow></mtd></mtr></mtable></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>41</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0296(4) The commitment open value open, expressed by the following formula 42 is output.

p-0297<maths id="MATH-US-00032" num="00032"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>open</mi><mi>u</mi></msub><mo>=</mo><mrow><mo>(</mo><mrow><msubsup><mrow><mo>{</mo><mrow><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>b</mi><mrow><mi>u</mi><mo>,</mo><mn>1</mn></mrow></msub></mrow><mo>}</mo></mrow><mrow><mn>1</mn><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>,</mo><msubsup><mrow><mo>{</mo><mrow><msubsup><mi>t</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mi>t</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow><mo>}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mn>42</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0298(5) The commitment com_uexpressed by the following formula 43 is output.

p-0299<maths id="MATH-US-00033" num="00033"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>com</mi><mi>u</mi></msub><mo>=</mo><mrow><mo>(</mo><mrow><msubsup><mrow><mo>{</mo><msub><mi>c</mi><mrow><mi>u</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>}</mo></mrow><mrow><mn>1</mn><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>⁢</mo><mrow><mo></mo><msubsup><mrow><mo>{</mo><msub><mi>d</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mn>43</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><ul><li id="ul0017-0001" num="0000"><ul><li id="ul0018-0001" num="0337">Commitment verifying algorithm V</li></ul></li></ul>

p-0300Input: the commitment com_v0of the network terminal <b>1200</b><i>v </i>

p-0301Output: the verification result {0, 1}

p-0302Processing:

p-0303<maths id="MATH-US-00034" num="00034"><math overflow="scroll"><mtable><mtr><mtd><msubsup><mrow><mo>{</mo><mrow><msub><mi>d</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>,</mo></mrow><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>44</mn></mrow><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mrow><mo>{</mo><mrow><mi>p</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>k</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mn>1</mn></mrow></msub></mrow><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mi>and</mi><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><msubsup><mrow><mo>{</mo><mrow><mi>p</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>k</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi><mo>,</mo><mn>2</mn></mrow></msub></mrow><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>45</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0304The certifications expressed by the formulas 45 included in the public information expressed by the formula 44 is verified, and if all the commitments com_vare accepted, the value of 1 is output, or otherwise, the value of 0 is output. <ul><li id="ul0019-0001" num="0000"><ul><li id="ul0020-0001" num="0343">Matching algorithm M</li></ul></li></ul>

p-0305Input: the commitment open value opens of the network terminal <b>1200</b><i>u </i>and the legal commitment com_v0of the network terminal <b>1200</b><i>v </i>

p-0306Output: the answering message ans_u,v0

p-0307Processing:

p-0308<maths id="MATH-US-00035" num="00035"><math overflow="scroll"><mtable><mtr><mtd><msubsup><mrow><mo>{</mo><mrow><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>b</mi><mrow><mi>u</mi><mo>,</mo><mn>1</mn></mrow></msub></mrow><mo>}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>46</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0309(1) A value expressed by the following formula 46 included in the commitment open value open_uis used to perform computations (a)-(d) expressed by the following formulas 47, where i=1, . . . , n.

p-0310<maths id="MATH-US-00036" num="00036"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><mrow><mo>(</mo><mi>a</mi><mo>)</mo></mrow><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><msubsup><mi>φ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow><mo>,</mo><mrow><mrow><msubsup><mi>φ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>are</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>computed</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>as</mi><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mrow><mi>follows</mi><mo>.</mo><mstyle><mtext /></mstyle><mo>⁢</mo><msubsup><mi>φ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></mrow><mo>=</mo><mrow><mrow><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>g</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow></mrow><mo>×</mo><mrow><munderover><mo>∏</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msup><mrow><mo>(</mo><msubsup><mi>ψ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><msub><mi>a</mi><mrow><mi>v</mi><mo>,</mo><mi>j</mi></mrow></msub></msup></mrow></mrow><mo>=</mo><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>g</mi><mrow><mi>u</mi><mo>,</mo><msup><mi>i</mi><mrow><msub><mi>f</mi><mi>u</mi></msub><mo>,</mo><mrow><mo>(</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow></mrow></msup></mrow></msub><mo>)</mo></mrow></mrow></mrow></mrow></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><msubsup><mi>φ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><mrow><munderover><mo>∏</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msup><mrow><mo>(</mo><msubsup><mi>ψ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><msub><mi>b</mi><mrow><mi>v</mi><mo>,</mo><mi>j</mi></mrow></msub></msup></mrow><mo>=</mo><mrow><msub><mi>E</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msub><mi>h</mi><mrow><mi>u</mi><mo>,</mo><msup><mi>i</mi><mrow><msub><mi>w</mi><mi>u</mi></msub><mo>,</mo><mrow><mo>(</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow></mrow></msup></mrow></msub><mo>)</mo></mrow></mrow></mrow></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><mrow><mrow><mo>(</mo><mi>b</mi><mo>)</mo></mrow><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><msubsup><mi>ξ</mi><mn>1</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow><mo>,</mo><msubsup><mi>ξ</mi><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><mrow><mrow><msubsup><mi>ξ</mi><mn>3</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><msub><mo>∈</mo><mi>R</mi></msub><mo>⁢</mo><mrow><mrow><msub><mi>Z</mi><mi>q</mi></msub><mo>⁢</mo><mstyle><mtext /></mstyle><mo>(</mo><mi>c</mi><mo>)</mo></mrow><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><msubsup><mi>μ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></mrow><mo>=</mo><mrow><mrow><mrow><msubsup><mi>φ</mi><mi>g</mi><mrow><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow><mo>⁢</mo><msubsup><mi>ξ</mi><mn>1</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></msubsup><mo>⁢</mo><mstyle><mtext /></mstyle><mo>(</mo><mi>d</mi><mo>)</mo></mrow><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><msup><mi>ρ</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup></mrow><mo>=</mo><mrow><mrow><mo>(</mo><mrow><msup><mi>v</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo>,</mo><msubsup><mi>μ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mi>λ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mi>λ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><msup><mi>s</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup></mrow><mo>)</mo></mrow><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>are</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>computed</mi></mrow></mrow></mrow></mrow><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><mrow><mi>using</mi><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mi>the</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>following</mi><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mrow><mi>formulas</mi><mo>.</mo><mstyle><mtext /></mstyle><mo>⁢</mo><msup><mi>v</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup></mrow></mrow><mo>=</mo><msup><mrow><mo>(</mo><msub><mi>h</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow><msubsup><mi>ξ</mi><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></msup></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><msubsup><mi>μ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><msup><mrow><mo>(</mo><mrow><msup><mrow><mo>(</mo><msub><mi>h</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow><msubsup><mi>ξ</mi><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></msup><mo>×</mo><msubsup><mi>φ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow><mo>)</mo></mrow><msubsup><mi>ξ</mi><mn>1</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></msup></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><msubsup><mi>λ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><msup><mrow><mo>(</mo><msubsup><mi>φ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><msubsup><mi>ξ</mi><mn>3</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></msup></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><msubsup><mi>λ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><msup><mrow><mo>(</mo><mrow><msup><mrow><mo>(</mo><msub><mi>h</mi><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>)</mo></mrow><msubsup><mi>ξ</mi><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></msup><mo>×</mo><msubsup><mi>φ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow><mo>)</mo></mrow><msubsup><mi>ξ</mi><mn>3</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></msup></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><msup><mi>ⅇ</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo>=</mo><mrow><mi>H</mi><mo>(</mo><mrow><mrow><msub><mi>com</mi><mi>u</mi></msub><mo>⁢</mo><mrow><mo></mo><msup><mi>v</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo></mo></mrow><mo>⁢</mo><msubsup><mi>μ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><mrow><mo></mo><msubsup><mi>μ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo></mo></mrow><mo>⁢</mo><msubsup><mi>λ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><mrow><mo></mo><msubsup><mi>λ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><msup><mi>s</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup></mrow><mo>=</mo><mrow><msubsup><mi>ξ</mi><mn>1</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>-</mo><mrow><msup><mi>ⅇ</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo>×</mo><msubsup><mi>ξ</mi><mn>3</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></mrow></mrow><mo>⁢</mo><mstyle><mtext /></mstyle></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mn>47</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0311(2) The answering message ans_u,vexpressed by the formula 48 is output.

p-0312<maths id="MATH-US-00037" num="00037"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>ans</mi><mrow><mi>u</mi><mo>,</mo><mi>v</mi></mrow></msub><mo>=</mo><msubsup><mrow><mo>{</mo><mrow><msubsup><mi>μ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><msup><mi>ρ</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup></mrow><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>48</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><ul><li id="ul0021-0001" num="0000"><ul><li id="ul0022-0001" num="0352">Result output algorithm D</li></ul></li></ul>

p-0313Input: the answering message ans_v,ufrom the network terminal <b>1200</b><i>v </i>to the network terminal <b>1200</b><i>u</i>, the legal commitment com, of the network terminal <b>1200</b><i>v</i>, and the list L_u, secret key K_uand commitment open value open_u0of the network terminal <b>1200</b><i>u </i>

p-0314Output: the common part {tilde over ( )}L_v,u(=L_v∩L_u) among the lists L_uand L_v, or error message

p-0315Processing: values shown by the formulas 49 are used as inputs.

p-0316The following processings are performed, where i=1, . . . , n.

p-0317<maths id="MATH-US-00038" num="00038"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msubsup><mrow><mo>{</mo><msub><mi>c</mi><mrow><mi>u</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>}</mo></mrow><mrow><mn>1</mn><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>included</mi><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><mi>in</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><msub><mi>com</mi><mi>u</mi></msub></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><msubsup><mrow><mo>{</mo><mrow><msubsup><mi>t</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mi>t</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow><mo>}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>included</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>in</mi><mo>⁢</mo><mstyle><mspace width="1.1em" height="1.1ex" /></mstyle><mo>⁢</mo><msub><mi>open</mi><mi>u</mi></msub></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><msub><mi>L</mi><mi>u</mi></msub><mo>=</mo><msubsup><mrow><mo>{</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>}</mo></mrow><mrow><mn>1</mn><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>49</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0318(1) Certification

p-0319In order to verify the certification expressed by the formula 50, the following formulas 51 are computed.

p-0320<maths id="MATH-US-00039" num="00039"><math overflow="scroll"><mtable><mtr><mtd><mrow><msup><mi>ρ</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo>=</mo><mrow><mo>(</mo><mrow><msup><mi>v</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo>,</mo><msubsup><mi>μ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mi>λ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mi>λ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><msup><mi>s</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>50</mn></mrow><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mrow><msup><mover><mi>ⅇ</mi><mo>~</mo></mover><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo>=</mo><mrow><mrow><mi>H</mi><mo>(</mo><mrow><msub><mi>com</mi><mi>u</mi></msub><mo>⁢</mo><mrow><mo></mo><msup><mi>v</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo></mo></mrow><mo>⁢</mo><msubsup><mi>μ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow><mo></mo></mrow><mo>⁢</mo><msubsup><mi>μ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><mrow><mo></mo><msubsup><mi>λ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo></mo></mrow><mo>⁢</mo><msubsup><mi>λ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></mrow><mo>)</mo></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><msubsup><mi>σ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><msub><mi>D</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msup><mrow><mo>(</mo><msubsup><mi>μ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><mrow><mn>1</mn><mo>/</mo><msubsup><mi>t</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></msup><mo>)</mo></mrow></mrow></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><msubsup><mi>σ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><msub><mi>D</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msup><mrow><mo>(</mo><msubsup><mi>μ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><mrow><mn>1</mn><mo>/</mo><msubsup><mi>t</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></msup><mo>)</mo></mrow></mrow></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><msubsup><mi>τ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><msub><mi>D</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msup><mrow><mo>(</mo><msubsup><mi>λ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><mrow><mn>1</mn><mo>/</mo><msubsup><mi>t</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></msup><mo>)</mo></mrow></mrow></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><msubsup><mi>τ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><msub><mi>D</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msup><mrow><mo>(</mo><msubsup><mi>λ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><mrow><mn>1</mn><mo>/</mo><msubsup><mi>t</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></msup><mo>)</mo></mrow></mrow></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><msup><mi>η</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo>=</mo><mrow><msup><mrow><mo>(</mo><msup><mi>v</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo>)</mo></mrow><mrow><mn>1</mn><mo>/</mo><msubsup><mi>t</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow></msup><mo>×</mo><mrow><munderover><mo>∏</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>C</mi><mrow><mi>v</mi><mo>,</mo><msup><mi>j</mi><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><msup><mi>j</mi><mi>j</mi></msup></mrow></msub></msup></mrow></msub></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>51</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0321(2) If the following formula 52 does not hold true, an error message is output and the processing is ended.

p-0322<maths id="MATH-US-00040" num="00040"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msubsup><mi>τ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><msubsup><mi>τ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow><mo>=</mo><mrow><msup><mrow><mo>(</mo><msup><mi>η</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup><mo>)</mo></mrow><msup><mi>s</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup></msup><mo>⁢</mo><msup><mrow><mo>(</mo><mrow><msubsup><mi>σ</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>⁢</mo><msubsup><mi>σ</mi><mi>h</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup></mrow><mo>)</mo></mrow><msup><mover><mi>ⅇ</mi><mo>~</mo></mover><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msup></msup></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>52</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0323(3) If σ_g^(u,v,i)is satisfied, α_u,iis output and the processing is ended. <ul><li id="ul0023-0001" num="0000"><ul><li id="ul0024-0001" num="0364">Exception processing request generation algorithm P</li></ul></li></ul>

p-0324Input: the legal commitment com_vof the network terminal <b>1200</b><i>v </i>and the list L_u0of the network terminal <b>1200</b><i>u </i>

p-0325Output: the exception processing request message ereq_v,u0

p-0326Processing:

p-0327(1) Using φ_t^(u,i)included in the commitment com_vand the list L_u, the following formulas 53 are computed, where i=1, . . . , n.

p-0328<maths id="MATH-US-00041" num="00041"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msup><mi>Z</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msup><mo>⁢</mo><msub><mo>∈</mo><mi>R</mi></msub><mo>⁢</mo><msub><mi>Z</mi><mi>q</mi></msub></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><msubsup><mi>κ</mi><mn>1</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><mrow><mo>(</mo><msubsup><mi>ψ</mi><mi>t</mi><mrow><mo>(</mo><mrow><mi>v</mi><mo>,</mo><mi>i</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><mo>×</mo><msup><mi>g</mi><mrow><mo>-</mo><msub><mi>a</mi><mrow><mi>u</mi><mo>,</mo><mi>j</mi></mrow></msub></mrow></msup><mo>⁢</mo><msubsup><mi>y</mi><mi>u</mi><msup><mi>z</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msup></msubsup></mrow></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><msubsup><mi>κ</mi><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><msup><mi>g</mi><msup><mi>z</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msup></msup></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>53</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0329(2) The exception processing request message ereq_v,uexpressed by the formula 54 is output.

p-0330<maths id="MATH-US-00042" num="00042"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>ereq</mi><mrow><mi>v</mi><mo>,</mo><mi>u</mi></mrow></msub><mo>=</mo><msub><mrow><mo>{</mo><mrow><msubsup><mi>κ</mi><mn>1</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mi>κ</mi><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup></mrow><mo>}</mo></mrow><mrow><mi>i</mi><mo>,</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mo>,</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>,</mo><mi>n</mi></mrow></msub></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>54</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><ul><li id="ul0025-0001" num="0000"><ul><li id="ul0026-0001" num="0372">Exception processing algorithm T</li></ul></li></ul>

p-0331Input: the exception processing request message ereq_v,uand the secret key K_T0of the TTP server <b>1210</b>

p-0332Output: the exception processing answering message eans_v,uor error message

p-0333Processing: it is confirmed that a fault (exception) occurs in the information exchange between the network terminals <b>1200</b><i>u </i>and <b>1200</b><i>v </i>according to a predetermined procedure described later. If the confirmation fails, the error message is output and returned to the network terminal <b>1200</b><i>u</i>, and the processing is ended. If the confirmation succeeds, using a decryption function D_yTusing the secret key K_T, the following processings are performed.

p-0334(1) The following formulas 55 are computed, where i, j=1, . . . , n.

p-0335<maths id="MATH-US-00043" num="00043"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msup><mover><mi>Z</mi><mo>~</mo></mover><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msup><mo>⁢</mo><msub><mo>∈</mo><mi>R</mi></msub><mo>⁢</mo><msub><mi>Z</mi><mi>q</mi></msub></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><msubsup><mover><mi>κ</mi><mo>~</mo></mover><mn>1</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><msup><mrow><mo>(</mo><mrow><msub><mi>D</mi><msub><mi>y</mi><mi>T</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><msubsup><mi>κ</mi><mn>1</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow></mrow><mo>)</mo></mrow><msup><mover><mi>z</mi><mo>~</mo></mover><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msup></msup></mrow><mo>⁢</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><msubsup><mover><mi>κ</mi><mo>~</mo></mover><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><msup><mrow><mo>(</mo><msubsup><mi>κ</mi><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>)</mo></mrow><msup><mover><mi>z</mi><mo>~</mo></mover><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msup></msup></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>55</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0336(2) The exception processing answering message eans_v,uexpressed by the formula 56 is output.

p-0337<maths id="MATH-US-00044" num="00044"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>ereq</mi><mrow><mi>v</mi><mo>,</mo><mi>u</mi></mrow></msub><mo>=</mo><msub><mrow><mo>{</mo><mrow><msubsup><mover><mi>κ</mi><mo>~</mo></mover><mn>1</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mover><mi>κ</mi><mo>~</mo></mover><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup></mrow><mo>}</mo></mrow><mrow><mi>i</mi><mo>,</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mo>,</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>,</mo><mi>n</mi></mrow></msub></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>56</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><ul><li id="ul0027-0001" num="0000"><ul><li id="ul0028-0001" num="0380">Exception processing result generation algorithm W</li></ul></li></ul>

p-0338Input: the exception processing answering message eans_v,uand the secrete key K_u0of the network terminal <b>1200</b><i>u </i>

p-0339Output: the common part {tilde over ( )}L_v,u(=L_v∩L_u) among the lists L_uand L_v

p-0340Processing: the following processings are performed, where i, j=1, . . . , n.

p-0341(1) A value of α_t^(u,v,i,j)is computed using the following formula 57.

p-0342<maths id="MATH-US-00045" num="00045"><math overflow="scroll"><mtable><mtr><mtd><mrow><msubsup><mi>σ</mi><mi>t</mi><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><msub><mi>D</mi><msub><mi>y</mi><mi>u</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><msubsup><mover><mi>κ</mi><mo>~</mo></mover><mn>2</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup><mo>,</mo><msubsup><mover><mi>κ</mi><mo>~</mo></mover><mn>1</mn><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mo>)</mo></mrow></msubsup></mrow><mo>)</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Formula</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mn>57</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

p-0343(2) If α_L^(u,v,i,j)=1, α_u,iis output.

p-0344Now, a verification method for the TTP server <b>1210</b> to confirm that a fault (exception) actually occurs in the information exchange between the network terminals <b>1200</b><i>u </i>and <b>1200</b><i>v </i>will be described.

p-0345To execute the exception processing algorithm, the TTP server <b>1210</b> has to confirm that a fault (exception) occurs in the information exchange between the network terminals <b>1200</b><i>u </i>and <b>1200</b><i>v</i>. If the matching result output unit <b>1204</b> outputs the error message, the TTP server <b>1210</b> can confirm the occurrence of the exception by verifying also the certification therefor. Further, in the computation of the common part to the lists of the network terminals <b>1200</b><i>u </i>and <b>1200</b><i>v</i>, for example, an exception may occur due to the fact that the network terminal <b>1200</b><i>v </i>transmits no answering message to the network terminal <b>1200</b><i>u</i>, although the network terminal <b>1200</b><i>u </i>transmits the answering message to the network terminal <b>1200</b><i>v</i>. In such a case, even if the error message is not output, the exception has to be addressed. However, it is quite difficult for the TTP server <b>1210</b> to distinguish the following two cases from each other. <ul><li id="ul0029-0001" num="0000"><ul><li id="ul0030-0001" num="0389">A case where the network terminal <b>1200</b><i>v </i>truly does not transmit the answering message to the network terminal <b>1200</b><i>u. </i></li><li id="ul0030-0002" num="0390">A case where although any information exchange does not actually occur between the network terminals <b>1200</b><i>u </i>and <b>1200</b><i>v</i>, the network terminal <b>1200</b><i>u </i>claims that the exception occurs, and illegally tries to know the common part with the list held by the network terminal <b>1200</b><i>v. </i></li></ul></li></ul>

p-0346Generally, these cases can be distinguished from each other by using a transaction certificate with a time limit by combining encryption means and non-encryption means with each other. The “time limit” used herein means to add a policy restriction to the transaction certificate in that:

p-0347(1) before the “time limit”, the TTP server accepts no exception request under circumferences where any of the network terminals provides a transaction stop certificate; and

p-0348(2) after the “time limit”, the TTP server <b>1210</b> accepts the exception request and solves the problem when any of the network terminals provides the transaction certificate.

p-0349<figref idrefs="DRAWINGS">FIG. 16</figref> is a diagram for illustrating the method for verifying an occurrence of an exception using the transaction certificate with a time limit.

p-0350Referring to <figref idrefs="DRAWINGS">FIG. 16</figref>, the verification method is implemented in the following procedure. Here, numbers in the drawing correspond to the numbers in the procedure.

p-03511. The network terminal <b>1200</b><i>u </i>confirms the correctness of the commitment com_vof the network terminal <b>1200</b><i>v. </i>

p-03522. The network terminal <b>1200</b><i>u </i>transmits a transaction certificate with a time limit Cert_u,v(period) to the network terminal <b>1200</b><i>v. </i>

p-03533. The network terminal <b>1200</b><i>v </i>transmits a transaction stop certificate Stop_v,uto the TTP server <b>1210</b> in any of cases where: <ul><li id="ul0031-0001" num="0000"><ul><li id="ul0032-0001" num="0399">the transaction certificate with a time limit Cert_u,v(period) is an illegal one;</li><li id="ul0032-0002" num="0400">the transaction certificate with a time limit Cert_u,v(period) cannot be transmitted within the time limit; and</li><li id="ul0032-0003" num="0401">the correctness of the commitment com_vof the network terminal <b>1200</b><i>v </i>cannot be confirmed.</li></ul></li></ul>

p-03544. The network terminal <b>1200</b><i>v </i>transmits a transaction certificate with a time limit Cert_v,u(period) to the network terminal <b>1200</b><i>v. </i>

p-03555. The network terminal <b>1200</b><i>u </i>transmits a transaction stop certificate Stop_u,vto the TTP server <b>1210</b> if the transaction certificate with a time limit Cert_v,u(period) is an illegal one or cannot be received within the time limit.

p-03566. The network terminal <b>1200</b><i>u </i>transmits an answer ans_u,vto the network terminal <b>1200</b><i>v </i>after the time limit.

p-03577. The network terminal <b>1200</b><i>v </i>transmits an answer ans_v,uto the network terminal <b>1200</b><i>u </i>after the time limit.

p-03588. If the network terminal <b>1200</b><i>u </i>cannot receive the answer ans_v,u, the network terminal <b>1200</b><i>u </i>transmits the transaction certificate with a time limit Cert_v,u(period) to the TTP server <b>1210</b> to request the server to address the exception.

p-03599. If the network terminal <b>1200</b><i>v </i>cannot receive the answer ans_u,v, the network terminal <b>1200</b><i>v </i>transmits the transaction certificate with a time limit Cert_u,v(period) to the TTP server <b>1210</b> to request the same to address the exception.

p-0360In this way, in response to the exception processing request from the network terminals <b>1200</b><i>u</i>, <b>1200</b><i>v</i>, the TTP server <b>1210</b> can perform the exception processing through the exception processing execution unit <b>1211</b> after confirming that a fault (exception) occurs in the information exchange between the network terminals <b>1200</b><i>u </i>and <b>1200</b><i>v. </i>

p-0361This embodiment is based on the least assumption of confidence to the TTP server <b>1210</b>. If the TTP server is not allowed to access the commitments of the network terminals, it cannot get any information associated with the lists even when performing the exception processing. However, if the TTP server is operated by a single network terminal <b>1200</b>, there remains a potential risk of illegal access to a secret held in each network terminal <b>1200</b> through illegal determination of the exception occurrence or illegal acquirement of the commitment. To address such a risk, as in the case of the secret distribution in the second embodiment, the TTP server <b>1210</b> may be split into a plurality of servers to have a threshold access structure, in which the exception processing can be performed only when the TTP servers <b>1210</b> having a value equal to or higher than a threshold cooperate with each other, thereby dramatically enhancing the confidence to the TTP server <b>1210</b>.

p-0362According to this embodiment, the TTP server <b>1210</b> essentially serves to:

p-0363(1) confirm the occurrence of the exception; and

p-0364(2) operate the secret key for the ElGamal encryption.

p-0365It is known that these functions can be readily distributed in the threshold access structure using a well-known prior art. Thus, secure operation of the TTP server <b>1210</b> according to this embodiment can be readily realized.

p-0366In this way, the system according to this embodiment satisfies the following requirements in performing matching of items of lists held by a plurality of network terminals <b>1200</b>. In the following description, reference symbol C denotes the commitment generation algorithm, reference symbol V denotes the commitment verification algorithm, reference symbol M denotes the matching algorithm, reference symbol D denotes the result output algorithm, reference symbol P denotes the exception processing request generation algorithm, reference symbol T denotes the exception processing algorithm and reference symbol W denotes the exception processing result generation algorithm.

p-03671. Confidentiality of Commitment

p-0368The value of the commitment, which is open information, provides no information on the list. That is, with respect to the lists L_uand L_vand the commitments com_uand com_v, if conditions of L_u≠L_v, com_u←C(L_u) and com_v←C(L_v) are satisfied, it is impossible to determine which of the lists L_uand Lv corresponds to any given one of the commitments com_uand com, with a probability higher than 50%.

p-03692. Verifiability of Commitment

p-0370It can be verified that the common part can be obtained by generating the commitment come by the commitment generation algorithm C and performing the exception processing using the commitment come as the input.

p-03713. Confidentiality of Answering Message

p-0372When conditions of V(com_u)=1, open_v←C(L_v) and ans_v,u=M(open_v,com_u) are satisfied, the network terminal <b>1200</b><i>u </i>cannot get any information on the list Lv from the answering message ans_v,u, except for the information that {tilde over ( )}L_v,uis the common part.

p-03734. Verifiability of Answering Message

p-0374It can be verified that the common part obtained from the answering message is the common part with the list corresponding to the commitment of the partner. That is, when conditions of V(com_v)=1 and open_u←C(L_u) are satisfied, the result res_v,u=D(ans_v,u, com_v, L_u, K_u, open_u) for the answering message ans_v,uis the common part {tilde over ( )}L_v,uamong the lists L_uand L_v, if it is not an error message.

p-03755. Exception Processing by Arbitration Organization

p-0376With respect to the commitment com, satisfying a condition of V(com_v)=1, assuming that the exception processing request message ereq_v,u=P(com_v, L_u), the exception request answering message eans_v,u=T(ereq_v,u, K_T) and the exception processing result eres_v,u=W(eans_v,u, K_u), the exception processing result eres_v,uis the common part {tilde over ( )}L_v,uamong the lists L_uand L_v. Only the exception processing algorithm T uses the secret key K_Tof the TTP server <b>1210</b> as the input (that is, the TTP server <b>1210</b> is involved only in the exception processing and is not used in the normal process).

p-03776. Efficiency

p-0378Communication is established from the network terminal <b>1200</b><i>u </i>to the network terminal <b>1200</b><i>v </i>once in the commitment phase, and once in the normal process. In addition, the TTP server <b>1210</b> is involved only in the exception processing and is not used in the normal process.

p-0379Now, applications of the network system for providing various services will be described.

p-0380(1) Match Making Service

p-0381In the past, generally, when one uses the Internet to search for another having the same interest as himself/herself, he/she has opened information about his/her interest on a webpage and waited for a response from an unspecific one, or passed the information to an agent server for intermediation.

p-0382However, according to the former method, private information has to be opened. According to the latter method, privacy protection has to be entrusted to the agent server, and there has been a risk of leaking information about participants if the security of the agent server is broken.

p-0383Using the network system according to the first embodiment as it is can provide a match making service with high security. That is, if the match making server <b>400</b> shown in <figref idrefs="DRAWINGS">FIG. 4</figref> is used as the agent server, the agent server can compute only the common items among information (lists) of participants without getting information of the individual participants. In addition, the agent server can also serve to inform the participants of only the number of common items, rather than to make a list of the common items.

p-0384Besides, using the network system according to the second embodiment as it is can provide a highly secure system without the agent server, in which only the participants can know the common items among the lists thereof.

p-0385Further, using the network system according to the third embodiment can provide a highly secure, efficient and highly practical system, in which, in the normal process, the participants can know the common items among the information (lists) of the participants only through information exchange therebetween.

p-0386<figref idrefs="DRAWINGS">FIG. 17</figref> schematically shows the match making service using the network system. Referring to this drawing, a list of a participant A containing “classical music”, “drive”, “ski” and “tennis” and a list of a participant B containing “classical music”, “diving”, “flower arrangement”, “tea ceremony” and “tennis” are subject to match making, and the common items of “classical music” and “tennis” are extracted. Therefore, it is proved that both the participants A and B have interests in these common items.

p-0387Furthermore, such a network system may be implemented by an application of a cellular phone with a radio broadcasting function such as Bluetooth. In such a case, the following service can be provided. That is, if users have previously registered information including their interests with their respective cellular phones, when users having the same interest (having registered the same items) come within a certain distance of each other, their respective cellular phones start to communicate with each other.

p-0388As a modification of the match making service, the list matching may be performed by specifying information of a partner to be searched for. In this case, each of the participants prepares two lists, that is, a list of the information about himself/herself (self-list, hereinafter) and a list of the information of the partner to be searched for (partner-list, hereinafter), and performs list matching on the partner-list held by himself/herself and the self-lists held by the others. Similarly, each participant performs list matching on the partner-lists held by the others and the self-list held by himself/herself.

p-0389As such an intermediation service, for example, such a service is also possible that the participants A and B each prepares two lists of the profile of himself/herself and the profile of the partner to be searched for, and a correspondence of the profile between one participant and the other is computed by performing two list common part computations on the self-profile of the participant A and the partner-profile of the participant B and on the partner-profile of the participant A and the self-profile of the participant B, thereby providing the correspondence as information about the affinity between the participants A and B.

p-0390Alternatively, the participant A may prepare one list describing the profile items of himself/herself as they are and the profile items of the partner as negative roots provided by multiplying them by −1. And, the participant B may prepare one list describing the profile items of himself/herself as negative roots provided by multiplying them by −1 and the profile items of the partner as they are. Thus, each participant can represent the self-list and the partner-list by one list. By using this list, the information about the affinity between the participants A and B can be obtained through one list common part computation.

p-0391(2) List Inquiry

p-0392Financial institutes, such as banks and credit companies, make a profit by providing financing for customers. Therefore, credit information about the customers is quite essential for administration. In particular, the list of persons in arrears is essential to estimate the risk of providing financing. On the other hand, many of the customers obtain financing from a plurality of financial institutes. Thus, for credit examination or the like, it may be desired to compare the lists of customers in arrears (referred to as black lists) among the plurality of financial institutes. In other words, by sharing the information on the arrears among the financial institutes, the credit information about the customers can be created more accurately.

p-0393However, the list of persons in arrears is an essential company secret for the financial institutes. Thus, to ensure the privacy of the customers and the confidence to the financial institutes, it is necessary to search for only the customers registered with the lists of a plurality of financial institutes, without disclosing the list of persons in arrears.

p-0394In this case, if the list inquiry is performed by using the network system according to the first, second or third embodiment, only the information about the common part among the lists (customers listed in the lists of the financial institutes to be investigated) can be extracted and exchanged evenly among the financial institutes.

p-0395(3) Data Integration of Human Resource Data Bank

p-0396Human resource data banks have information (list) about skills, desired jobs or the like of registrants as a company secret, and companies ready for adoption have a list of skills, job descriptions or the like required for prospective employees. Effective provision or acquirement of human resources can be realized by extracting the common part among the lists. However, the information about the human resources the companies wish to acquire includes information about their respective essential strategies. Thus, it is undesirable that information in the list except for the common part is known to the other companies.

p-0397In this case, if the list inquiry is performed by using the network system according to the first, second or third embodiment, the common part (information) to the demander and supplier of the human resource can be extracted while keeping the human resource data itself in secret.

p-0398(4) Matching Database of Commodity Price in Electronic Commerce Market

p-0399In the electronic commerce market, a commodity price is established by maintaining the demand and supply balance between a seller and a buyer. In this case, both the seller and the buyer have their respective lists of commodity numbers and desired prices, and a price satisfying the wishes of the seller and buyer can be established by extracting the common part to the lists. The intended prices of commodities are important secret information both for the seller and the buyer. Therefore, it is advantageous that, from the lists of the desired prices, only the information about the commodities for which the desired prices of the seller and buyer agree with each other.

p-0400In this case, if the list inquiry is performed by using the network system according to the first, second or third embodiment, the seller and the buyer can investigate which commodity prices agree with each other, while keeping their respective desired commodities and prices thereof in secret.

p-0401As described above, according to this invention, the security in the information exchange can be ensured, and list matching with higher efficiency and practicality can be provided. In addition, according to this invention, by using the distributed secret computation, a secure method for peer-to-peer list matching can be provided.

p-0402The present invention can be realized in hardware, software, or a combination of hardware and software. A visualization tool according to the present invention can be realized in a centralized fashion in one computer system, or in a distributed fashion where different elements are spread across several interconnected computer systems. Any kind of computer system—or other apparatus adapted for carrying out the methods and/or functions described herein—is suitable. A typical combination of hardware and software could be a general purpose computer system with a computer program that, when being loaded and executed, controls the computer system such that it carries out the methods described herein. The present invention can also be embedded in a computer program product, which comprises all the features enabling the implementation of the methods described herein, and which—when loaded in a computer system—is able to carry out these methods.

p-0403Computer program means or computer program in the present context include any expression, in any language, code or notation, of a set of instructions intended to cause a system having an information processing capability to perform a particular function either directly or after conversion to another language, code or notation, and/or reproduction in a different material form.

p-0404Thus the invention includes an article of manufacture which comprises a computer usable medium having computer readable program code means embodied therein for causing a function described above. The computer readable program code means in the article of manufacture comprises computer readable program code means for causing a computer to effect the steps of a method of this invention. Similarly, the present invention may be implemented as a computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a function described above. The computer readable program code means in the computer program product comprising computer readable program code means for causing a computer to effect one or more functions of this invention. Furthermore, the present invention may be implemented as a program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for causing one or more functions of this invention.

p-0405It is noted that the foregoing has outlined some of the more pertinent objects and embodiments of the present invention. This invention may be used for many applications. Thus, although the description is made for particular arrangements and methods, the intent and concept of the invention is suitable and applicable to other arrangements and applications. It will be clear to those skilled in the art that modifications to the disclosed embodiments can be effected without departing from the spirit and scope of the invention. The described embodiments ought to be construed to be merely illustrative of some of the more prominent features and applications of the invention. Other beneficial results can be realized by applying the disclosed invention in a different manner or modifying the invention in ways known to those familiar with the art.