Patent ID: 8812867

Claim:
A method for performing searchable encryption and searching for encrypted data, comprising: setting all necessary variables and preparing a secret key necessary for encryption; encrypting a data using the secret key and a given data and generating an index to be used for later search, to store the encrypted data and the index; generating a trapdoor to be used in searching for the encrypted data by using the secret key and a keyword for the searching; and searching for a desired data using the generated trapdoor and the stored index, wherein, when encrypting the data and generating the index, the generated index (A) is an array formed of r×(N+R) elements, where N is the number of data to be encrypted, R is a maximum integer value defining a keyword included in each data, and r is an integer satisfying R=2 r and has a form of A[i]=(ID i , (LD i , LK i ), (RD i , RK i ), where ID i is an identifier stored in the element and (LD i , LK i ) and (RD i , RK i ) are two links indicating next elements, wherein generating the index (A) comprises: generating an array B having the same number of elements as an array A configured by the user; initializing all the values of each element for the arrays A and B, setting the initial interval R 0,0 =[1, R]; and for tε{1, 2, . . . , r}, computing E t - 1 , d = ⌊ a + b 2 ⌋ and separating R t-1,d into two sub intervals R t,2d =[a, E t-1,d ] and R t,2d+1 =[E t-1,d +1, b] for R t-1,d =[a,b] from t=1 to t=r (where d=0, . . . , 2 t −1).