Specification
A METHOD, SYSTEM, AND COMPUTER-READABLE MEDIUM FOR PROVIDING A SEARCHING OVER ENCRYPTED KEYWORDS IN A
DATABASE
FIELD OF THE INVENTION
[0001] The present invention relates to the field of searchable encryption. In particular, the present invention provides a computer-implemented method, system and computer readable medium for providing a searching over encrypted keywords in a database.
BACKGROUND OF THE INVENTION
[0002] The advent of storage as a service being provided by the cloud providers and facilitating efficient analytics over it, has opened an entire new area of research over methods for secure data storage and efficient search and retrieval. Numerous works have been done over it with Boneh et al's method for trapdoor generation and corresponding search pioneering in the area. Boneh's method was based on double hashing of the keyword for trapdoor generation. The Park et al's scheme improvised the trapdoor generation by providing a generation mechanism comprising of usage of a single hash function over the keyword. But all these schemes suffer from offline key word guessing attacks. The trapdoors are generated statically i.e. same trapdoor generated every time for a particular key word making it vulnerable to brute force attack over the limited range of dictionary words by a misfeasor, masquerader or clandestine user.
[0003] The radical work for architectural design framework was proposed in the cryptographic cloud storage scheme. In the existing schemes, to search for any keyword the data user supplies the keyword to the data managing authority to get a corresponding trapdoor which is searched at the cloud database. Since keywords form a very limited range of dictionary words, the present schemes are liable to offline keyword guessing attack, i.e. the user can sniff a trapdoor from the network and then by applying brute force attack over it, they can guess the corresponding keyword.
[0004] The existing processes have limitations such as searchable encryption uses same trapdoor (unique static), for same keyword to be searched for i.e. there is a one to one mapping between the keyword and trapdoor. The existing methods are vulnerable to online and offline dictionary attacks. All existing schemes are based on single trapdoor search.
[0005] Thus, there is a need to overcome the problems of the existing technologies. Therefore, the present inventors have developed a computer-implemented method, system and computer-readable medium for providing a searching over encrypted keywords in a database, which would provide secure search by generating one time trapdoor i.e. trapdoor is changed dynamically every time for the same keyword.
SUMMARY OF THE INVENTION
[0006] According to one aspect of the invention there is provided a computer implemented method executed by one or more computing devices for providing a searching over encrypted keywords in a database. The method comprises the steps of generating at least one keyword, generating a plurality of different encrypted keywords corresponding to said keyword, storing said at least one encrypted keyword in said database; generating a plurality of different trapdoors for said keyword, verifying said plurality of different trapdoors with said plurality of different encrypted keywords corresponding to said keyword and determining said keyword if said plurality of different trapdoors match with one said encrypted keyword corresponding to said keyword else determining said keyword is not found.
[0007] According to another aspect of the invention there is provided a system for providing a searching over encrypted keywords in a database. The system comprises a memory and a processor operatively coupled to the memory. The processor configured to perform the steps of generating at least one keyword, generating a plurality of different encrypted keywords corresponding to said keyword, storing said at least one encrypted keyword in said database; generating a plurality of different trapdoors for said keyword, verifying said plurality of different trapdoors with said plurality of different encrypted keywords corresponding to said keyword and determining said keyword if said plurality of different trapdoors match with one said encrypted keyword corresponding to said keyword else determining said keyword is not found.
[0008] According to another aspect of the invention there is provided a computer-readable code stored on a non-transitory computer-readable medium that, when executed by a computing device, performs a method for providing a searching over encrypted keywords in a database. The method comprises the steps of generating at least one keyword, generating a plurality of different encrypted keywords corresponding to said keyword, storing said at least one encrypted keyword in said database; generating a plurality of different trapdoors for said keyword, verifying said plurality of different trapdoors with said plurality of different encrypted keywords corresponding to said keyword and determining said keyword if said plurality of different trapdoors match with one said encrypted keyword corresponding to said keyword else determining said keyword is not found.
BRIEF DESCRIPTION OF THE DRAWINGS
[0009] Features, aspects, and advantages of the present invention will be better understood when the following detailed description is read with reference to the accompanying drawings in which like characters represent like parts throughout the drawings, wherein:
[0010] FIG. 1 shows a three-tier architecture for data outsourcing model;
[0011] FIG.2shows a flowchart depicting a method for providing a searching over encrypted keywords in a database;
[0012] FIG.3 shows an environment in which the present invention can be practiced, in accordance with an embodiment of the present invention; and
[0013] FIG.4 shows a generalized computer network arrangement, in one embodiment of the present technique.
DETAILED DESCRIPTION OF THE INVENTION
[0014] While system and method are described herein by way of example and embodiments, those skilled in the art recognize that system and method for providing a searching over encrypted keywords in a database are not limited to the embodiments or drawings described. It should be understood that the drawings and description are not intended to be limiting to the particular form disclosed. Rather, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the appended claims. Any headings used herein are for organizational purposes only and are not meant to limit the scope of the description or the claims. As used herein, the word "may" is used in a permissive sense (i.e., meaning having the potential to) rather than the mandatory sense (i.e., meaning must). Similarly, the words "include", "including", and "includes" mean including, but not limited to.
[0015] The following description is full and informative description of the best method and system presently contemplated for carrying out the present invention which is known to the inventors at the time of filing the patent application. Of course, many modifications and adaptations will be apparent to those skilled in the relevant arts in view of the following description in view of the accompanying drawings and the appended claims. While the system and method described herein are provided with a certain degree of specificity, the present technique may be implemented with either greater or lesser specificity, depending on the needs of the user. Further, some of the features of the present technique may be used to advantage without the corresponding use of other features described in the following paragraphs. As such, the present description should be considered as merely illustrative of the principles of the present technique and not in limitation thereof, since the present technique is defined solely by the claims.
[0016] As a preliminary matter, the definition of the term "or" for the purpose of the following discussion and the appended claims is intended to be an inclusive "or" That is, the term "or" is not intended to differentiate between two mutually exclusive alternatives. Rather, the term "or" when employed as a conjunction between two elements is defined as including one element by itself, the other element itself, and combinations and permutations of the elements. For example, a discussion or recitation employing the terminology "A" or "B" includes: "A" by itself, "B" by
itself and any combination thereof, such as "AB" and/or"BA." It is worth noting that the present discussion relates to exemplary embodiments, and the appended claims should not be limited to the embodiments discussed herein.
[0017] FIG.l shows three-tier architecture for data outsourcing model. The data storage on cloud is neither a single user task nor a onetime involvement. It involves multiple users and a number of times data is to be stored, used and modified. Interfaces for inter user interactions are also essential to provide an efficient architecture. The architecture used for demonstration of the concept involves three parties, and hence is termed as three-tier architecture. The different components are a Data User (102), a Data Owner (104) and a Data Provider (106).
[0018] The Data User
[0019] The data user (102) consists of an individual(s) or the corporation accessing the data. Considering the healthcare scenario, the user list consists of Patient, Doctor, Hospital, Pharmaceutical Company, Diagnostic labs, Research Scientists, Health Ministry, Blood bank and related organizations. The data user communicates with the Data Owner and the Data provider as per the requirement.
[0020] The data user (102) provides a keyword W (108) that he wants to search for, to the data
owner (104).The data user (102) receives back the trapdoor Tw (110) and using it, the data user
looks into the data provider (106) for a particular keyword and the search results are returned in encrypted form (112).The data user may then request for the decryption key (114) or use the one if he already possesses it, for decrypting the selected files.
[0021] Data Owner
[0022] Data owner (104) is the enterprise which owns the data and has outsourced it to the data provider (106). The data provider (106) can be cloud provider, database provider, etc. Data owner (104) has the function to encrypt the data, outsourcing it for storage, providing trapdoor for searching options and distribution of appropriate keys for decryption of data to authorized users only. The three essential components of it are data (116), trapdoor generator (118) and key
distributor (120). The data component stores the encrypted data at the provider. The trapdoor generator (118) receives the keyword to be searched for from the data user and generates the corresponding trapdoor to the user. The key distributor component (120) as the name depicts performs the task of maintaining the public parameters, decryption keys and distributing them to the users when asked upon. The data verifier component (not shown in figure), if included checks the integrity of the data. It checks if the data stored at the provider has been modified by anyone unauthorized to do so. It is implemented by storing an additional tag with the data files which is changed on every change in the file, and hence keep track of the integrity of the data. The tag can be a checksum which is intact for a given file. The detailed description of integrity verification has been omitted here. The major focus here is on the trapdoor generation and searching in the three tier architecture.
[0023] Data Provider
[0024] The data provider (106) stores the data. It performs the function of storing the data provided by the data owner (104). It also enables data search by the user by comparing the trapdoor with the data field and return the results in an encrypted format.
[0025] FIG.2 shows a flowchart depicting a method for providing a searching over encrypted keywords in a database. The method comprises the steps to generate one or more keywords (202) for the searchable data. After preparing keywords, generate a plurality of different encrypted keywords (204) corresponding to the keyword. Then, store the encrypted keywords in the database (206). The present invention provides one time trapdoor generation i.e. generate a plurality of different trapdoors (208) for the keyword of searchable data. Then, verify (210) the plurality of different trapdoors with the plurality of different encrypted keywords corresponding to the keyword. If the plurality of different trapdoors match (212) withone said encrypted keyword corresponding to the keyword then determine that the keyword is found (214) or else determine that the keyword is not found (216) in the database.
[0026] FIG.3 shows an environment in which the present invention can be practiced, in accordance with an embodiment of the present invention. The system (300) comprises a key
generation module (302), an encryption module (304), a trapdoor generator module (306), a search module (308), a verification module (310) and a decryption module (312).
[0027] The key generation module (302) performs key generation process and provides the required keys for encryption and decryption.
[0028] Key Generation
[0029] Based on a security parameter k, system parameters and keys are generated. Gl and G2
are two cyclic group of some prime order n with an admissible pairing "e: Gt X G± -» G2
[0030] A generator Pa for Gt is generated.Three cryptographic hash functionsifj, Hz and if3 are
selected where Hx ■ {0,1}* -> {0,1}* and H2-.G2-+ {0,1}* andff3 : {0,1}* -» Gv
[0031] Consider the message as M and cipher text as C. Randomly st is selected as the secret key,
where st€Z/qZ.
[0032] Pm = H3{lD) (1)
[0033] Where PiDis the encryption key andID is the user identity used for identity based
encryption. Also the decryption key is Ka where Kd = Pm • st (2)
[0034] The Public key island is defined as Qt = stP^. (3)
[0035] The encryption module (304) performs the operation of the encryption of the data and keywords i.e. generate a plurality of different encrypted keywords corresponding to the keyword.
[0036] Encryption
[0037] For encryption, randomly select r such thatr £ ZfqZ. The message is M, keyword is W and the cipher text is C.
[0038] C is defined asC = [ VJrN] (4) [0039] Where,P = M © H2(2(Pm, QtY) (5)
[0040] / = rH1(w)Po + rQand N = r-Po (6)
[0041] The message M is stored in the above form C at the data provider. V is the encryption of the message M, using identity based encryption. J and N components of C are useful for keyword search.
[0042] The trapdoor generator module (306) performs the operation of trapdoor generation i.e. generate a plurality of different trapdoors (208) for the keyword.
[0043] Trapdoor generation
[0044] The most important component for the architecture is the generation of trapdoor and its
security. For any keyword 'W the user wants to search for, a trapdoor TWis generated. The
architecture uses the approach of one time trapdoor, so even for same keyword new trapdoor is generated every time. So the possibility of online keyword guessing attack is eliminated. The trapdoor generation method also introduces a random parameter 'y' and using 'y' it generates one time trapdoor and breaking it is a discrete logarithmic problem, thus eliminating any possibility for offline keyword guessing attack. This random parameter generated leads to new trapdoor every time, since for each search a new random parameter is generated.
[0045] For any keyword 'W the user wants to search for, it sends 'W to the data owner (104). The trapdoor TWis generated by the data owner (104) and sent back to the data user (102). For
keyword ' W Trapdoor Tw is defined as
[0046] Tw = [y (H1(W) + stT)-1P0,y ■ P0] (7)
[0047] Where y is the random parameter, selected such that y e Z/qZ.
[0048] For simplicity of expression trapdoor may be written as Tw = [L,K] (8)
[0049] The search module (308) performs the operation of search in the database.
[0050] Search
[0051] The architecture provides for searchable encryption using one time trapdoor. To search for
a keyword W, the user sends the word to the data owner (104), and receives back the trapdoor Tw.
It then sends the trapdoor to the data provider (106) and search is performed over there. All the files which match the search are given but in encrypted form only. The user can decrypt the files using the decryption key which it has or can get from the data owner. The mechanism for search is explained.
[0052] The trapdoor send to the data provider is Tw where,
Tw = [L,A].
[0053] The provider checks if e,ff) = e(/,L) (9)
[0054] If the expression evaluates to true then the keyword matches and the file is returned otherwise not.
[0055] The verification module (310) performs the operation of verification of the plurality oi different trapdoors with the plurality of different encrypted keywords corresponding to the keyword.
[0056] Verification
[0057] The search approach mentioned is consistent. The requirement being that for any keyword
W and trapdoor TWif the search evaluates to true then, the concerned keyword is the one which is being searched for.
[0058] The consistency of the search using trapdoor is checked as:e(/,L) [0059] Substituting the values for J and L
[0060] =e(rH1(W)P0+rCt,y(H1(W) + st)1 P0) [0061] It is known thatQt = st -PQ. Using it, [0062] = e{THx{W}Pa +rst • P*y{Hx{W) + sty*- ■ Pa) [0063] = i{rCH±(W) +- st} ■ P^H^W) + st)-% ■ **o) [0064] = e(r ■ PQ ,y ■ P^W*^ -tn
Documents
Application Documents
| # |
Name |
Date |
| 1 |
4463-CHE-2012 FORM-3 26-10-2012.pdf |
2012-10-26 |
| 1 |
4463-CHE-2012-FORM 13 [12-10-2020(online)].pdf |
2020-10-12 |
| 2 |
4463-CHE-2012-RELEVANT DOCUMENTS [12-10-2020(online)].pdf |
2020-10-12 |
| 2 |
4463-CHE-2012 FORM-2 26-10-2012.pdf |
2012-10-26 |
| 3 |
4463-CHE-2012-FER.pdf |
2019-11-14 |
| 3 |
4463-CHE-2012 FORM-1 26-10-2012.pdf |
2012-10-26 |
| 4 |
4463-CHE-2012 DRAWINGS 26-10-2012.pdf |
2012-10-26 |
| 4 |
4463-CHE-2012 FORM-18 19-11-2014.pdf |
2014-11-19 |
| 5 |
4463-CHE-2012 DESCRIPTION (COMPLETE) 26-10-2012.pdf |
2012-10-26 |
| 5 |
4463-CHE-2012 FORM-1 30-07-2014.pdf |
2014-07-30 |
| 6 |
4463-CHE-2012 CLAIMS 26-10-2012.pdf |
2012-10-26 |
| 6 |
4463-CHE-2012 CORRESPONDENC OTHERS 30-07-2014.pdf |
2014-07-30 |
| 7 |
4463-CHE-2012 ABSTRACT 26-10-2012.pdf |
2012-10-26 |
| 7 |
4463-CHE-2012 FORM-3 04-02-2014.pdf |
2014-02-04 |
| 8 |
4463-CHE-2012 CORRESPONDENCE OTHERS 26-10-2012.pdf |
2012-10-26 |
| 9 |
4463-CHE-2012 ABSTRACT 26-10-2012.pdf |
2012-10-26 |
| 9 |
4463-CHE-2012 FORM-3 04-02-2014.pdf |
2014-02-04 |
| 10 |
4463-CHE-2012 CORRESPONDENC OTHERS 30-07-2014.pdf |
2014-07-30 |
| 10 |
4463-CHE-2012 CLAIMS 26-10-2012.pdf |
2012-10-26 |
| 11 |
4463-CHE-2012 DESCRIPTION (COMPLETE) 26-10-2012.pdf |
2012-10-26 |
| 11 |
4463-CHE-2012 FORM-1 30-07-2014.pdf |
2014-07-30 |
| 12 |
4463-CHE-2012 DRAWINGS 26-10-2012.pdf |
2012-10-26 |
| 12 |
4463-CHE-2012 FORM-18 19-11-2014.pdf |
2014-11-19 |
| 13 |
4463-CHE-2012-FER.pdf |
2019-11-14 |
| 13 |
4463-CHE-2012 FORM-1 26-10-2012.pdf |
2012-10-26 |
| 14 |
4463-CHE-2012-RELEVANT DOCUMENTS [12-10-2020(online)].pdf |
2020-10-12 |
| 14 |
4463-CHE-2012 FORM-2 26-10-2012.pdf |
2012-10-26 |
| 15 |
4463-CHE-2012-FORM 13 [12-10-2020(online)].pdf |
2020-10-12 |
| 15 |
4463-CHE-2012 FORM-3 26-10-2012.pdf |
2012-10-26 |
Search Strategy
| 1 |
Search_Strategy_4463_CHE_2012_04-11-2019.pdf |