`
`
`as) United States
`
`
`
`
`
`
`
`
`
`a2) Patent Application Publication co) Pub. No.: US 2011/0145594 Al
`
`
`
`
`
`
`
`
`
` JHOet al. (43) Pub. Date: Jun. 16, 2011
`
`
`
`
`US 20110145594A1
`
`
`
`
`
`
`
`(54) METHOD FOR PERFORMING SEARCHABLE
`SYMMETRIC ENCRYPTION
`
`
`
`
`
`(75)
`
`
`
`Inventors:
`
`
`
`
`
`
`
`Nam-Su JHO,Seoul (KR);
`
`
`
`
`Do-Won HONG, Daejeon (KR);
`
`
`
`
`Hyun-Sook CHO,Daejeon (KR)
`
`
`(73) Assignee:
`
`
`
`
`
`
`
`(21) Appl. No.:
`
`
`(22)
`Filed:
`
`
`(30)
`
`
`
`Dec. 16,2009
`
`
`
`Electronics and
`Telecommunications Research
`
`
`
`
`
`Institute, Daejeon-city (KR)
`
`12/962,047
`
`
`Dec.7, 2010
`
`
`
`Foreign Application Priority Data
`
`
`
`(KR) veeecccceeceee 10-2009-0125540
`
`
`
`
`
`
`Publication Classification
`
`
`
`
`
`
`
`
`
`
`
`(51)
`
`(52)
`
`(57)
`
`
`
`Int. Cl.
`
`
`(2006.01)
`GO6F 21/24
`
`
`
`UNS. Ce oceeccccccccccccccccscessesssssseeseeseseeseeseseeaes 713/189
`
`ABSTRACT
`
`
`
`
`
`Disclosed is a method for searchable symmetric encryption.
`
`
`
`
`
`
`
`The method for performing searchable encryption and
`
`
`
`
`
`
`
`
`searching for encrypted data includes: 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 trapdoorto be used
`
`
`
`
`
`
`
`
`
`
`to search the encrypted data by using the secret key and a
`
`
`
`
`
`
`
`
`keywordto be used for the searching; and searching a desired
`
`
`
`
`
`
`
`
`
`data using the generated trapdoor and the stored index.
`
`
`
` S100
`
`
`
`
`
`
`PREVIOUSLY PREPARE ENCRYPT AND GENERATE INDEX
` 5300
`5400
`
`
`
`S200
`
`
`
`
`
`
`(STORE IN SERVER)
`
`
`
`
`
`
`
`
`
`
`
`GENERATE TRAPDOOR
`
`
`
`
`
`
`
`
`
`SEARCH
`
`
`
`
`
`
`SEARCH USING NEW KEYWORD
`
`
`
`Page 1 of 8
`
`Netskope Exhibit 1015
`
`Page 1 of 8
`
`Netskope Exhibit 1015
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`
`Jun. 16,2011 Sheet 1 of 3
`
`
`
`US 2011/0145594 Al
`
`FIG.
`
`
`1
`
`
`
`
`
`
`
`PREVIOUSLY PREPARE
`
`5200
`
`
`
`ENCRYPT AND GENERATE INDEX
`
`
`(STORE IN SERVER)
`
`
`
`5100
`
`
`
`
`5300
`
`
`
`
`
`5400
`
`
`
`GENERATE TRAPDOOR
`
`
`
`SEARCH
`
`
`
`
`SEARCH USING NEW KEYWORD
`
`
`
`Page 2 of 8
`
`Netskope Exhibit 1015
`
`Page 2 of 8
`
`Netskope Exhibit 1015
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`
`Jun. 16,2011 Sheet 2 of 3
`
`
`
`US 2011/0145594 Al
`
`
`FIG. 2
`
`
`
`
`|
`Rio
`Ria
`
`1
`Ego
`R
`
`Roo
`
`Rot
`
`
`
`Roo
`
`R23
`
`
`
`
`
`
`
`
`
`
`Page 3 of 8
`
`Netskope Exhibit 1015
`
`Page 3 of 8
`
`Netskope Exhibit 1015
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`
`Jun. 16,2011 Sheet 3 of 3
`
`
`
`US 2011/0145594 Al
`
`
`FIG. 3
`
`
`
` |
`
`a
`
`|
`
`at]
`
`|
`
`at2
`
`to
`
`
`
`
`
`(16[OAR|RPTAR|S
`
`Page 4 of 8
`
`Netskope Exhibit 1015
`
`Page 4 of 8
`
`Netskope Exhibit 1015
`
`

`

`
`
`
`US 2011/0145594 Al
`
`
`
`Jun. 16, 2011
`
`
`
`METHOD FOR PERFORMING SEARCHABLE
`
`
`
`SYMMETRIC ENCRYPTION
`
`
`
`
`
`CROSS REFERENCE TO RELATED
`
`
`APPLICATIONS
`
`
`
`
`
`
`
`
`
`[0001] This application claims priority to Korean Patent
`
`
`
`
`
`
`
`
`Application No. 10-2009-0125540 and filed on Dec. 16,
`
`
`
`
`
`
`
`2009, the entire contents of which are herein incorporated by
`reference.
`
`
`
`
`BACKGROUND OF THE INVENTION
`
`
`
`
`
`
`
`
`
`1. Field of the Invention
`[0002]
`
`
`
`
`
`
`
`[0003] The present inventionrelates to amethodfor search-
`
`
`
`
`
`
`
`able symmetric encryption, and more particularly,
`to a
`
`
`
`
`
`
`methodfor searchable symmetric encryption capable of pro-
`
`
`
`
`
`
`
`viding efficient range search by using a linked graph.
`
`
`
`
`
`2. Description of the Related Art
`[0004]
`
`
`
`
`
`
`
`[0005] A modern society is changed into a society that
`
`
`
`
`
`
`
`
`
`
`digitalizes and stores all information and shares and uses the
`
`
`
`
`
`
`
`stored information through a network. Further, due to the
`
`
`
`
`
`
`
`
`increase in the amount of processed data and demands for
`
`
`
`
`
`
`
`various services, various specialized external storage space
`
`
`
`
`are being extensively utilized.
`
`
`
`
`
`
`
`
`[0006] Moreover, security of information stored in the
`
`
`
`
`
`
`
`
`external storage space has becomean issue. Security in the
`
`
`
`
`
`
`
`external storage space is different from when individuals
`
`
`
`
`
`
`managed information by oneself using an independentstor-
`
`
`
`
`
`
`
`
`
`age space. The reason forthis is that an information owneris
`
`
`
`
`
`
`
`
`fundamentally different from one that manages the external
`
`
`
`
`
`
`
`storage space. An access control technique or a key manage-
`
`
`
`
`
`
`
`
`ment technique whichis principally used to protect the infor-
`
`
`
`
`
`mation in a database is effective in preventing an external
`
`
`
`
`
`
`
`intruder, but the techniques cannot fundamentally prevent a
`
`
`
`
`
`
`
`
`manager of the external storage space from reading data
`
`
`
`
`
`stored in the corresponding storage means.
`
`
`
`
`
`
`
`
`[0007] Asaresult, data encryption may be used as a method
`
`
`
`
`
`
`
`for safely storing the information. That is, information to be
`
`
`
`
`
`
`
`stored in the external storage space is encrypted by using an
`
`
`
`
`
`
`
`encryption system proven to be secure. The encryption sys-
`
`
`
`
`
`
`
`
`
`tem having the proved safety ensures that an attacker who
`
`
`
`
`
`
`
`
`
`does not own a decryption key cannot acquire stored infor-
`
`
`
`
`
`
`
`
`mation from ciphertext. Therefore, even though the external
`
`
`
`
`
`
`
`
`intruderor the managerof the storing space access the stored
`
`
`
`
`
`
`
`
`ciphertext, they do not actually obtain any significant infor-
`
`
`
`
`
`mation. Meanwhile, encryption of information is a method
`
`
`
`
`
`
`
`for perfectly securing confidentially stored information, but
`
`
`
`
`
`
`
`the information encryption also disables many additional
`
`
`
`
`
`
`
`
`functions provided from the general database. That is, as the
`
`
`
`
`
`
`amount of stored information increase, various database
`
`
`
`
`
`
`
`
`functions are required to efficiently utilize and manage the
`
`
`
`
`
`
`
`stored information. Therefore, a method for simply encrypt-
`
`
`
`
`
`
`
`ing and storing the information is not applicable.
`
`
`
`
`
`[0008] A searchable encryption protocol is contrived to
`
`
`
`
`
`
`
`search for data including a predetermined keyword while
`
`
`
`
`
`
`ensuring the confidentiality of the encrypted informationlike
`
`
`
`
`
`
`
`
`the general encryption system. Since most of the various
`
`
`
`
`
`
`
`
`functions provided from the database are based on keyword
`
`
`
`
`
`
`
`search,the searchable encryption system is considered as one
`
`
`
`
`
`of the solutions to the above-mentioned problems.
`
`
`
`
`
`
`
`[0009]
`In the searchable encryption system, it is assumed
`
`
`
`
`
`
`
`
`
`that each document consists of several keywords, and the
`
`
`
`
`
`
`
`
`query is determined by keywords that the user wants to
`
`
`
`
`
`
`search. Because ciphertext in encryption systems reveals no
`
`
`
`
`
`
`
`information about an encrypted data, searchable encryption
`
`
`
`
`
`
`
`provides a clue for searching, whichis called an ‘index’. An
`
`
`
`
`
`
`
`
`index contains information aboutthe relations between key-
`
`
`
`
`
`
`
`
`words and encrypted data. However, an indexis also locked in
`
`
`
`
`
`
`
`
`order to keep it secret, and can only be opened by those
`
`
`
`
`
`
`
`possessing a special key, called a ‘trapdoor’. Since a search is
`
`
`
`
`
`
`
`
`
`executed by the database server, to conduct one, the user has
`
`
`
`
`
`
`
`
`to generate and handovera trapdoorto the server.
`
`
`
`
`
`
`
`[0010] Usually, searchable encryption consists of four
`
`
`
`
`
`
`
`algorithms: key generation, build index, trapdoor generation,
`
`
`
`
`
`
`
`
`
`and search. In the key generation step, the user chooses an
`
`
`
`
`
`
`
`encryption system and prepares other parameters including
`
`
`
`
`
`
`
`
`encryption and decryption keys. A set of data and system
`
`
`
`
`
`
`
`
`parametersare given to the build index algorithm as an input.
`
`
`
`
`
`
`
`
`The build index algorithm outputs encrypted data and
`
`
`
`
`
`
`
`
`indexes. Outputs of the build index algorithm are sent to the
`
`
`
`
`
`
`
`
`
`
`
`server andstored. Ifthe user wants to search for data, then the
`
`
`
`
`
`
`
`
`user runs the trapdoor generation algorithm. The keywords
`that the user wants to use in the search and the user’s secret
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`key are inputinto the trapdoorgeneration algorithm. After the
`
`
`
`
`
`
`
`
`
`trapdoor is given to the server, the server runs the search
`
`
`
`
`
`
`
`
`
`
`algorithm. The trapdoor and indexesare input for the search,
`
`
`
`
`
`
`
`and the result of the search algorithm is a set of documents
`
`
`
`
`
`
`
`corresponding to the queried keyword. Finally, the result of
`
`
`
`
`
`the search is given to the user.
`
`
`
`
`
`
`[0011] Basic searchable encryption providesa search algo-
`
`
`
`
`
`
`
`rithm that finds documents correspondingto just one specific
`
`
`
`
`
`
`
`keyword. However, this search algorithm is very limited and
`
`
`
`
`
`
`
`cannot satisfy various demandsthat naturally arise. There-
`
`
`
`
`
`
`fore, designing a searchable encryption with useful additional
`
`
`
`
`
`functions is an important goal in searchable encryption. Fre-
`
`
`
`
`
`
`quently mentioned additional functions are conjunctive key-
`
`
`
`
`
`
`
`word search, range search, ordering, size comparison, and
`
`
`
`
`
`
`
`arbitrary search etc. The present patent concentrates on the
`
`
`range search.
`
`
`
`
`
`
`[0012]
`Formally, a range searchis a search of documents of
`
`
`
`
`
`
`
`which corresponding keywords are included within a set of
`
`
`
`
`
`
`
`successive keywords, an interval, rather than as a single key-
`
`
`
`
`
`
`
`word. To achieve a range search regarding an interval[a, b]
`
`
`
`
`
`
`
`
`using ordinal searchable encryption,the user has to do simple
`
`
`
`
`
`
`
`
`keyword searches b-a+1 times repeatedly. This is a very inef-
`
`
`
`
`
`
`
`
`
`ficient and insecure method. Because the server, which actu-
`
`
`
`
`
`
`
`
`ally runs the search algorithm,trivially obtains information
`
`
`
`
`
`
`
`
`
`
`regarding the size of the range and can also divide the result
`
`
`
`
`
`
`
`into b-a+1 subsets, each subset actually corresponds to a
`
`
`single keyword.
`
`
`
`
`
`
`
`
`
`
`[0013] The research results for the range search are very
`
`
`
`
`
`
`
`
`
`infrequent until now. U.S.A.patentlaid open publication No.
`
`
`
`
`
`
`
`
`2005-014724 (System and Method for Fast Querying of
`
`
`
`
`
`
`Encrypted Databases) discloses a searchable encryption sys-
`
`
`
`
`
`
`
`
`
`
`tem supporting the range search for the encrypted data. This
`
`
`
`
`
`
`
`
`
`method uses a schemethat divides data into segments having
`
`
`
`
`
`
`
`
`
`
`any size and encrypts them into a segmentunit (data included
`
`
`
`
`
`
`
`
`in the same segment is encrypted by the same encryption
`
`
`
`
`
`
`
`key). The method further requires a post-processing process
`
`
`
`
`
`
`
`
`
`
`to removea false hit included in the searching result and has
`
`
`
`
`
`
`lower safety than the encryption method.
`
`
`
`
`
`
`
`[0014]
`“‘Conjunctive, Subset and Range Queries on
`
`
`
`
`
`
`
`
`Encrypted Data, TCC 2007, LNCS4392, pp 535-554, 2007”
`
`
`
`
`
`
`
`
`by Boneh,et al., discloses a safety model for a coupling
`
`
`
`
`
`
`
`
`keyword search, a subset search, and a range search and a
`
`
`
`
`
`
`
`searchable encryption system supporting various types of
`
`
`
`
`
`
`
`
`searches having safety verified by the model. The method
`
`
`
`
`
`
`
`
`
`
`
`Page 5 of 8
`
`Netskope Exhibit 1015
`
`Page 5 of 8
`
`Netskope Exhibit 1015
`
`

`

`
`
`
`US 2011/0145594 Al
`
`
`
`Jun. 16, 2011
`
`
`
`
`
`
`
`
`
`
`
`
`
`provides verifiable safety by a public key based design but
`
`
`
`
`
`
`
`
`requires a lot of time to perform bilinear and public key
`
`operation.
`
`
`
`
`
`“‘Searchable Symmetric Encryption Improved
`[0015]
`
`
`
`
`
`
`
`Definitions and Efficient Constructions,’ Proc of the ACM-
`
`
`
`
`
`
`
`
`CCS, Proc. of the 13th ACMCCS2006, pp. 79-88, 2006” by
`
`
`
`
`
`
`Curtmola et al., discloses a searchable encryption system
`
`
`
`
`
`
`
`
`based on a linked chain. The methodis very efficient in terms
`
`
`
`
`
`
`
`
`
`ofa searching speed but doesnotdisclose a further function of
`
`
`
`
`
`
`a range search, andthelike.
`
`SUMMARYOF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`
`[0016] The present invention proposes to solve the above
`
`
`
`
`
`problems. It is an object of the present invention to provide a
`
`
`
`
`
`
`method for searchable symmetric encryption providing an
`
`
`
`
`
`
`
`
`efficient range search by a linked graph by using only a simple
`
`
`
`
`
`one-wayfunction such as a hash function.
`
`
`
`
`
`[0017] A-searchable encryption is a cryptographical proto-
`
`
`
`
`
`
`
`
`col enabling a keyword search for encrypted data and
`
`
`
`
`
`
`
`
`encrypts and stores data, thereby makingit possible to easily
`
`
`
`
`
`
`
`
`search for desired data while maintaining security of data.
`
`
`
`
`
`
`[0018] The searchable encryption technology may be
`
`
`
`
`
`
`
`divided into a searchable symmetric encryption system and a
`
`
`
`
`
`
`
`
`searchable public key encryption system according the char-
`
`
`
`acteristics of the encryption system.
`
`
`
`
`
`
`[0019] A method for searchable symmetric encryption is
`
`
`
`
`
`
`
`designed based on symmetric encryption and is moreefficient
`
`
`
`
`
`
`
`
`
`
`than the public key method for encryption and search, such
`
`
`
`
`
`
`
`that it is suitable for a large-capacity database. However, since
`
`
`
`
`
`
`
`
`the method for searchable symmetric encryption uses the
`
`
`
`
`
`
`
`symmetric key scheme,it is disadvantageousin that only the
`
`
`
`
`
`
`
`
`
`
`owner(user) of the secret key can perform the encryption and
`
`
`
`
`
`
`
`search andit has a limitation in providing various additional
`
`
`
`
`
`
`
`
`functions. Research and development for the method for
`
`
`
`
`
`
`searchable symmetric encryption providing various addi-
`
`
`
`
`
`
`
`
`tional functions providedin the methodforthe current search-
`
`
`
`
`
`
`
`
`able public key encryption has actively progressed. The
`
`
`
`
`
`
`
`present patent provides the method for searchable symmetric
`
`
`
`
`
`encryption providing a range search function.
`
`
`
`
`
`
`[0020] The methodfor searchable symmetric encryption is
`
`
`
`
`
`
`
`
`configured to include four steps, which are a key generation
`
`
`
`
`
`
`
`
`step, a build index step, a trapdoor generating step, and a
`
`
`search step.
`
`
`
`
`
`
`
`
`
`
`[0021] The key generation step is a step that a usersetsall
`
`
`
`
`
`
`
`
`variables necessary for a system and prepares a secret key
`
`
`
`
`necessary for encryption by a user.
`
`
`
`
`
`
`
`
`
`
`[0022] The build index step is a step that the user encrypts
`
`
`
`
`
`
`
`
`
`
`a data using the secret key and generates an index to be used
`
`
`
`
`
`
`
`
`
`
`for later search. In this case, the generated ciphertext and
`
`
`
`
`
`
`
`index are stored in the external server (database).
`
`
`
`
`
`
`
`
`
`[0023] The trapdoor generating step is a step that the user
`
`
`
`
`
`
`
`
`generatesa trapdoorto be used for search of data by using the
`
`
`
`
`
`
`
`
`
`
`secret key of the user and the keyword to be used for the
`
`
`
`
`
`
`
`
`searching. The trapdoor may be designed not to obtain infor-
`
`
`
`
`
`
`
`
`mation on the keyword to be used for the searching by the
`
`
`
`
`
`
`
`
`
`
`server. The searchingstep is a step that the server searches for
`
`
`
`
`
`
`
`
`
`
`a data desired by a user by using the given trapdoorand the
`stored index.
`
`
`
`
`
`
`
`
`
`
`[0024] Atthe searchingstep, the server is designed to know
`
`
`
`
`
`
`
`
`
`
`whether the stored data are the data desired by user and not to
`
`
`
`
`
`
`
`know any information on a keyword searched by the user or
`contents of the stored data.
`
`
`
`
`
`
`
`
`
`
`
`[0025] The unit of information performing the index gen-
`
`
`
`
`
`
`
`
`eration and search is referred to as a keyword andthe range
`
`
`
`
`
`
`
`
`search means simultaneously searching for data conforming
`
`
`
`
`
`
`
`
`
`
`to all the keywords included in the given range (orinterval)
`
`
`
`
`
`
`
`
`through a one-time query. The simplest methodfor the user to
`
`
`
`
`
`
`
`perform the range search is a methodof performing a search
`
`
`
`
`
`
`
`
`
`several times by using each keyword included in the range but
`
`
`
`
`
`
`
`
`this is inefficient. Further, since the server knowsthe result
`
`
`
`
`
`
`
`and additional information of each keyword,there is a prob-
`
`
`
`
`
`
`
`
`lem in regards to a safety aspect. In order to solve the problem,
`
`
`
`
`
`the proposed methodis a range search.
`
`
`
`
`
`
`
`
`
`[0026] The present invention extends the linked list pro-
`
`
`
`
`
`
`
`posed by Curtmola,et al., in 2006,to the linked graph of the
`
`
`
`
`
`
`
`
`searchable symmetric encryption system that can search the
`
`
`
`range usingthis.
`
`
`
`
`
`
`
`[0027] According to the present invention, it can remark-
`
`
`
`
`
`
`
`
`
`ably reduce the calculation necessary for the encryption and
`
`
`
`
`
`
`
`
`the generation and searchof the trapdoorsince it uses only a
`
`
`
`
`
`
`
`
`simple calculation of the one-way function such as a hash
`
`
`
`
`
`
`
`
`function, etc., without using a complex public key calculation
`
`
`
`
`
`
`
`
`generally used in the existing range searching method. Fur-
`
`
`
`
`
`
`
`
`
`
`ther, the existing methods perform the search for all the
`
`
`
`
`
`
`
`
`
`indexes, while the present invention searches for only the
`
`
`
`
`
`
`
`indexes of data includedin the range to be searched by using
`
`
`
`
`
`
`
`
`the linked graph structure. As a result, the present invention
`
`
`
`
`
`
`
`may bereferred to the searchable encryption method more
`
`
`
`
`suitable for a large-capacity database.
`
`
`
`
`
`
`
`
`In other words, the present invention provides the
`[0028]
`
`
`
`
`
`
`
`range search function to efficiently improve the search time
`and the calculation.
`
`
`
`
`
`
`
`
`
`
`[0029]
`Further, the present invention provides the search-
`
`
`
`
`
`
`
`able encryption system suitable for the large-capacity data-
`base.
`
`
`
`
`
`
`
`
`[0030]
`Inaddition,the safety ofthe method accordingto the
`
`
`
`
`present invention is cryptographically verified.
`
`
`
`
`
`
`
`
`
`
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`
`
`
`
`
`
`FIG. 1 is a flow chart of a method for searchable
`[0031]
`
`
`
`
`
`
`symmetric encryption according to the present invention;
`
`
`
`
`
`FIG. 2 isa diagram showingdefinition ofan interval
`[0032]
`
`
`
`
`
`
`tree used in the present invention; and
`
`
`
`
`
`
`[0033]
`FIG. 3 is architecture of a linked tree used in the
`
`
`present invention.
`
`
`
`
`
`
`
`
`
`DETAILED DESCRIPTION OF THE PREFERRED
`
`
`
`EMBODIMENTS
`
`
`
`
`
`
`
`
`[0034] The present invention will be described below with
`
`
`
`
`
`
`reference to the accompanying drawings. Herein, the detailed
`
`
`
`
`
`description of a related known function or configuration that
`
`
`
`
`
`may makethe purposeof the present invention unnecessarily
`
`
`
`
`
`
`ambiguousin describing the present invention will be omitted
`
`
`
`
`
`
`Exemplary embodiments of the present invention are pro-
`
`
`
`
`
`
`
`
`vided so that those skilled in the art may more completely
`
`
`
`
`
`
`
`understandthe present invention. Accordingly, the shape, the
`
`
`
`
`
`
`
`size, etc., of elements in the figures may be exaggerated for
`
`
`explicit comprehension.
`
`
`
`
`
`[0035] Hereinafter, a method for searchable symmetric
`
`
`
`
`
`
`
`encryption according to the present
`invention will be
`described in detail.
`
`
`
`
`
`
`
`
`[0036] The basic architecture of the method for searchable
`
`
`
`
`
`
`symmetric encryption according to the present invention is
`
`
`
`
`
`
`shown in FIG. 1. The basic architecture is configured to
`
`
`
`
`
`
`
`include generating and previously preparing a secret key of a
`
`
`
`
`
`
`
`
`
`user (S100), encrypting data and generating indexesandstor-
`
`
`
`
`
`
`
`ing them ina database by a user (S200), generating a trapdoor
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page6 of 8
`
`Netskope Exhibit 1015
`
`Page 6 of 8
`
`Netskope Exhibit 1015
`
`

`

`
`
`
`US 2011/0145594 Al
`
`
`
`Jun. 16, 2011
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`i)], one
`iv) In a linked tree starting from A[f(t,
`[0055]
`by auser by using a given keyword (S300), and searching by
`
`
`
`
`
`
`
`
`
`
`“EMPTY”link is searched andthe valueofthe link is changed
`a server (computing device) (S400).
`
`
`
`
`
`
`
`
`
`
`to G, k)).
`[0037]
`In the present invention, the number of data to be
`
`
`
`
`
`
`
`
`
`
`
`
`
`stored is denoted as N and keywordsincluded in each data is
`For convenience,the linked tree generated by the
`[0056]
`
`
`
`
`
`
`
`
`
`
`
`
`represented as an integer value(all keywords may be consid-
`above method will be denoted as G,, for eacht,i.
`
`
`
`
`
`
`
`
`
`
`
`
`
`ered as a bit string having a predetermined length) from 1 to
`FIG. 3 is architecture of a linked tree used in the
`[0057]
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`R. For convenience, assume that R=2” is satisfied due to an
`present invention. Referring to FIG.3, the linked tree gener-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`existence of any integer r. Further, assumethat each data has
`ated by the above methodis presented as an example.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`an integer from 1 to N as an identifier of data.
`[0058]
`6. Connection of an externallink: the user performs
`
`
`
`
`
`
`
`
`
`
`
`[0038] Thekey generation step ofthe user (100) determines
`the following processon all R,[a,b]Str, OSd=2’-1).
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a secret key k and a one-way function f: rx{0,1}’ {0,1}, h:
`[0059] When d is even number, G,,, Grasis +++» Gps is
`
`
`
`
`
`
`
`
`
`
`
`
`rx{0,1}’+{0,1}” to be used in encrypting the symmetric
`concatenated in an ascendingorderusing G,, as a start-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`encryption system E (use the secret key having awbit length)
`ing point. In other words, (f(t,i+1), h(t,i+1)) is stored at
`
`
`
`
`
`
`
`
`
`one of the ‘EMPTY’links of G.
`
`
`
`and data, where s=log(rx(N+R)). The secret key k and the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`one-way function f, h are secret information knownto only
`[0060] When dis an odd number, G,,,G,,_;,...,G,, are
`the user.
`
`
`
`
`
`
`concatenated in a descending order by using G, as a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`[0039] The index (A) generated in the build index step
`starting point. In other words, (f(t,i-1), h(t,i-1)) is stored
`
`
`
`
`
`
`
`
`
`
`
`
`(200)is an array formed of rx(N+R) elements and has a form
`at one of the ‘EMPTY’links of G,,.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ofAfi]J=dD,, (LD,, LK,), (RD,, RK,)). ID, represents an iden-
`7. An empty element among the elements of the
`[0061]
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tifier of the data stored in the element and (LD,, LK,) and
`array A andBis filled with randomly generated value. Finally,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(RD, RK,) are two linkages indicating next elements. A
`each element A[j] is encrypted by using B[j] as a secretkey. In
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`method configuring the index (A) is as follows. For conve-
`other words, E,,,,(A[j]) is computed. A[j] is replaced with
`
`
`
`
`
`
`
`
`
`nience, § is a set of all the data, S, is a set of data including
`Egy(AGD-
`
`
`
`
`
`
`
`
`keywordsi (ie {1, 2, ... , R}).
`[0062]
`8. Array B is deleted.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`1. The user configures an array A andinitializesall
`[0040]
`[0063] Each data D,is encrypted using the user’s secret key
`the values of each element to ‘EMPTY’or 0.
`
`
`
`
`
`
`
`
`
`
`
`
`
`k separately from the index and the index andthe ciphertextis
`
`
`
`
`
`
`
`
`[0041]
`2. The user generates an array B including elements
`transmitted to the server to be stored.
`
`
`
`
`
`
`
`
`
`
`
`
`with the same numberto A. The array B is a temporary array
`
`
`
`
`
`
`
`
`[0064] At the trapdoor generating step 300, the user gener-
`in which each elementhas a size ofw bits andis initialized as
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ates the trapdoorfor any search range[a, b].
`“EMPTY?
`
`
`
`
`
`
`
`
`
`[0065]
`1. the userfirst searches te{1, 2, ...,r} suitable for
`
`
`
`
`3. Separating interval
`[0042]
`
`
`[a, b] as follows.
`
`
`
`
`
`
`[0043]
`Set the initial interval R,)=[1, R]
`
`
`
`
`
`
`
`
`
`
`
`
`[0066]
`it is initialized to t=1, Rp=[1,R]=[a,, bol.
`[0044]
`For te{1, 2,..., r}, the following work is per-
`
`
`
`
`
`
`
`formed from t=1 to t=r. However, d=0,..., 2’-1.
`
`
`
`
`
`
`i) For an interval R,_,-[a, b], compute
`[0045]
`
`
`
`
`E,= [= vee |
`
`
`
`
`
`
`
`
`
`
`
`
`
`Brad = l
`
`
`
`a+b
`
`2 j
`
`
`
`
`
`
`
`
`
`
`is calculated and if E, E[a, b], t value is stored and ends.
`
`
`
`
`
`
`
`IfE<a, thena=E,, b=b,_, are set. Otherwise (i.e.
`[0067]
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ea), a=, b=E,, are set. After being changed into
`[0046]
`ii) Separate R,, , into two sub-intervals, R,.#-[a,
`
`
`
`
`
`
`
`
`
`t=t+1, it is returned to the abovestep.
`FE.1al and Ryoaei En atl, bj.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`2. Theuser calculates the trapdoor witht obtained at
`[0068]
`[0047]
`FIG. 2 isa diagram showingdefinition ofan interval
`
`
`
`
`
`
`
`
`tree used in the present invention. Referring to FIG. 2, R,,.4
`step 1.
`is divided into two sub-intervals from t=1 to t=r.
`
`
`
`
`
`
`
`
`Trapdoor=((ft,a),h(t, @)),(At 8),ke 8)))
`
`
`
`
`
`
`
`
`[0048]
`4. Indication ofa starting point: for eacht, 1(1St=r,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`[0069]
`3. The above obtainedt has the following character-
`1=iSR), f(t, 1) is calculated andA[f(t, 1)] is searched. A[f(t, i1)]
`
`
`
`
`
`
`
`
`istics.
`
`is reservedas a starting pointfor a t-th layer ofa keyword i. In
`
`
`
`
`
`
`
`
`
`
`
`
`
`other words, a value of ID,,,) is changed from ‘EMPTY’to
`[0070] When [a, b] is divided by two sub-intervals [a,
`
`
`
`
`
`
`
`
`
`
`
`E,],[E,+1,b], each sub-interval is included in the two
`“NONP’andh(t, i) is stored in B[f(t, 1)].
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`consecutive intervals such as [a,E,|CR,,, [E,+1,b]
`5. For each t, i 1St=r, 1SiSR), S,,=S,is defined
`[0049]
`
`
`
`
`
`
`
`
`
`
`
`
`ER,a1 Reo Reay1 are intervals defined at the build
`and the following process is performed.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`indexstep) In addition, R,,is defined as the linked chain
`[0050] A data D is optionally selected in S,, and is stored
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`in a right direction and R,4,, is defined as the linked
`in IDg,% and data D is deleted from the S,,. If S,,; is an
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`chain inaleft direction, which each has E,and E,+1 as an
`empty set, all the following processes are omitted and
`
`
`
`
`
`
`end point.
`progresses to the next t andi.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`[0071] Therefore, when searching for the value of the two
`[0051] The followingis repeated until S,, is an empty set.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`linked chains starting from a and b endingat E, and E,+1, all
`1)Select a data DinS,, randomly, and D is deleted in
`[0052]
`
`
`
`
`
`S.
`
`data includedin [a, b] can be searched.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`[0072] At the searching step (400), assumethat the server
`[0053]
`11) ‘EMPTY’ element A[j] is randomly selected
`
`
`
`
`
`
`
`
`
`
`
`
`
`receives the trapdoor ((f(t,a),h(t,a)), (f(t,b),h(t,b))) from the
`among, elements of the array A and randomwbitkey k, is
`user.
`
`
`generated.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`iti) The identifier ofD is stored in ID, andk, is stored
`[0054]
`[0073] The serverfirst searches A[f(t,a)] at the array A and
`
`
`
`
`
`
`
`
`in Bij].
`decrypts A[f(t,a)] by using h(t,a) as a decryption key.
`
`
`
`
`
`
`Page 7 of 8
`
`Netskope Exhibit 1015
`
`Page 7 of 8
`
`Netskope Exhibit 1015
`
`

`

`
`
`
`US 2011/0145594 Al
`
`
`
`Jun. 16, 2011
`
`
`
`
`
`
`
`
`
`
`
`4. The method for performing searchable encryption and
`
`
`
`
`
`
`
`searching for encrypted data according to claim 1, wherein
`
`
`
`
`
`
`
`
`the generated index (A) is an array formed of rx(N+R)ele-
`
`
`
`
`
`
`ments (where N is the numberofdata to be encrypted, R is a
`
`
`
`
`
`
`
`maximum integer value defining a keyword included in each
`
`
`
`
`
`
`
`
`data, and, r is an integer satisfying R=2”) and has a form of
`
`
`
`
`
`
`
`AiJ=dD,, (LD,, LK,), (RD,, RK,)) [where ID,is an identifier
`
`
`
`
`
`
`
`
`
`stored in the element and (LD,, LK,) and (RD,, RK,) are two
`
`
`
`
`
`
`
`
`
`links indicating next elements] at the encrypting the data and
`
`
`
`
`the generating the index.
`
`
`
`
`
`
`
`5. The method for performing searchable encryption and
`
`
`
`
`
`
`searching for encrypted data according to claim 4, wherein
`
`
`
`
`
`
`the generating the index (A) comprising:
`
`
`
`
`
`generating an array B having the same numberof elements
`
`
`
`
`
`as an array A configured by the user; and
`
`
`
`
`
`
`
`
`
`initializing all the values of each element for the arrays A
`and B.
`
`
`
`
`
`
`
`
`
`6. The method for performing searchable encryption and
`
`
`
`
`
`
`
`searching for encrypted data according to claim 5, wherein
`
`
`
`
`
`
`
`
`each element of the array B has a size of A bit and is a
`
`
`
`
`
`
`temporary array for storing an encryption key.
`
`
`
`
`
`
`
`7. The method for performing searchable encryption and
`
`
`
`
`
`
`searching for encrypted data according to claim 5, wherein
`
`
`
`
`
`
`
`the generating the index (A) further comprising:
`
`
`
`
`
`
`setting the initial interval Ry,=[1, R]; and
`
`
`
`
`for te{1, 2, ..., r}, computing
`
`
`
`
`
`
`
`
`
`
`
`
`
`[0074] Assuming that the decrypted elementis A[v]=UID,,
`
`
`
`
`
`
`
`
`(LD,, LK,), (RD,, RK,,), b,), ID, is included in the search
`
`
`
`
`
`
`
`
`results and the search is performedfor each link.
`
`
`
`
`
`
`
`
`In other words, A[LD,] is decrypted with LK,, and
`[0075]
`
`
`
`
`
`
`
`
`
`the storedidentifier is included in theresult list. This process
`
`
`
`
`
`
`
`
`
`is continued until all
`the links starting from A[v] has
`
`
`
`
`
`
`
`
`
`“EMPTY”value. Similarly, the search for the linked chain
`
`
`
`
`
`
`
`starting from A[f(t,b)] is performed. Finally, the indexesof all
`the searched data are transmitted to the user.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`[0076]
`Some steps of the present invention can be imple-
`
`
`
`
`mented as a computer-readable code in a computer-readable
`
`
`
`
`
`
`recording medium. The computer-readable recording media
`
`
`
`
`
`
`
`includeall types of recording apparatuses in which data that
`
`
`
`
`
`
`
`can be read by a computer system is stored. Examples of the
`
`
`
`
`
`
`computer-readable recording media include a ROM, a RAM,
`
`
`
`
`
`
`
`a CD-ROM, a CD-RW, a magnetic tape, a floppy disk, an
`
`
`
`
`
`
`
`
`HDD,an optical disk, an optical magnetic storage device,etc.
`
`
`
`
`
`
`and in addition, include a recording medium implemented in
`
`
`
`
`
`
`
`
`the form ofa carrier wave (for example, transmission through
`
`
`
`
`
`
`
`the Internet). Further, the computer-readable recording media
`
`
`
`
`
`
`
`are distributed on computer systems connected through the
`
`
`
`
`
`
`
`network, and thus the computer-readable recording media
`
`
`
`
`
`
`
`maybestored and executed as the computer-readable code by
`a distribution scheme.
`
`
`
`
`
`
`
`
`
`
`[0077] As described above, the exemplary embodiments
`
`
`
`
`
`
`
`
`have been described andillustrated in the drawings and the
`
`
`
`
`
`
`
`
`
`description. Herein, specific terms have been used, but are
`
`
`
`
`
`
`
`
`
`just used for the purpose of describing the present invention
`
`
`
`
`
`
`
`
`
`
`and are not used for qualifying the meaning or limiting the
`
`
`
`
`
`
`
`scope of the present invention, which is disclosed in the
`
`
`
`
`
`
`appended claims. Therefore, it will be appreciated to those
`skilled in the art that various modifications are made and other
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`and separating R,_, ., into two sub-intervals R,,[a, E,_1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the
`equivalent embodiments are available. Accordingly,
`and R,oai=l[E~1,at1, b] for R,,[a,b] from t=1 to t=r
`
`
`
`
`
`
`
`
`
`
`actual technical protection scope of the present invention
`(where d=0,..., 2’-1).
`
`
`
`
`
`
`
`
`
`
`