Searchable encryption method

Abstract

A method for searchable encryption of a system defining a secret key and a public is provided. A data stream cipher can include n elementary data (b.sub.1, b.sub.2, . . . , b.sub.n). The method can include generation of a variate for all elementary data b.sub.j, for values of j from 1 to n, generation of an element function of the public key (g.sup.x(bj),zj) and the variate, the element being associated with a random element of a group of a bilinear environment, the element associated with the random element of the group forming first encryption data (C.sub.j,1). The method can also include generation of a shift factor (g.sup.a.zj−1) function of the variate and the public key, and associated with the random element of the group, the shift factor representing a position of the monomial in the encrypted stream, the shift factor associated with the random element of the group forming second encryption data. The data stream cipher can include the first and second encryption data for all values of j from 1 to n.

Claims

1. A method of generating trapdoors in a searchable encryption system, the system defining a secret key and a public key, a trapdoor being associated with a keyword comprising elementary data (v.sub.1,v.sub.2, . . . w.sub.l) the trapdoor being generated by: generating l randoms (v.sub.1,v.sub.2, . . . v.sub.l), generating a polynomial (V) in an element z, the polynomial dependent on the secret key, the polynomial of degree l, a j-th coefficient of the polynomial, 1≤j≤l, being dependent on an encoding of the j-th elementary data item (w.sub.j) of the keyword defined in the secret key and of a j-th random (v.sub.j) of the l randoms, the trapdoor comprising the polynomial associated with a random element of a group (h) of a bilinear environment, and the l randoms associated with the random element of the group; and making the trapdoor available to a test entity configured to detect the keyword in a ciphertext of a data stream transmitted between an encryption entity and a decryption entity.

2. A searchable encryption method of a system defining a secret key and a public key, a ciphertext of a data stream which comprises n elementary data (b.sub.1,b.sub.2, . . . b.sub.n) comprising: generation of a random (a), and for any elementary data item b.sub.j, j=1 to n, generation of an element dependent on the public key (g.sup.x(b.sub.j),z.sup.f) and the random, the element being associated with a random element of a group (g) of a bilinear environment, the element associated with the random element of the group forming a first encryption data item (C.sub.j,1), and generation of a shift factor (g.sup.a,z.sup.j−z) dependent on the random and the public key, and associated with the random element of the group, the shift factor being representative of a position of a monomial in the encrypted stream, the shift factor associated with the random element of the group forming a second encryption data item (C.sub.j,2), the ciphertext of the data stream comprising for any j=1 to n, the first and second encryption data items; the method further comprising transmission of the ciphertext of the data stream to a decryption entity configured to decrypt the ciphertext of the data stream.

3. A method of detecting a keyword in a ciphertext of a data stream in a searchable encryption system, the system defining a secret key and a public key, the keyword comprising l elementary data (w.sub.1, . . . w.sub.t), the method comprising: obtaining a trapdoor associated with the keyword, the trapdoor comprising l randoms (h.sup.vi) associated with a random element (h) of a group of a bilinear environment, and a polynomial in an element z, dependent on the secret key and of degree l, the polynomial being associated with the random element of the group (h.sup.v), an i-th coefficient of the polynomial, 1≤i≤l, being dependent on an encoding of the i-th elementary data item (w.sub.i) of the keyword defined in the secret key and an i-th random (v.sub.i) of the l randoms, starting from a current position j, and for any i=1 to l, coupling (E41) of the (j+i)-th element of the ciphertext and of the i-th random of the trapdoor by means of a bilinear mapping, the bilinear mapping taking as input a first element of a first group and a second element of a second group and with values in a third group, and assembling the l couplings obtained, the assembling producing a first polynomial of degree l, for any i=1 to l, coupling a shift factor associated with the current position and of the polynomial associated with the trapdoor, the coupling producing a second polynomial of degree l, and comparing the first and second polynomials, equality of the two polynomials being representative of the presence of the keyword in the stream starting from the current position j.

4. A method of decrypting a ciphertext of a data stream, the data stream comprising of elementary data (b.sub.1,b.sub.2, . . . b.sub.n), the ciphertext being generated in by the searchable encryption method of claim 2, the decryption method comprising: obtaining (E50) of a trapdoor associated with each of the distinct elementary data of the data stream, the trapdoor being generated in accordance with the method for generating trapdoors as claimed in claim 1, detecting the presence of the trapdoor, in accordance with the method of claim 3.

5. A device for generating trapdoors in a searchable encryption system, the system defining a secret key and a public key, a trapdoor being associated with a keyword comprising l a elementary data (w.sub.1 . . . w.sub.l), the device configured to: generate l randoms (v.sub.1,v.sub.2, . . . v.sub.l), generate a polynomial in an element z, dependent on the secret key, and of degree l a j-th coefficient of the polynomial, 1≤j≤l, being dependent on an encoding of the j-th elementary data item (w.sub.j) of the keyword defined in the secret key and a J-th random (v.sub.j) of the l-randoms, the trapdoor comprising the polynomial associated with a random element of a group (h) of a bilinear environment, and the l randoms associated with the random element of the group; and make the trapdoor available to a test entity configured to detect the keyword in a ciphertext of a data stream transmitted between an encryption entity and a decryption entity.

6. A non-transitory computer readable medium having stored thereon instructions which, when executed by a processor, cause the processor to implement the method of claim 1.

7. A searchable encryption device of a system defining a secret key and a public key, a ciphertext of a data stream which comprises n elementary data (b.sub.1,b.sub.2, . . . b.sub.n), the device configured to: generate a random (a), and generate, for any elementary data item b.sub.j,l=1 to n, an element dependent on the public key (g.sup.x(b.sub.j),z.sup.i) and the random, the element being associated with a random element of a group (g) of a bilinear environment, the element associated with the random element of the group forming a first encryption data item (C.sub.j,1) and generation of a shift factor (g.sup.a.z.sup.i−1) dependent on the random and the public key, and associated with the random element of the group, the shift factor being representative of a position of a monomial in the encrypted stream, the shift factor associated with the random element of the group forming a second encryption data item (C.sub.j,2), the ciphertext of the data stream comprising for any j=1 to n, the first and second encryption data items; the device further configured to transmit the ciphertext of the data stream to a decryption entity configured to decrypt the ciphertext of the data stream.

8. A non-transitory, computer readable medium having stored thereon instructions which, when executed by a processor, cause the processor to implement the method of claim 2.

9. A device for detecting a keyword in a ciphertext of a data stream in a searchable encryption system, the system defining a secret key and a public key, the keyword comprising l elementary data (w.sub.1 . . . w.sub.l), the device configured to: obtain a trapdoor associated with the keyword, the trapdoor comprising l randoms (h.sup.vi) associated with a random element (h) of a group of a bilinear environment, and a polynomial in an element z, dependent on the secret key and of degree l, the polynomial being associated with the random element of the group (h.sup.v), an i-th coefficient of the polynomial, 1≤i≤l, being dependent on a ciphertext of the i-th elementary data item (w.sub.i) of the keyword defined in the secret key and an i-th random (v.sub.i) of the l randoms, starting from a current position j, and for any i=1 to l calculate a coupling of the (j+i)-th element of the ciphertext and of the i-th random of the trapdoor by means of a bilinear mapping, the bilinear mapping taking as input a first random element of a first group and a second random element of a second group and with values in a third group, and to assemble the 1 couplings obtained, the assembling producing a first polynomial of degree l, for any i=to 1to l, calculate a coupling of a shift factor associated with the current position and of the polynomial associated with the trapdoor, the coupling producing a second polynomial of degree l, compare the first and second polynomials, equality of the two polynomials being representative of the presence of the keyword in the stream starting from the current position j.

10. A non-transitory, computer readable medium having stored thereon instructions which, when executed by a processor, cause the processor to perform the method of claim 3.

11. A searchable encryption system comprising: a trapdoor-generating device for generating trapdoors in the searchable encryption system, the system defining a secret key and a public key, a trapdoor being associated with a keyword comprising l elementary data (w.sub.1 . . . w.sub.l), the trapdoor-generating device configured to: generate l randoms (v.sub.1, v.sub.2, . . . v.sub.l), generate a polynomial in an element z, dependent on the secret key, and of degree l, a j-th coefficient of the polynomial, 1≤j≤l, being dependent on an encoding of the j-th elementary data item (w.sub.j) of the keyword defined in the secret key and a j-th random (v.sub.j) of the l-randoms, the trapdoor comprising the polynomial associated with a random element of a group (h) of a bilinear environment, and the l randoms associated with the random element of the group; and make the trapdoor available to a test entity configured to detect the keyword in a ciphertext of a data stream transmitted between an encryption entity and a decryption entity; a searchable encryption device of the searchable encryption system, a ciphertext of a data stream which comprises n elementary data (b.sub.1, b.sub.2, . . . , b.sub.n), the searchable encryption device configured to: generate a random (a), and generate, for any elementary data item b.sub.j,j=1 to n, an element dependent on the public key (g.sup.x(b.sub.j),z.sup.i) and the random, the element being associated with a random element of a group (g) of a bilinear environment, the element associated with the random element of the group forming a first encryption data item (C.sub.j,1), and generation of a shift factor (g.sup.az.sup.j−1) dependent on the random and the public key, and associated with the random element of the group, the shift factor being representative of a position of a monomial in the encrypted stream, the shift factor associated with the random element of the group forming a second encryption data item (C.sub.j,2), the ciphertext of the data stream comprising for any j=1 to n, the first and second encryption data items; the device further configured to transmit the ciphertext of the data stream to a decryption entity configured to decrypt the ciphertext of the data stream; and the device of claim 9.

12. The method of claim 1, wherein making the trapdoor available to a test entity for use in the detection of the keyword in an encrypted stream comprises transmitting the trapdoor to a test entity distinct from an entity which generated the trapdoor.

13. The method of claim 1, wherein the test entity comprises the same entity that generated the trapdoor.

14. The method of claim 1, wherein the ciphertext in which the test entity is configured to detect the keyword is generated independently of the keyword the test entity is configured to detect.

15. The device of claim 5, wherein the device is configured to make the trapdoor available to a test entity for use in the detection of the keyword in an encrypted stream by transmitting the trapdoor to a test entity distinct from an entity which generated the trapdoor.

16. The device of claim 5, wherein the test entity comprises the same entity that generated the trapdoor.

17. The device of claim 5, wherein the ciphertext in which the test entity is configured to detect the keyword is generated independently of the keyword the test entity is configured to detect.

Description

(1) Other characteristics and advantages of the present invention will be better understood from the description and appended drawings among which:

(2) FIGS. 1a and 1b present a searchable encryption system, according to two exemplary embodiments;

(3) FIG. 2 presents the steps of a searchable encryption method, according to an exemplary embodiment;

(4) FIG. 3 presents the steps of a method for generating trapdoors, according to an exemplary embodiment;

(5) FIG. 4 presents the steps of a method for detecting a keyword in a stream, according to an exemplary embodiment;

(6) FIG. 5 presents the steps of a decryption method, according to an exemplary embodiment;

(7) FIG. 6 is a schematic representation of a device for generating trapdoors, according to an exemplary embodiment;

(8) FIG. 7 is a schematic representation of a searchable encryption device, according to an exemplary embodiment;

(9) FIG. 8 is a schematic representation of a device for detecting the presence of a keyword in a stream, according to an exemplary embodiment.

(10) A searchable encryption system, according to a first exemplary embodiment, will now be described in conjunction with FIG. 1a.

(11) A searchable encryption system 100 intended to detect the presence of an element, or keyword W, in an encrypted stream C comprises a plurality of entities. An encryption entity 10 is designed to encrypt a data stream B for the attention of a decryption entity 11. The data stream is for example a stream of bits, or a stream of bytes. The decryption entity 11 is designed to receive the stream B encrypted as a stream C, and to decrypt it.

(12) The searchable encryption system 100 is based on a public-key cryptography system. To this end it rests upon a secret key K.sub.s. and an associated public key K.sub.p. It is assumed that an entity 12 for generating keys is designed to generate the pair of keys K.sub.s, K.sub.p for the system 100 according to a known scheme.

(13) An entity for generating trapdoors 13 is designed to generate, for a keyword W to be searched for in the encrypted stream B, an associated “trapdoor” T. A trapdoor T is a piece of information associated with the keyword W; the trapdoor T is designed to allow a test entity 14 which holds it to search for the presence of the keyword W in the encrypted stream C. The entity for generating trapdoors 13 has at its disposal the secret key K.sub.s. generated by the entity for generating keys 12. The entity for generating trapdoors 13 is designed to transmit the trapdoor or trapdoors that it has generated to the test entity 14.

(14) In a second exemplary embodiment of the encryption system 100, illustrated by FIG. 1b, the decryption entity 11 is designed to generate the keys, to generate the trapdoors associated with the keywords to be searched for and to transmit them to the test entity 14. Stated otherwise, the decryption entity 11 implements the functionalities of the entity for generating keys 12 and of the entity for generating trapdoors 13 such as are presented in conjunction with FIG. 1a. It is understood that the exemplary embodiment described in conjunction with FIG. 1b offers maximum security in the sense that the secret key K.sub.s of the system is held only by a single entity, the decryption entity 11.

(15) In another variant (not represented) the entity for generating keys 12 is independent of the decryption entity 11. In this case, the decryption entity 11 receives the secret key K.sub.s from the entity for generating keys 12 in a secure manner, according to a known protocol.

(16) In another exemplary embodiment (not represented), the decryption entity 11 implements the functions of the test entity 14 and detects the presence of keywords in a stream. Such an architecture is suitable for malware detection implemented by an enterprise on an incoming encrypted data stream.

(17) The searchable encryption system 100 operates in a bilinear environment which refers to three cyclic groups, customarily denoted G1, G2 and GT, of prime order p, as well as a bilinear mapping e, called a “bilinear coupling” taking as input an element of the group G1 and an element of the group G2 and with values in the group GT.

(18) This type of environment is frequently used in cryptography and may be implemented very efficiently.

(19) An exemplary embodiment is concerned with an asymmetric bilinear environment which refers to the case where no efficiently evaluable functions between the groups G1 and G2 are known.

(20) The steps of a searchable encryption method, according to an exemplary embodiment, will now be described in conjunction with FIG. 2.

(21) The method described here is illustrated in the case of a searchable encryption system 100 such as represented in conjunction with FIG. 1a. In this example, it is considered that the entity for generating keys 12 of the system 100 is distinct from the decryption entity 11. Likewise, it is considered that the entity for generating trapdoors 14 is distinct from the decryption entity 11. Although non-optimum as regards security, this system makes it possible to distinguish the functions of each of the entities. Adaptation of the method to another system, for example the system 100 described in conjunction with FIG. 1b, is immediate.

(22) The encryption entity 10 is designed to encrypt a data stream B for the attention of the decryption entity 11. The data stream B is for example a stream of bits, or a stream of bytes. In the example described here it is assumed that the data stream which is encrypted is a stream of n-bits, denoted B=b.sub.1 . . . b.sub.n. The decryption entity 11 is designed to receive the encrypted stream, denoted C, and to decrypt it.

(23) In a prior step E20 of generating keys, the entity for generating keys 12 generates a secret/public key pair K.sub.s/K.sub.p for the searchable encryption system 100. The secret key K.sub.s of the system 100 comprises a secret, such as a random integer z, and an encoding of each of the possible values taken by the elements b.sub.i, or elementary data. For example, with each possible value of b.sub.i is associated a random integer x.sub.i. The encoding of the value b.sub.i is the integer x.sub.i and is denoted x(b.sub.i)=x.sub.i. Note that in the case of streams of bits, the secret key K.sub.s comprises two encoding values associated respectively with the bits 0 and 1. Thus, the secret key of the system 100 comprises, for all possible values of b.sub.i:

(24) $K_s=\{\begin{array}{c}{x}_i=x\left(b_i\right),\\ z\end{array}$

(25) The associated public key comprises:

(26) $K_p=\{\begin{array}{c}{g}^{z^j}\\ g^{\left(x_i.Math.z^j\right)}\end{array}$

(27) with g a random element of the group G1, and j the maximum size of the data streams to be encrypted. For example, j=1000, or j=256, etc. In a conventional manner, exponentiation makes it possible not to be able to retrieve the values z.sup.j and x.sub.i. z.sup.j from the public key.

(28) Note that in another exemplary embodiment where the stream would consist of bytes, the secret key would comprise a random integer and the encoding of 256 values.

(29) In a following publication step E21, the public key K.sub.p is published by the key generating entity 12. The secret key K.sub.s is transmitted in a secure manner to the decryption entity 11 in a sending step E22. Note that the prior steps of generating keys E20, of publication E21 and of sending the secret key E22 are executed on creation of the system, for the generation of a pair of keys. The public key K.sub.p is used for any encryption and by any encryption entity 10 for the attention of the decryption entity 11, until the pair of keys is revoked or/and renewed.

(30) In a following step E23 for generating a random, the encryption entity 10 randomly generates an integer a.

(31) In a following encryption step E24, the encryption entity 10 undertakes the encryption of the data item B by means of the elements of the public key K.sub.p. To this end, the encryption entity 10 calculates for each element b.sub.1,1≤j≤n of the stream B=b.sub.1 . . . b.sub.n to be encrypted a first encryption data item C.sub.j,1 and a second encryption data item C.sub.j,2 according to the following formula:

(32) $\{\begin{array}{c}{C}_{j,1}={\left(g^{x\left(b_j\right).Math.z^j}\right)}^a\\ C_{j,2}={\left(g^{z^{j-1}}\right)}^a\end{array}\hspace{1em}$

(33) The power of the first encryption data item C.sub.j,1=(g.sup.x(b.sup.j.sup.).z.sup.j).sup.a is a monomial associated with the j-th element of the stream B.

(34) The second encryption data item, C.sub.j,2=(g.sup.z.sup.j−1).sup.a, is intended to take account of the position j of the current bit b.sub.b in the stream B to be encrypted and thus to take into account a shift of the current bit b.sub.j with respect to the initial bit b.sub.1 in the stream B. Thus, and according to this formula, for the bit b.sub.1 of B, positioned in first position, there is no shift, the associated shift element is g.sup.a. The bit b.sub.2 positioned in second position undergoes a shift of 1 with respect to the first bit b.sub.1, the associated shift element is then (g.sup.z).sup.a, etc. The first and second encryption data items C.sub.j,1, C.sub.j,2 form an encrypted stream C corresponding to the ciphertext of the stream B.

(35) In a following sending step 25, the encryption entity 10 sends the encrypted stream C to the decryption entity 11.

(36) The generation of the first and second encryption data items is carried out independently of keywords to be searched for in the stream B. Thus, it is not necessary to define a priori the keywords while encrypting a stream, as is the case with known solutions. Thus, the searchable encryption described here offers significant flexibility which allows application to encrypted stream broadcasting services in which the keywords that the entity which decrypts wants to identify in the stream are defined by said entity itself, without involving the encryption entity.

(37) A method for generating trapdoors, according to an exemplary embodiment, will now be described in conjunction with FIG. 3.

(38) The method for generating trapdoors is implemented by the entity for generating trapdoors 13. Note that the method for generating trapdoors is independent of the encryption method and can be implemented provided that the entity 13 for generating trapdoors possesses the secret key K.sub.s. and the data item that it is searching for.

(39) In an initial step E30 of generating a trapdoor, the entity 13 for generating trapdoors, holding the secret key K.sub.s, generates a trapdoor T for a keyword W. The keyword W is a plaintext data item, here a string of bits. The trapdoor T which is associated therewith is intended to be used to search for the presence of the keyword W in the stream B, on the basis of the encrypted stream C. The keyword W is a series of bits: W=w.sub.1 . . . w.sub.l. The generation of the trapdoor T associated with the keyword W consists in generating in a first generating sub-step E301, l random integers v.sub.i, 1≤i≤l, and in generating in a second generating sub-step E302 a polynomial V in z of degree l whose coefficients are of the form:

(40) v.sub.i.x(w.sub.i), where x(w.sub.i) is the encoding of w.sub.i such as defined in the course of the step of configuration by the secret key K.sub.s.

(41) The random values and the polynomial V not being able to be revealed, they are transmitted to the test entity 14 in the guise of trapdoor T in the form of an exponentiation. More precisely, the trapdoor T associated with the keyword W and which comprises the l random values and the polynomial V in z of degree l comprises:

(42) $T=\{\begin{array}{c}{h}^V=h^{v_1.Math.x\left(w_1\right).Math.z+v_2.Math.x\left(w_2\right).Math.z^2+\mathrm{.Math.}+v_l.Math.x\left(w_l\right).Math.z^l,}\\ h^{v_1},h^{v_2},\mathrm{.Math.},h^{v_l}\end{array},$

(43) where h is a random element of the group G2.

(44) In a following sending step E31, the trapdoor T associated with the keyword W is sent to the test entity 14, designed to detect the presence of the keyword W with which the trapdoor T in the stream B has been associated therewith on the basis of the encrypted stream C. Note that in an exemplary embodiment where the decryption entity 11 implements the functions of the entity for generating trapdoors 13 and of the test entity 14, this step is not executed. It appears dashed in FIG. 3.

(45) The method for generating trapdoors does not impose any constraint as regards the size of the keywords with which the trapdoors are associated and/or as regards their number. With respect to known solutions, this offers great flexibility as regards the choice of keywords.

(46) In a variant embodiment of the method for generating trapdoors, there are selected in the course of the generating sub-step E301, l random elements v.sub.i, 1≤i≤l, of a subset of integers. In this example, there is no constraint as regards the size of the subset from which the random elements arise. Thus, it is possible for some of the elements v.sub.i generated in this subset to be equal. This is the case for example when the subset is reduced to an element. By selecting the random elements in a subset of integers, the phase of detecting trapdoors in the ciphertext is optimized; the detection time can be considerably reduced, especially when several random elements are equal.

(47) A method for detecting a keyword in an encrypted stream, according to an exemplary embodiment, will now be described in conjunction with FIG. 4.

(48) The detection method, implemented by the test entity 14, consists in searching for the presence of the keyword W in the stream B on the basis of the encrypted stream C. Indeed, it is the encrypted stream C which is transmitted between the encryption entity 10 and the decryption entity 11 and it is this encrypted stream C that the test entity 14 analyses with the aim of detecting the presence of the keyword W. More precisely, it is question of verifying whether a sub-string of the stream B, b.sub.j+1 . . . b.sub.j+1 transmitted encrypted in the stream C is equal to the keyword W. An informal objective is to reconstruct a polynomial U on the basis of the first encryption data C.sub.j+1,1, . . . , C.sub.j+l,1 of the stream B and to compare it with the polynomial V which is associated with the trapdoor T. Indeed, a mathematical property of polynomials is that two polynomials are equal if and only if their coefficients are pairwise equal. Since the encoding used to encrypt the stream B, more precisely the elementary data b.sub.1 . . . b.sub.n of the stream B, and the encoding used to construct the trapdoor T, which depends on the encoding of the elementary data w.sub.1 . . . w.sub.l of the keyword W, is the same, then equality of the two polynomials necessarily implies that the successive encodings of the elementary data b.sub.j+1 . . . b.sub.j+l which feature in the polynomial U are equal to the encodings of the elementary data w.sub.1 . . . w.sub.l of the keyword W which are used to generate the trapdoor T. Such equality therefore indicates that the keyword W=w.sub.1 . . . w.sub.l is equal to the sub-string b.sub.j+1 . . . b.sub.j+1 of the stream B.

(49) In an initial obtaining step E40, the test entity 14 obtains the trapdoor T associated with the keyword W. In the example described here, the test entity 14 receives from the entity for generating trapdoors 13 the trapdoor T associated with the keyword W. In another exemplary embodiment in which the decryption entity 11 implements the functions of the entity 13 for generating trapdoors and the functions of the test entity 14, the decryption entity 11 obtains the trapdoor T by generating it. In a following step E41 of coupling and assembling elements of the ciphertext from a current position, the test entity 14 assembles l-elements of the ciphertext from a current position j with the aim of obtaining a polynomial U. This polynomial is intended to be compared with the polynomial V associated with the trapdoor T. The first encryption data being exponentiations of monomials, there is calculated the product of the exponentiations of the consecutive l-monomials. Moreover, it is noted that random integers v.sub.i occur in the coefficients of the polynomial V associated with the trapdoor T. In order for the comparison between the polynomials U and V to be meaningful it is therefore necessary that the integers v.sub.i also occur in the polynomial U to be reconstructed. To this effect, in the coupling and assembling step E41, a coupling is used between the first encryption data C.sub.j+1,1 and the parameters h.sup.v.sup.i, included in the trapdoor T and one therefore calculates:

(50) $\underset{i=1àl}{.Math.}e\left(C_{j+i,1},h^{v_i}\right),\mathrm{where}$$.Math.\mathrm{is}\mathrm{the}\mathrm{standard}\mathrm{symbol}\mathrm{for}\mathrm{designating}a\mathrm{product}=e\left(C_{j+1,1,}{h}^{v_1}\right).Math.e\left(C_{j+2,1,}{h}^{v_2}\right)\mathrm{.Math.}e\left(C_{j+l,1,}{h}^{v_l}\right)=e\left({\left(g^{x\left(b_{j+1}\right).Math.z^{j+1}}\right)}^a,h^{v_1}\right).Math.e\left({\left(g^{x\left(b_{j+2}\right).Math.z^{j+2}}\right)}^a,h^{v_2}\right)\mathrm{.Math.}e\left({\left(g^{x\left(b_{j+l}\right).Math.z^{j+l}}\right)}^a,h^{v_l}\right)={e\left(g,h\right)}^{a.Math.x\left(b_{j+1}\right).Math.z^{j+1}.Math.v_1}.Math.{e\left(g,h\right)}^{a.Math.x\left(b_{j+2}\right).Math.z^{j+2}.Math.2}\mathrm{.Math.}{e\left(g,h\right)}^{a.Math.x\left(b_{j+l}\right).Math.z^{j+1}.Math.v_l}$

(51) By using the properties of the coupling and post-product, the exponent of e(g, h) is a polynomial U′ such that:

(52) $U^{\prime }=a.Math.\underset{i=1àl}{.Math.}x\left(b_{j+1}\right).Math.v_i.Math.z^{j+i}$$U^{\prime }=a.Math.z^j.Math.\underset{i=1àl}{.Math.}x\left(b_{j+1}\right).Math.v_i.Math.z^i$$U^{\prime }=a.Math.z^j.Math.U$

(53) where U is a polynomial in z of degree l.

(54) It is noted that equality between the sub-string b.sub.j+1 . . . b.sub.j+1 and the keyword W is equivalent to equality between the polynomial U and the polynomial V since the encodings involved in encrypting the stream B and in generating the trapdoor T associated with the keyword W are the same.

(55) To compare the sub-string b.sub.j+1 . . . b.sub.j+l and the keyword W, it therefore remains to compare the polynomials U and V, this being possible by virtue of the coupling. Thus, in a coupling step E42, there is calculated the coupling of the second encryption data item C.sub.j +1,2 and of the first element of the trapdoor T,h.sup.V. One obtains:
e(C.sub.j+1,2, h.sup.V)=e(g.sup.a.z.sup.(j+1−1), h.sup.V)=e(g,h).sup.a.z.sup.j.sup..V

(56) The second encryption data item C.sub.j+1,2 is used to shift the polynomial V, or more precisely to take account of the current position j, in the stream B, starting from which the search for the keyword W is performed. The current position j constitutes the shift that has to be taken into account. Note that the second encryption data item of index j+1 is used since by construction this is the data item which corresponds to the monomial which features in the current position.

(57) In a following test step E43, one verifies whether:
e(g,h).sup.a.z.sup.j.sup..U=e(g,h).sup.a.z.sup.j.sup..V

(58) In a first case (“ok” branch in FIG. 4) where the equality is satisfied, corresponding to the case where U=V, then this signifies that the sub-string b.sub.1+1 . . . b.sub.j+l is identical to the keyword W. Indeed, U has the property that if U=V then b.sub.j+1 . . . b.sub.j+l=W. In an exemplary embodiment, in a following message sending step E44, an information message is sent to the decryption entity 11 so as to inform it of the presence of the keyword in the stream and of the position j+1 in the stream B at which the keyword has been found. In a following incrementing step E45, the current position j is incremented by one notch and the search for the keyword W continues from this new current position.

(59) In a second case (“nok” branch in FIG. 4) where the equality is not satisfied, the keyword W is different from b.sub.j+1 . . . b.sub.j+l since there exists at least one difference between the polynomials U and V. In an exemplary embodiment, in the following incrementing step E45, the current position j is incremented by one notch and the search for the keyword W continues from this new current position.

(60) The method makes it possible to detect the presence of keywords of any size, in any encrypted stream and at any location in this string. The detection of a keyword in a stream makes it possible not only to be informed of the presence of the keyword in the string but also to know the keyword's exact location in the stream.

(61) A decryption method, according to an exemplary embodiment, will now be described in conjunction with FIG. 5.

(62) In an initial step E50 of generating trapdoors, the entity for generating trapdoors 13 generates trapdoors for all the possible values of elementary data of a stream B. In the example described here of a stream of bits, two trapdoors are generated: one for a first keyword corresponding to the bit 0 and one for a second keyword corresponding to the bit 1. Note that in the case of a stream of bits, the generation of a single trapdoor, associated with one of the two keywords, is sufficient.

(63) In a following step E51 of sending the trapdoors, the entity for generating trapdoors 13 sends the previously generated trapdoors to the test entity 14.

(64) In a following test step E52, implemented when sending an encrypted stream C from the encryption entity 10 to the decryption entity 11, the test entity 14 implements the method for detecting a keyword such as described previously for the set of trapdoors that it has received previously. Thus, in accordance with an exemplary embodiment described, the decryption entity 11 is informed of the detection of each of the keywords, that is to say of each of the bits and of their position.

(65) In a following reconstructing step E53, the decryption entity 11 which knows the position of each of the keywords, in this instance the bits 0 and 1, reconstructs the plaintext stream. Note that in the case where a single trapdoor has been generated, for example for the keyword corresponding to the bit 0, the decryption entity 11 which receives from the test entity 14 the position of all the bits 0 in the stream B, sets the other bits of the stream to 1 and thus reconstructs the initial stream B.

(66) A device for generating trapdoors in a searchable encryption system, according to an exemplary embodiment will now be described in conjunction with FIG. 6.

(67) A device 60 for generating trapdoors is an item of computing equipment, such as a computer.

(68) The device 60 for generating trapdoors comprises: a processing unit or processor 601, or “CPU” (“Central Processing Unit”), intended to load instructions into memory, to execute them and to perform operations; a set of memories, including a volatile memory 602, or “RAM” (for “Random Access Memory”) used to execute code instructions, to store variables, etc., and a storage memory 603 of “EEPROM” type (“Electrically Erasable Programmable Read Only Memory”). In particular, the storage memory 603 is designed to store a software module for generating trapdoors which comprises code instructions for implementing the steps of the method for generating trapdoors such as is described previously. The storage memory 603 is also designed to store in a secure area the secret key K.sub.s of the searchable encryption system.

(69) The device 60 for generating trapdoors also comprises: a first generating module 604, designed to generate, for a trapdoor T associated with a keyword W which comprises l elementary data, W=w.sub.1 . . . w.sub.l, l randoms v.sub.1, v.sub.2, . . . , v.sub.l. The first generating module 604 is designed to implement step E301 of the trapdoor generating method such as described previously; a second generating module 605, designed to generate a polynomial V in an element z, dependent on the secret key, and of degree l in which a j-th coefficient of said polynomial, 1≤j≤l, is dependent on an encoding of the j-th elementary data item w.sub.j of the keyword defined in the secret key K.sub.s of the searchable encryption system and of a j-th random v.sub.j of the l randoms. The second generating module 605 is designed to implement step E302 of the method for generating trapdoors such as described previously; an optional sending module 606, designed to send the trapdoor T which comprises said polynomial h.sup.V associated with a random element h of a group of a bilinear environment, and the l randoms h.sup.v.sup.j associated with the random element of the group. The sending module 606 is designed to implement the optional step E31 of the method for generating trapdoors such as described previously. The sending module 606 appears dashed in FIG. 6.

(70) The first and second generating modules 604 and 605, and the sending module 606 are preferably software modules comprising software instructions for implementing the steps of the method for generating trapdoors of a searchable encryption system such as described previously.

(71) The invention therefore also relates to: a computer program comprising instructions for the implementation of the method for generating trapdoors such as described previously when this program is executed by a processor of the device for generating trapdoors, a readable recording medium on which is recorded the computer program described hereinabove.

(72) A searchable encryption device, according to an exemplary embodiment, will now be described in conjunction with FIG. 7.

(73) A searchable encryption device 70 is an item of computing equipment, such as a computer.

(74) The searchable encryption device 70 comprises: a processing unit or processor 701, or CPU, intended to load instructions into memory, to execute them and to perform operations; a set of memories, including a volatile memory 702, or RAM used to execute code instructions, to store variables, etc., and a storage memory 703 of EEPROM type. In particular, the storage memory 703 is designed to store a searchable encryption software module which comprises code instructions for implementing the steps of the searchable encryption method such as is described previously. The memory 703 is also designed to store the public key K.sub.p of the searchable encryption system;

(75) The searchable encryption device 70 also comprises: a first generating module 704, designed to generate a random a. The first generating module 704 is designed to implement step E23 of the searchable encryption method such as described previously; a second generating module 705, designed to generate, for any elementary data item b.sub.j, j=1 to n, of the stream B to be encrypted, the power of a monomial dependent on the public key (g.sup.x(b.sup.j.sup.).z.sup.j) and the random, said element being associated with a random element of a group g of a bilinear environment, said element associated with the random element of the group forming a first encryption data item (C.sub.j,1). The second generating module 705 is also designed to generate a shift factor g.sup.a.z.sup.j−1, dependent on the random and the public key, and associated with the random element of the group, said shift factor being representative of a position of said monomial in the encrypted stream C, said shift factor associated with the random element of the group forming a second encryption data item (C.sub.j,2). The ciphertext C of the data stream comprises, for any j=1 to n, the monomials generated and the associated shift factors. Stated otherwise, the ciphertext comprises the first and second encryption data items C.sub.j,1, C.sub.j,2. The second generating module 705 is designed to implement step E24 of the searchable encryption method such as described previously.

(76) The first and second generating modules 704 and 705 are preferably software modules comprising software instructions for implementing the steps of the searchable encryption method such as is described previously.

(77) The invention therefore also relates to: a computer program comprising instructions for the implementation of the searchable encryption method such as described previously when this program is executed by a processor of the searchable encryption device, a readable recording medium on which is recorded the computer program described hereinabove.

(78) A device for detecting a keyword in a stream, according to an exemplary embodiment, will now be described in conjunction with FIG. 8.

(79) A device 80 for detecting a keyword in a stream is an item of computing equipment, such as a computer.

(80) The device 80 for detecting a keyword in a stream comprises: a processing unit or processor 801, or CPU, intended to load instructions into memory, to execute them and to perform operations; a set of memories, including a volatile memory 802, or RAM used to execute code instructions, to store variables, etc., and a storage memory 803 of EEPROM type. In particular, the storage memory 803 is designed to store a software module for detecting a keyword in a stream which comprises code instructions for implementing the steps of the searchable encryption method such as is described previously;

(81) The device 80 for detecting a keyword in a stream also comprises: an obtaining module 804, designed to obtain a trapdoor T associated with the keyword, said trapdoor comprising l randoms h.sup.v.sup.i associated with a random element h of a group of a bilinear environment, and a polynomial V in an element z, dependent on the secret key and of degree l, said polynomial being associated with the random element of the group h.sup.V, an i-th coefficient of said polynomial, 1≤i≤l, being dependent on an encoding of the i-th elementary data item w.sub.i of the keyword defined in the secret key and an i-th random v.sub.i of the l randoms. In an exemplary embodiment where the device 80 for detecting a keyword is distinct from the entity for generating trapdoors 13, the obtaining module 804 receives the trapdoor T from the device 13 for generating trapdoors. The obtaining module 804 is designed to implement step E40 of the method for detecting a keyword such as described previously; a coupling and assembling module 805, designed to, starting from a current position j, and for any i=1 to l, calculate a coupling of the (j+i)-th element of the encrypt and of the i-th random of the trapdoor by means of a bilinear mapping (e), said bilinear mapping taking as input a first element g of a first group G1 and a second element h of a second group G2 and with values in a third group GT, and assembling the l couplings obtained, said assembling producing a first polynomial of degree l. The coupling and assembling module 805 is designed to implement step E41 of the method for detecting a keyword such as described previously; a coupling module 806, designed to, for any i=1 to l, calculate a coupling of the shift factor associated with the current position and of the polynomial V associated with the trapdoor, said coupling producing a second polynomial U of degree l. The coupling module 806 is designed to implement step E42 of the method for detecting a keyword such as described previously; a module 807 for comparing the first and second polynomials, designed to compare the first and second polynomials, equality of the two polynomials being representative of the presence of the keyword W in the stream B starting from the current position j. The comparing module 807 is designed to implement step E43 of the method for detecting a keyword such as described previously.

(82) The obtaining module 804, the coupling and assembling module 805, the coupling module 806 and the comparing module 807 are preferably software modules comprising software instructions for implementing the steps of the method for detecting a keyword in a stream such as is described previously.

(83) The invention therefore also relates to: a computer program comprising instructions for the implementation of the method for detecting a keyword in a stream such as described previously when this program is executed by a processor of the device for detection a keyword in a stream, a readable recording medium on which is recorded the computer program described hereinabove.

(84) The invention also pertains to a searchable encryption system 100 which comprises: a device for generating trapdoors 60, such as described previously, at least one searchable encryption device 70, such as described previously, and a device 80 for detecting a keyword in a stream such as described previously.

(85) Note that in an exemplary embodiment where the devices for generating trapdoors 60, and for detecting a keyword in a stream 80 are distinct, the trapdoor sending module 606 of the device for generating trapdoors 60 is present in the system.