JP4199753B2 - On-demand search method, on-demand search system and terminal - Google Patents

Description

  The present invention can obtain the content associated with the selected keyword without the information provider holding the plurality of contents corresponding to the plurality of keywords being made aware of the keyword arbitrarily selected by the user. The present invention relates to an on-demand search method and system.

  In recent years, on-demand search systems via the Internet have been realized one after another. The on-demand search system is a system in which information associated with a keyword is provided from a providing terminal when a keyword is input from a use terminal.

  The on-demand search system requires privacy guarantee such as concealing a keyword (for example, purchase information) input by a user in order to use the open Internet. Therefore, the Oblivious Keyword Search (hereinafter referred to as “OKS”) has been proposed as a technique for dealing with the guarantee of privacy.

OKS is a following two-party protocol performed between an information provider and a user. The information provider associates information (here, n contents) with each keyword, and manages the information by encrypting it. The information provider gives n keywords w _i (i: 1,..., N) to the user. The user selects an arbitrary keyword w ^* from n keywords w _i (i: 1,..., N) given by the information provider, and the keyword w ^* is known to the information provider. The data is sent to the information provider as question data. The information provider adds the processing using the encryption key used to encrypt the content to the question data including the keyword w ^* from the user so that the encryption key used by the user is not known, and as response data Send back. The response data sent back from the information provider to the user includes the keyword w ^* selected by the user himself and the encryption key used for encrypting the content. Therefore, the user can correctly decrypt only the content associated with the selected keyword w ^* by processing the encrypted content managed by the information provider using the received response data. it can.

As described above, in OKS, the user can obtain information associated with the keyword w ^* without knowing the selected keyword w ^* by the information provider. Further, the user cannot obtain information associated with other keywords other than the arbitrary keyword w ^* selected by the user.

  As a conventional OKS system, there is OKS based on the RSA blind signature system by Ogata and Kurosawa (see Non-Patent Document 1).

  Hereinafter, OKS based on the RSA blind signature scheme will be described in detail.

step1.
Assume that on the information provider side, keywords w _i (i: 1,..., N) and contents c _i corresponding thereto are stored in the database in advance.

First, the information provider generates a public key (N, e) and a secret key (d) for an RSA signature, calculates K _{i according} to the following equation for i = 1 to n, and further calculates E _i .

K _i = H (w _i ) ^d mod N
E _i = G (w _i ‖K _i ‖i) XOR (0 ^l ‖c _i )
Here, H () is a cryptographically secure hash function (such as SHA1), G () is a pseudo random number generator, ‖ is a combination of bit strings, XOR is an exclusive OR of bit strings, and 0 ^l is a continuous l (L) A number of “0” bit strings.

The information provider distributes (N, e, E ₁ ,..., E _n ), which is a set of the public key and the obtained E _i , to the users.

step2.
The user will want to search for _(one of the w 1 ~w _n) keyword ^w *. The user selects a random number r,
Y = r ^e · H (w ^* ) mod N
And Y obtained is sent to the information provider.

step3.
The information provider receives Y from the user, uses the RSA signature private key d,
K ′ = Y ^d mod N
And the obtained K ′ is sent to the user.

step4.
The user receives K ′ from the information provider and uses the random number r,
K = K '/ r mod N
Calculate Then the user can do everything from i = 1 to n.
a _i ‖b _i = E _i XOR G (w _i ‖K‖i)
Calculate Here, a _i is the first l bit and b _i is the remaining character string.

step5.
when it is a _i = ^{0 l,} that is from the beginning "0" when the bit is l (el) pieces continuous, regarded as keyword _{w i} matches the ^{w *.} In this case, the content _{c i} corresponding to the keyword ^{w *,} obtained as _{b i.}

As described above, since the user can obtain the information associated with the keyword w ^* without the information provider knowing the arbitrary keyword w ^* selected by the user, the privacy of the user is guaranteed. Further, since the user can only obtain information associated with an arbitrary keyword w ^* selected by himself / herself, the profit of the information provider is guaranteed.

Waka Ogata, Satoshi Kurosawa, “Oblivious keyword search”, Journal of Complexity, 2004, vol. 20, pp. 356-371)

  In a conventional on-demand search system, a method for protecting the privacy of a user is based on the RSA signature method, and considering the security of the RSA signature method, it is necessary to set the key length size to 1024 bits or more. As a result, the amount of communication between the information provider and the user increases, which is difficult in terms of efficiency.

  Therefore, the present invention provides an on-demand search system that can reduce the amount of data exchanged between the information provider and the user by OKS, and can verify whether the information provider is correctly performing according to the procedure. The purpose is to do.

  According to the present invention, a providing terminal for providing encrypted content by encrypting content corresponding to a keyword stored in a database on a one-to-one basis, and a use terminal for decrypting and using the encrypted content, On-demand search method using an on-demand search system connected via a network, wherein the providing terminal generates a first random number, and the providing terminal uses the first random number Generating public information, the providing terminal, a keyword stored in the database, content corresponding to the keyword on a one-to-one basis, the first random number, a first hash function, a first Generating the encrypted content using a second hash function, and the providing terminal comprising the public information, the encrypted content, Are recorded on a recording medium, the recording medium is distributed to a user terminal, the user terminal generates a second random number, the user terminal receives the second random number, and Abel Using a group generator and the first hash function, converting an arbitrarily selected keyword into a form not known to the providing terminal to generate a keyword search input, and the using terminal, Transmitting the keyword search input to the providing terminal via a network; receiving the keyword search input by the providing terminal; and providing the keyword search input; and the first random number; And generating the first keyword search output using the network, and the providing terminal outputs the first keyword search output via the network. Transmitting to the terminal; receiving the first keyword search output; using the public information recorded on the recording medium; the keyword search input; and the abel Verifying the validity of the first keyword search output using a group generator and a verification formula using the nature of the pairing operation, and the use terminal is considered valid Generating a second keyword search output using the first keyword search output, the public information, and the second random number; and the user terminal, the second keyword search output, Using the encrypted content recorded on the recording medium, the second hash function, and the arbitrarily selected keyword, the arbitrarily selected keyword is 1: 1. And obtaining a corresponding content with the on-demand search method.

  In addition, according to the present invention, a providing terminal that provides encrypted content by encrypting content corresponding to a keyword stored in a database on a one-to-one basis, and use for decrypting and using the encrypted content An on-demand search system in which a terminal is connected via a network, wherein the providing terminal generates first random number generation means for generating a first random number and public information using the first random number Using public information generating means, a keyword stored in the database, content corresponding to the keyword on a one-to-one basis, the first random number, a first hash function, and a second hash function In order to distribute the content encryption means for generating the encrypted content, the public information, and the encrypted content to the user terminal, Recording medium writing means for recording, keyword search input receiving means for receiving a keyword search input transmitted from the user terminal via the network, the keyword search input, and the first random number, First keyword search output generation means for generating one keyword search output, and first keyword search output transmission means for transmitting the first keyword search output to the user terminal via a network, The user terminal uses the second random number generation means for generating the second random number, the second random number, the generation source of the abelian group, and the keyword selected arbitrarily using the first hash function. A keyword search input generation means for generating the keyword search input by converting the information into a form that is not known to the providing terminal; A keyword search input transmitting means for transmitting to the providing terminal via a network; a first keyword search output receiving means for receiving the first keyword search output transmitted from the providing terminal via the network; Validity of the first keyword search output using the public information recorded on the recording medium, the keyword search input, the generation source of the abelian group, and a verification formula using the nature of the pairing operation Using the first keyword search output validity verification means for verifying, the first keyword search output deemed valid, the public information, and the second random number, Second keyword search output generation means for generating a search output, the second keyword search output, and the encrypted content recorded on the recording medium And content decrypting means for obtaining content corresponding to the arbitrarily selected keyword on a one-to-one basis using the second hash function and the arbitrarily selected keyword. An on-demand search system is obtained.

  Further, according to the present invention, the encrypted content obtained by encrypting the content corresponding to the keyword stored in the database on a one-to-one basis and the public information are provided, and the keyword search input received via the network is the first. A second random number generating means for generating a second random number in a user terminal used for an on-demand search system including a providing terminal that converts and generates a first keyword search output by Using the second random number, the abel group generator, and the first hash function, the keyword search input is generated by converting an arbitrarily selected keyword into a form not known to the providing terminal. Keyword search input generation means and keyword search input transmission for transmitting the keyword search input to the providing terminal via the network A first keyword search output receiving means for receiving the first keyword search output transmitted from the providing terminal via the network, the public information, the keyword search input, and the abelian group. First keyword search output validity verification means for verifying the validity of the first keyword search output using a generation source and a verification expression using the nature of the pairing operation is regarded as valid. A second keyword search output generating means for generating a second keyword search output using the first keyword search output, the public information, and the second random number; and the second keyword search. Using the output, the encrypted content, the second hash function, and the arbitrarily selected keyword, one-to-one correspondence with the arbitrarily selected keyword A content decryption means for obtaining the content that, the user terminal characterized in that it comprises the obtained.

  According to the present invention, by applying a method based on the discrete logarithm problem on an elliptic curve in which the key length size can be set at about 160 bits, the amount of communication can be reduced to 1/3 compared with the conventional method, and the efficiency side Improved.

  Further, according to the present invention, by verifying the data exchanged by the OKS between the information provider and the user by means of Bayeux pairing or Tate pairing, the user can correctly follow the procedure in the information provider. It is possible to verify that processing is being performed, and to prevent fraud of information providers.

  Hereinafter, an embodiment of the present invention will be described in detail with reference to the drawings.

  FIG. 1 shows a schematic configuration of an on-demand search system according to an embodiment of the present invention. The illustrated system includes a providing terminal (provider terminal) 20 and a use terminal (user terminal) 30 that are connected to each other via a network (here, the Internet) 10. In addition, a database 40 is connected to the providing terminal 20.

  The providing terminal 20 encrypts some or all of the keywords and contents registered in the database, and provides them to the use terminal 30. Here, it is assumed that the keyword and the content correspond one-to-one. The encrypted keyword and content are provided to the use terminal 30 by an arbitrary recording medium (for example, CD-ROM or DVD).

  The use terminal 30 converts the arbitrarily selected keyword into a form not known to the providing terminal 20 by the one-way function, and sends the converted keyword to the providing terminal 20 via the network 10. In addition, the providing terminal 20 converts the data including the keyword from the use terminal 30 into a form that is not known to the use terminal 30 by a one-way function using the encryption key used for encrypting the content. To the user terminal 30 via Here, a method based on a discrete logarithm problem on an elliptic curve having a relatively small key length size is applied to the transmission / reception of data between the use terminal 30 and the providing terminal 20 to reduce the communication amount.

  The user terminal 30 that has received the data from the providing terminal 20 receives a pair of multiplicative multiplicative groups with respect to two points P and Q defined on the elliptic curve, such as Weil pairing or Tate. Using the pairing (Tate pairing) e (P, Q), it is verified whether the processing in the information provision 30 is correctly performed according to the procedure.

  Hereinafter, the present embodiment will be further described with reference to FIGS.

  In order to realize the OKS based on the discrete logarithm problem on the elliptic curve, first, an efficient OKS based on the discrete logarithm problem on the finite field will be described with reference to FIG.

(1) OKS based on discrete logarithm problem over finite field
step1.
An abelian group (commutative group) whose order is a prime number q is G, and a generation source of the group G is g. Also, let H ₀ () and H ₁ () be random hash functions.

In the database 40, it is assumed that n keywords w _i (i: 1,..., N) and content c _i corresponding to the keywords one by one are stored in the database in advance.

step2.
The providing terminal 20 (information provider) selects the random number s,
y = ^{g s}
Calculate In addition, the providing terminal 20 performs the following for all i = 1 to n.
K _i = H ₀ (w _i ) ^s
E _i = H ₁ (w _i ‖K _i ‖i) XOR (0 ^l ‖c _i )
Calculate Here, ‖ is a combination of bit strings, XOR is an exclusive OR of bit strings, and 0 ^l is l (0) consecutive “0” bits.

The providing terminal 20 records the obtained y and E _i as distribution data (y, E ₁ ,..., E _n ) on a recording medium such as a CD-ROM or DVD. The information provider who uses the providing terminal 20 distributes the recording medium to the users.
User to use the user terminal 30 and you would like to search for any of w ^* of the keyword w ₁ ~w _n. The user terminal 30 selects a random number r,
Y = g ^r H ₀ (w ^* )
And Y obtained is sent to the providing terminal 20 via the Internet 10.

step4.
When the providing terminal 20 receives Y from the use terminal 30, it uses the random number s,
K ′ = Y ^s
And the obtained K ′ is sent to the user terminal 30 via the Internet 10.

step5.
When the usage terminal 30 receives K ′ from the providing terminal 20, K = K ′ / y ^r using the random numbers r and y.
Calculate Furthermore, the use terminal 30 is configured for all of i = 1 to n.
a _i ‖b _i = E _i XOR H ₁ (w _i ‖K‖i)
Calculate Here, a _i is the first l (el) bit, and b _i is the remaining character string.

step6.
When a _i = 0 ^l, that is, when the first consecutive l bits are all “0”, it is considered that the keyword w _i matches w ^* . At this time, the corresponding content c _i is obtained as b _i .

  Next, an example in which the information provider's fraud is extended to OKS will be described with reference to FIG.

(2) OKS that can detect fraudulent information providers
step1.
An abelian group (commutative group) whose order is a prime number q defined on the elliptic curve is G, and a generation source of the group G is P. Also, let H ₀ () and H ₁ () be random hash functions.

In the database 40, it is assumed that n keywords w _i (i: 1,..., N) and content c _i corresponding to the keywords one by one are stored in the database in advance.

step2.
The providing terminal 20 (information provider) selects the random number s,
Public information Y = sP
Calculate In addition, the providing terminal 20 performs the following for all i = 1 to n.
Encryption key Ki = sH ₀ (wi)
Encrypted content Ei = H ₁ (wi‖Ki‖i) XOR (0 ^l ‖ci)
Calculate Here, ‖ is a combination of bit strings, XOR is an exclusive OR of bit strings, and 0 ^l is l (0) consecutive “0” bits.

Providing terminal 20 records the obtained Y and _{E i} to a recording medium such as a CD-ROM or DVD. The information provider who uses the providing terminal 20 distributes (Y, E ₁ ,..., E _n ) by distributing the recording medium to the user.

step3.
It is assumed that the user who uses the user terminal 30 wants to search for any w ^* among the keywords w1 to wn. The user terminal 30 selects a random number r,
Keyword search input X = rP + H ₀ (w ^* )
And the obtained X is sent to the providing terminal 20 via the Internet 10.

step4.
When the providing terminal 20 receives X from the use terminal 30, it uses the random number s,
First keyword search output K '= sX
And the obtained K ′ is sent to the user terminal 30 via the Internet 10.

step5.
When the use terminal 30 receives K ′ from the providing terminal 20, the validity of K ′ is a Beille pair that is a mapping to a multiplicative group having bilinearity with respect to two points P and Q defined on the elliptic curve. It is verified whether e (P, K ′) = e (Y, X) is equal using a Weil pairing or Tate pairing e (P, Q).

  The Beille pairing is described in Mitsuko Miyaji and Hiroaki Kikuchi, “IT Text Information Security”, page 90, Ohmsha, 2003.10.25.

  The user terminal 30 regards K ′ as valid if e (P, K ′) = e (Y, X) is equivalent, and regards K ′ as invalid if it is not equivalent.

step6.
The use terminal 30 has step5. Using K ′ and random numbers r and Y that are considered valid in the verification of
Second keyword search output K = K'-rY
Calculate Furthermore, the use terminal 30 determines that i = 1 to n.
ai‖bi = Ei XOR H ₁ (wi‖K‖i)
Calculate Here, ai is the first l bit and bi is the remaining character string.

step7.
When a _i = 0 ^l, that is, when the first consecutive l bits are all “0”, it is considered that the keyword w _i matches w ^* . At this time, the corresponding content c _i is obtained as b _i .

  As described above, in the present embodiment, by adopting a method based on the discrete logarithm problem on an elliptic curve, the key length size (the size of random numbers s and r) can be set to about 160 bits. The amount of communication can be reduced to 1/3 compared to the method.

  Further, by verifying the data exchanged between the providing terminal 20 and the use terminal 30 by OKS using Bayeux pairing or ate pairing, it is verified whether the processing in the providing terminal 20 is correctly performed according to the procedure. it can.

It is the schematic which shows the structure of the on-demand search system which concerns on one embodiment of this invention. It is a figure for demonstrating the processing procedure of OKS based on the discrete logarithm problem on the finite field performed using the system of FIG. It is a figure for demonstrating the processing procedure of OKS based on the discrete logarithm problem on the finite field performed using the system of FIG.

Explanation of symbols

10 network 20 providing terminal 30 using terminal 40 database

Claims (9)

A providing terminal that encrypts contents corresponding to keywords stored in the database on a one-to-one basis and provides the encrypted contents and a use terminal for decrypting and using the encrypted contents are connected via a network. An on-demand search method using the on-demand search system,
The providing terminal generates a first random number;
The providing terminal generates public information using the first random number;
The providing terminal uses a keyword stored in the database, content corresponding to the keyword on a one-to-one basis, the first random number, a first hash function, and a second hash function. Generating the encrypted content;
The providing terminal recording the public information and the encrypted content on a recording medium;
Distributing the recording medium to use terminals;
The user terminal generating a second random number;
The user terminal uses the second random number, the abel group generator, and the first hash function to convert an arbitrarily selected keyword into a form that is not known to the providing terminal. Generating a search input;
The user terminal transmitting the keyword search input to the providing terminal via a network;
The providing terminal receiving the keyword search input;
The providing terminal generates a first keyword search output using the keyword search input and the first random number;
The providing terminal transmitting the first keyword search output to the user terminal via a network;
The user terminal receiving the first keyword search output;
The use terminal uses the public information recorded on the recording medium, the keyword search input, the generation source of the abelian group, and a verification formula using the property of pairing operation, Verifying the validity of the keyword search output;
Generating a second keyword search output using the first keyword search output deemed valid by the user terminal, the public information, and the second random number;
The user terminal uses the second keyword search output, the encrypted content recorded on the recording medium, the second hash function, and the arbitrarily selected keyword to arbitrarily Obtaining content corresponding one-to-one with the selected keyword;
An on-demand search method comprising:   2. The on-demand search method according to claim 1, wherein an Oblivious Keyword Search (OKS) is used. The providing terminal uses G as an abelian group (commutative group) whose order is a prime number q defined on an elliptic curve, P as a generation source of the group G, s as the first random number, and Y as the public information. = SP, the first hash function is set as H ₀ , the second hash function is set as H _1, and for all the keywords wi and contents ci of indexes i = 1 to n,
Encryption key Ki = sH ₀ (wi)
And the encrypted content Ei = H ₁ (wi‖Ki‖i) XOR (0 ^l ‖ci)
(Where XOR is an exclusive OR of bit strings, 0 ^l is a series of l 0 bits, and ‖ is a combination of bit strings)
3. The method according to claim 2, wherein an encryption method based on a discrete logarithm problem on an elliptic curve for calculating is applied to reduce the amount of data transmitted and received between the providing terminal and the using terminal. Demand search method. In order to verify whether or not K ′ received as the first keyword search output is valid data, the user terminal uses the public information Y and the second random number as r, and is arbitrarily selected. The keyword search input X = rP + H ₀ (w ^* ) when the keyword is w ^* , the generation source P of the abelian group, and the two points P and Q defined on the elliptic curve are bilinear. Using Beille pairing or Tate pairing e (P, Q), which is a mapping to the multiplicative group,
Verification equation e (P, K ′) = e (Y, X)
4. The on-demand search method according to claim 3, wherein the first keyword search output K ′ is regarded as valid data if the verification expressions are equal. A providing terminal that encrypts contents corresponding to keywords stored in the database on a one-to-one basis and provides the encrypted contents and a use terminal for decrypting and using the encrypted contents are connected via a network. On-demand search system,
The providing terminal is:
First random number generating means for generating a first random number;
Public information generating means for generating public information using the first random number;
Using the keyword stored in the database, the content corresponding to the keyword on a one-to-one basis, the first random number, the first hash function, and the second hash function, the encrypted content Content encryption means for generating
A recording medium writing means for recording the public information and the encrypted content on a recording medium for distribution to the user terminal;
Keyword search input receiving means for receiving a keyword search input transmitted from the user terminal via the network;
First keyword search output generation means for generating a first keyword search output using the keyword search input and the first random number;
First keyword search output transmission means for transmitting the first keyword search output to the user terminal via a network;
With
The user terminal is
Second random number generation means for generating a second random number;
Using the second random number, the abel group generator, and the first hash function, the keyword selection input is generated by converting an arbitrarily selected keyword into a form not known to the providing terminal. Keyword search input generation means for performing,
Keyword search input transmission means for transmitting the keyword search input to the providing terminal via the network;
First keyword search output receiving means for receiving the first keyword search output transmitted from the providing terminal via the network;
Validating the first keyword search output using the public information recorded on the recording medium, the keyword search input, the generation source of the abelian group, and a verification formula using the nature of the pairing operation First keyword search output correctness verification means for verifying
Second keyword search output generation means for generating a second keyword search output using the first keyword search output deemed valid, the public information, and the second random number;
Using the second keyword search output, the encrypted content recorded on the recording medium, the second hash function, and the arbitrarily selected keyword, to the arbitrarily selected keyword An on-demand search system comprising: content decrypting means for obtaining content corresponding one-to-one. The providing terminal uses G as an abelian group (commutative group) whose order is a prime number q defined on an elliptic curve, P as a generation source of the group G, s as the first random number, and Y as the public information. = SP, the first hash function is set as H ₀ , the second hash function is set as H _1, and for all the keywords wi and contents ci of indexes i = 1 to n,
Encryption key Ki = sH ₀ (wi)
And the encrypted content Ei = H ₁ (wi‖Ki‖i) XOR (0 ^l ‖ci)
(Where XOR is an exclusive OR of bit strings, 0 ^l is a series of l 0 bits, and ‖ is a combination of bit strings)
And applying a cryptographic method based on a discrete logarithm problem on an elliptic curve that reduces the amount of data transmitted and received between the user terminal and the providing terminal,
In order to verify whether or not K ′ received as the first keyword search output is valid data, the user terminal uses the public information Y and the second random number as r, and is arbitrarily selected. The keyword search input X = rP + H ₀ (w ^* ) when the keyword is w ^* , the generation source P of the abelian group, and the two points P and Q defined on the elliptic curve are bilinear. Using Beille pairing or Tate pairing e (P, Q), which is a mapping to the multiplicative group,
Verification equation e (P, K ′) = e (Y, X)
6. The on-demand search system according to claim 5, wherein if the verification expressions are equal, the first keyword search output K ′ is regarded as valid data. It provides encrypted content obtained by encrypting content corresponding to keywords stored in the database on a one-to-one basis and public information, and converts a keyword search input received via a network using a first random number. In a use terminal used in an on-demand search system including a providing terminal that generates and returns a first keyword search output,
Second random number generation means for generating a second random number;
Using the second random number, the abel group generator, and the first hash function, the keyword search input is generated by converting an arbitrarily selected keyword into a form not known to the providing terminal. Keyword search input generation means;
Keyword search input transmission means for transmitting the keyword search input to the providing terminal via the network;
First keyword search output receiving means for receiving the first keyword search output transmitted from the providing terminal via the network;
The first information for verifying the validity of the first keyword search output using the public information, the keyword search input, the generation source of the abelian group, and the verification formula using the property of the pairing operation A keyword search output correctness verification means;
Second keyword search output generation means for generating a second keyword search output using the first keyword search output deemed valid, the public information, and the second random number;
Using the second keyword search output, the encrypted content, the second hash function, and the arbitrarily selected keyword, content corresponding to the arbitrarily selected keyword is one-to-one. Content decrypting means to obtain;
A use terminal comprising: The providing terminal uses G as an abelian group (commutative group) whose order is a prime number q defined on an elliptic curve, P as a generation source of the group G, s as the first random number, and Y as the public information. = SP, the first hash function is set as H ₀ , the second hash function is set as H _1, and all the keywords wi and contents ci of indexes i = 1 to n are set as follows:
Encryption key Ki = sH ₀ (wi)
And the encrypted content Ei = H ₁ (wi‖Ki‖i) XOR (0 ^l ‖ci)
(Where XOR is an exclusive OR of bit strings, 0 ^l is a series of l 0 bits, and ‖ is a combination of bit strings)
And applying a cryptographic method based on a discrete logarithm problem on an elliptic curve that reduces the amount of data transmitted and received between the user terminal and the providing terminal,
In order to verify whether or not K ′ received as the first keyword search output is valid data, the user terminal uses the public information Y and the second random number as r, and is arbitrarily selected. The keyword search input X = rP + H ₀ (w ^* ) when the keyword is w ^* , the generation source P of the abelian group, and the two points P and Q defined on the elliptic curve are bilinear. Using Beille pairing or Tate pairing e (P, Q), which is a mapping to the multiplicative group,
Verification equation e (P, K ′) = e (Y, X)
8. The use terminal according to claim 7, wherein the first keyword search output K ′ is regarded as valid data if the verification expressions are equal to each other. The providing terminal uses G as an abelian group (commutative group) whose order is a prime number q defined on an elliptic curve, P as a generation source of the group G, s as the first random number, and Y as the public information. = SP, the first hash function is set as H ₀ , the second hash function is set as H _1, and for all the keywords wi and contents ci of indexes i = 1 to n,
Encryption key Ki = sH ₀ (wi)
And encrypted content Ei = H ₁ (wi‖Ki‖i) XOR (0 ^l ‖ci)
(Where XOR is an exclusive OR of bit strings, 0 ^l is a series of l 0 bits, and ‖ is a combination of bit strings)
And applying a cryptographic method based on a discrete logarithm problem on an elliptic curve that reduces the amount of data transmitted and received between the user terminal and the providing terminal,
In order to verify whether or not K ′ received as the first keyword search output is valid data, the user terminal uses the public information Y and the second random number as r, and is arbitrarily selected. The keyword search input X = rP + H ₀ (w ^* ) when the keyword is w ^* , the generation source P of the abelian group, and the two points P and Q defined on the elliptic curve are bilinear. Using Beille pairing or Tate pairing e (P, Q), which is a mapping to the multiplicative group,
Verification equation e (P, K ′) = e (Y, X)
The on-demand search method according to claim 1, wherein the first keyword search output K 'is regarded as valid data if the verification expressions are equal.

Images