KR101232385B1 - Searchable Symmetric Encryption Method and System - Google Patents

Abstract

By using a bloom filter-based index, a symmetric key-based password generation and retrieval method and system for retrieving encrypted data without decryption, reducing the index size and retrieving data through multiple keywords In this regard, by the server, the user terminal and the encryption generating means installed in the user terminal, the information on the keyword between the communication between the user terminal and the server is not leaked to the server to search for keywords that the user wants to search from the trap door A method for generating a symmetric key based encryption that cannot be learned, the method comprising: (a) a user terminal encrypting and transmitting data to a server using a key known only to the server, and (b) the encryption generating means generates and indexes data from the index. The search key used to search for a pseudorandom permutation Generating keys to be used; and (c) the cipher generating means applies keywords corresponding to each document together with the keys generated from the step (b) to the pseudo random number functions to generate an index using a bloom filter method. Prepare a configuration that includes the steps.
By using the symmetric key-based encryption generation and retrieval method and the system, it is possible to increase the storage efficiency by minimizing the size of the index, and to provide a multi-keyword retrieval for a fast and flexible retrieval query.

Description

Symmetric key-based password generation and retrieval method and system

The present invention relates to a symmetric key-based encryption generation and retrieval method and system thereof. In particular, by using a bloom filter-based index, the encrypted data is retrieved without decryption, the index size is reduced, and several keywords are used. The present invention relates to a symmetric key-based encryption generation and retrieval method and system for retrieving data.

The Republic of Korea became the world's best network with the 'high-speed information and communication infrastructure construction project' that has been in progress since the 1990s, and the development of such networks has caused a change in the way users store data. Before the high-speed information network was established, users used portable storage media such as USB memory or external hardware to carry their data. Such portable storage media have a high risk of loss and have the inconvenience of not being able to access the stored data without carrying them.

Therefore, users want to store and access their main data through the network anytime and anywhere without risking the loss of storage media. This has led to a surge in the use of remote storage services such as web hard.

However, remote storage is a hacker or an unethical administrator who is at risk of exposing personal and sensitive information stored inside.

Therefore, users want to encrypt and store data in order to protect privacy and confidentiality of sensitive data. This is because there is a risk that the contents of the data are exposed to the server performing the search. If a lot of such data is stored in the server, a function is needed so that users can search only the desired data as needed. In other words, there is a need for a method that enables users to search for desired data without compromising the confidentiality of the encrypted data. The proposed technique is searchable encryption technology.

As encryption technology, encryption algorithm is used for secure key distribution and message transmission between server and terminal. Such encryption algorithm uses symmetric key cryptography, public key cryptography and hash algorithm.

Symmetric key cryptography includes DES, AES, SEED, RC5, etc. DES is the basic algorithm of symmetric key cryptography. Symmetric key cryptography is a method in which a sender and a receiver encrypt and transmit the same key. DES converts data to 64-bit output using 56-bit keys, using initial permutation and a single iteration process. The cryptographic algorithm takes a 64-bit input and goes through a series of steps to produce a 64-bit output. Decryption is performed in the reverse order of encryption using the same key as encryption.

Public key cryptography is RSA, an Internet encryption and algorithm developed in 1977 by algorithms developed by three mathematicians: Ron Rivest, Adi Shamir, and Leonard Adleman. It is an authentication system. This method uses two large prime numbers to construct the public and private keys by multiplying these numbers and adding operations, which involves deriving the two sets of numbering schemes used. Information can be encrypted and decrypted using the constructed public and private keys. The principle of operation consists of very complex mathematics. The strength of RSA is that it is difficult to find the private key.

Types of hash algorithms include MD5 and SHA. Hash algorithm is a function that can be used for data integrity and message authentication. It compresses a string of bits of arbitrary length into a hash code which is a fixed length output value. Most hash functions used in cryptographic applications have strong collision resistance. To be required. The hash algorithm can be divided into a hash algorithm and a dedicated hash algorithm based on a block cipher algorithm such as DES. Since the hash algorithm is faster than the block cipher algorithm, the hash algorithm is used in most applications. The hash function is a one-way function that converts inputs of various lengths into fixed short-length outputs and is used for data integrity verification and message authentication.

In addition, there is a need to apply encryption technology to reduce the risk of storing data on an untrusted server, and along with the necessity of a searchable encryption technology that can securely search encrypted data, Proceeded.

Document 1 proposed 'Practical Techniques for Searches on Encrypted Data', which can be referred to as an initial symmetric key based searchable cipher. Data storage servers, such as mail and file servers, require encryption of the data stored to provide security and reduce the risk of privacy breaches. That is, the following Document 1 proposes a method for retrieving encrypted data having a specific keyword while providing confidentiality of data from an untrusted server. The scheme proposed in Document 1 below divides a document into words, each word being represented by a 64-bit block. By pre-encrypting the block of each word and re-encrypting the stream cipher generated by the pseudo-random permutation and pseudo-random function and XOR operation, it is possible to check whether the word is included in the document without exposing the plain text of the cipher text. The method of Document 1 below can be said to be meaningful as an initial searchable cryptographic system although no clear security is defined.

In addition, 'Secure Indexes' proposed in Document 2 is a searchable encryption system that can be searched with a single keyword. For the first time, we defined a clear security model for searchable cryptographic systems and proved the security of the proposed searchable cryptographic systems. This paper consists of key generation, trapdoor generation, indexing, and index retrieval process, and it uses Bloom filter to express the words of the document. However, since the bloom filter is used, the search results have a probability of including an error. To reduce the probability of this error, a larger bloom filter should be used, but using too large a bloom filter makes the search inefficient.

The 'Privacy Preserving Keyword Searches on Remote Encrypted Data' method proposed in Document 3 is designed to reflect the practical needs for a searchable encryption system, such as using a very small trapdoor. The system also uses pseudo-random number generation functions only. Whereas conventional searchable cryptosystems store an index for each keyword separately, the system uses only one bit of information for each keyword. That is, it only stores whether the data contains the given keyword. In addition, the amount of storage can be minimized by using a hash table. In this case, however, there is a disadvantage that the number of communication between the user and the server increases during the searching process.

As the technology that provides the fastest search speed among the existing symmetric key methods, 'Searchable Symmetric Encryption (SSE)' proposed in Document 4 implements documents having each keyword as a linked list. In the following method of Document 4, additional data such as an address value of a document, a key value for decryption of the next node, and an address value of the next node are added to each node, thereby reducing storage efficiency. In addition, when the document is added in the SSE scheme, it has a complicated structure that requires changing the decryption and link of the first node. When deleting a document as well as inserting a document, the node of the document to be deleted must be found and deleted from the linked list of each keyword corresponding to the document. For this purpose, a decryption operation occurs continuously, which causes an overload of the server when the document is inserted / deleted. There is a problem.

Dawn Xiaodong Song, David Wagner, Adrian Perrig Practical Techniques for Searches on Encrypted Data. IEEE Symposium on Security and Privacy 2000: 44-55 (Prakash) Cryptology ePrint Archive: Report 2003/216 Secure Indexes, Eu-Jin Goh Cryptology ePrint Archive: Report 2004/051 Privacy Preserving Keyword Searches on Remote Encrypted Data Yan-Cheng Chang and Michael Mitzenmacher Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions In Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS 2006).

SUMMARY OF THE INVENTION An object of the present invention is to solve the problems as described above. By using a bloom filter-based searchable index, the index size is reduced in searching encrypted data. It is to provide a symmetric key-based password generation and retrieval method and system that provides efficiency and improves the efficiency of retrieval by retrieving data containing several keywords in one field without restriction.

It is another object of the present invention to provide a symmetric key-based encryption generation and retrieval method and system for securely retrieving data using a trap door without encrypting and storing data in a server that is not trusted.

In order to achieve the above object, in the symmetric key-based encryption generation method according to the present invention, information on a keyword is leaked between communication between the user terminal and the server by a password generation means installed in a server, a user terminal, and the user terminal. And a method of generating a symmetric key based encryption so that the server cannot learn keywords that a user wants to search from a trap door, the method comprising: (a) a user terminal encrypting and transmitting data to a server using a key known only to the server; (b) generating the keys used for the pseudo random number function by inserting a search key used in index generation and retrieval of data from the index into a pseudo random number sequence, and (c) the encryption generating means in each case. Apply keywords corresponding to the document to the pseudorandom functions, respectively, with the keys generated from step (b) Characterized in that it comprises indexing to over double filter system.

In the symmetric key-based encryption generation method according to the present invention, (d) generating a trap door to prevent the server from knowing keyword information in order to find data including a keyword from the index generated by the encryption generation means. Generating a key used for a pseudo random number function by inserting a search key used for retrieving data in a pseudo random number permutation into a pseudo random number permutation; The method may further include generating a trap door using a bloom filter method by applying the keys generated from the step (d).

In order to achieve the above object, a symmetric key-based retrieval method according to the present invention includes a server, a user terminal, and an encryption generating means installed in the user terminal, and securely expresses an encrypted document and keywords of the document. A symmetric key-based retrieval method for retrieving data between a server having a server and a user who wants to retrieve a document encrypted with a keyword, the method comprising: (a) a trap door expressing a keyword to be retrieved by the user terminal through an encryption communication unit; (B) a search step of searching for an index value corresponding to a bit string represented by 1 in the trap door from an index expressed by a bloom filter of documents owned by the server, and checking whether the document matches each document. And (c) transmitting the matching documents to the user terminal. .

In addition, in order to achieve the above object, a symmetric key-based password generation system according to the present invention is installed in a user terminal, is connected to a server and a network, and information on keywords is not leaked between communication between the user terminal and the server. A symmetric key-based encryption generation system that prevents a server from learning keywords that a user wants to search from a trap door, the encryption communication unit for encrypting data to be uploaded to the server with an encryption key, indexing and retrieving data from the index A key generator for indexing the search key used in the pseudo random number sequence to generate keys used in the pseudo random number function, and the keywords corresponding to each document in the pseudo random number functions, respectively. To be indexed with the Bloom filter method by applying In addition, a pseudo-random number is used to search for data in a pseudo-random permutation to generate a trap door that prevents the server from knowing keyword information in order to find data including a keyword from the index generated by the index generator. A trap door key generator for generating keys used in a pseudo random number function in permutation and keywords to be searched are applied to the pseudo random number function together with the keys generated by the key generator for trap doors, respectively, to trap in a bloom filter method. It characterized in that it comprises a trap door generating unit for generating a door.

As described above, according to the symmetric key based encryption generation and retrieval method and system according to the present invention, it is possible to increase the storage space efficiency by minimizing the size of the index, and to provide a multi-keyword retrieval for a fast and flexible retrieval query ( The effect of querying is obtained.

1 is a configuration diagram schematically showing a symmetric key based encryption generation and retrieval system according to an embodiment of the present invention;
2 is a block diagram showing the configuration of an agent 40, which is a means for generating encryption of FIG.
FIG. 3 is a flow chart describing the symmetric key based encryption generation and retrieval method according to the present invention. FIG. 4 is a flow chart detailing each step of FIG.
5 is a reference diagram for explaining an index generation method according to an embodiment of the present invention;
6 is a reference diagram illustrating how a user terminal generates a trap door for keyword search;
7 is a reference diagram illustrating a test process of searching for a document through a trap door in a server.

These and other objects and novel features of the present invention will become more apparent from the description of the present specification and the accompanying drawings.

First, the symmetric key-based encryption generation and retrieval according to the present invention and the concept of the system will be described.

Searchable password generation and retrieval systems must meet the following requirements:

1. Confidentiality: The communication data between the remote storage server and the client terminal should only be identified by legitimate individuals, and the third-party attacker shall not be able to infer the keywords and documents corresponding to the keywords.

2. Retrieval Speed: Clients with limited system resources should be able to provide quick retrieval of documents containing keywords to be stored in remote storage.

3. Efficiency of server storage: For fast search in searchable cryptosystems, the capacity of the index to be created should be small.

4. Efficiency of traffic: The traffic should be low for the efficiency of network resources between client and server.

5. Efficiency of document search: The efficiency of supporting multiple keyword search should be provided with one search instead of single keyword search.

In the present invention, in order to satisfy the conditions described above, it is to provide a password generation system that encrypts and stores data in an untrusted server and securely searches using a trap door without decrypting it.

That is, the present invention can reduce the capacity of the index to express the keyword information of the encrypted data by using the bloom filter, and unlike the existing searchable cryptographic system, it is possible to search the data by only one communication with multiple keywords without limiting the fields of the search query. To create a symmetric key-based password generation and retrieval system that supports flexible retrieval.

EMBODIMENT OF THE INVENTION Hereinafter, the structure of this invention is demonstrated according to drawing.

First, an example of configuration of a symmetric key-based encryption generation and retrieval system for implementing the present invention will be described with reference to FIGS. 1 and 2.

1 is a block diagram schematically showing a symmetric key-based encryption generation and retrieval system according to an embodiment of the present invention, Figure 2 is a block diagram showing the configuration of the agent 40, the encryption generating means of FIG.

As shown in FIG. 1, the password generation and retrieval system for implementing the present invention comprises a user terminal 10, a server 20, an agent 40 as a password generation means, and a database (DB, 50).

The user terminal 10 is a terminal having a computing function such as a PC, a notebook computer, a PDA, a tablet PC, and has an internal storage medium such as a hard disk for storing documents. In addition, when the external storage device is inserted, the user terminal 10 recognizes the storage device and uses the storage device as one storage medium. At this time, the document stored in the user terminal 10, for example, the document stored in the hard disk is copied or moved to be stored in an external storage device such as a flash memory, USB memory, SD card, micro SD card, removable hard disk, etc. Can be.

The server 20 is a conventional server connected to the network 30, and is connected to the user terminal 10 through the network 30 and is a server that is not trusted. The server 20 performs data communication with the user terminal 10 to provide a corresponding service in response to a service request of the user terminal 10.

The server 20 receives a document to be exported from the user terminal 10 and determines whether the document is justified. If it is determined that the document can be taken out, that is, the server 40 checks whether or not the document matches each index in the index, and transmits the matching documents to the agent 40 of the user terminal 10.

Agent 40, which is a means for generating encryption, is a program device installed in the user terminal 10. The server 20 has an index for safely expressing the encrypted document and the keywords of the document and the document encrypted with the keyword. Search the data between the user terminal 10, the information about the keyword is not leaked between the communication between the user terminal 10 and the server 20, the server 20 is to search the user terminal 10 from the trap door Do not learn the keywords that are.

In addition, the database 50 is for storing necessary data, and stores documents, etc. transmitted from the user terminal 10, and is constructed by a general database construction theory in view of the ease and efficiency of access and retrieval.

Next, the configuration of the encryption generating means 40 in the symmetric key-based encryption generation system according to an embodiment of the present invention will be described in more detail with reference to FIG. 2. Here, the cipher generating means 40 refers to the agent 40 described above. The cryptographic generation means 40 is a program device installed in the user terminal 10.

As shown in FIG. 2, the encryption generating means 40 according to the present invention includes an encryption communication unit 41, an index key generation unit 42, an index generation unit 43, a trap door key generation unit 44, and the like. The trap door generating unit 45 is configured. In addition, a user authentication unit for authenticating a user in order to block a recognition of the external storage device when the external storage device is inserted into the user terminal 10 and to release the recognition block of the storage device when the user authentication is successful. And a media control unit for managing the storage medium.

The encryption communication unit 41 encrypts data to be uploaded to the server 20 with an encryption key. That is, the user encrypts and transmits the data to the server 20 using a key known only by the user.

The index key generator 42 generates keys used in a pseudo random number function by inserting a search key used for index generation and retrieval of data from the index into a pseudo random number sequence, and the index generator 43 generates a document. The keywords corresponding to are applied to the pseudo random number functions together with the keys generated by the index key generator 42 to generate an index using the Bloom filter method.

The key generation unit 44 for the trap door is a pseudo-generator for generating a trap door that prevents the server 20 from knowing keyword information in order to find data including a keyword from the index generated by the index generation unit 43. The search key used to search data in the random number sequence is added to the pseudo random number sequence to generate keys used in the pseudo random number function. The trap door generator 45 traps the keywords to be searched in the pseudo random number function. The trap door is generated by a bloom filter method by applying the keys generated by the door key generator 44 together.

The trap door generated by the trap door generation unit 45 is transmitted to the server 20 via the network 30 through the encryption communication unit 41, the server 20 stores the transmitted data in the database 50 do.

A symmetric key based encryption generation and retrieval method according to the present invention will be described with reference to FIGS. 3 and 4.

FIG. 3 is a flow chart describing the symmetric key based encryption generation and retrieval method according to the present invention, and FIG. 4 is a flowchart detailing each step of FIG.

Symmetric key-based encryption and retrieval according to the present invention is largely divided into the index generation step (S10), trap door generation step (S20), document retrieval step (S30) and transmission step (S40), as shown in FIG. Are distinguished.

First, the indexing process is explained.

The index generation process is performed by the user terminal 10 safely generating keyword information of data to be transmitted to the server 20 in the following order.

The user terminal 10 first encrypts data to be uploaded to the server 20 with an encryption key through the encryption communication unit 421 (S101). The index key generator 42 generates a key of pseudo random number functions used to generate a specific bit string bloom filter for expressing information of keywords of each data, by inserting an index generating key into the pseudo random number permutation ( S102). Next, the index generator 43 generates the index by changing the bit value of the bloom filter corresponding to the value to 1 by inserting the keywords of the document into the pseudo random functions, and repeating the above process by the number of keywords. In operation S103, a bloom filter corresponding to the document is generated.

After the index is generated by the index generator 43, the user first generates a trap door when searching for data using a keyword.

The generation of the trap door proceeds in the following order.

The trap door key generator 44 in the user terminal 10 generates keys of a pseudo random number function used to create a trap door by inserting an index generation key into a pseudo random number sequence, and the trap door generator 45 searches. The trap door is created by creating a bloom filter in the same manner as the index generation process with keywords to be made (S104).

After generating the trap door, the encryption communication unit 41 transmits the trap door to the server 20 (S105), and the server 20 tests whether each document has keywords from the index through the trap door.

The document search process proceeds in the following order.

First, the user terminal 10 transmits a trap door representing a keyword to be searched through the encryption communication unit 41 to the server 20. The server 20 searches for the value of the index corresponding to the bit string represented by 1 in the trap door from the index represented by the bloom filter of the documents. The index of the document having the value of the searched bit string all 1 indicates that all the keywords to be searched are included, and the searched encrypted documents are transmitted to the user terminal 10.

Next, the symbols used in the present specification are defined as follows.

ek: document encryption key

sk: index / search key

m: the total number of documents

n: the total number of keywords

j: Number of keywords in a specific document (j≤n)

q: the number of documents with a specific keyword (q≤m)

c: the number of one-way functions used for the bloom filter

l: length of the bloom filter (l <n)

d _i : i-th document

w _i : i-th keyword

w _{i , j} : j-th keyword of the i-th document

D: collection of documents

W: set of keywords

: i번째 문서의 블룸 필터

: Bloom filter in the i document

E _* []: encrypted with *

D _* []: decrypt with *

F _* []: pseudorandom number function with keys of *

P []: pseudo-random permutation

H []: safe one-way function

IT _i : i th record of the index table

DT _i : i-th record of the data table

T _* : Trapdoor to search for documents with * keywords

Hereinafter, a lumber filter-based multi-keyword searchable symmetric key cryptosystem according to an embodiment of the present invention will be described in detail with reference to FIGS. 5 to 7.

5 is a reference diagram for explaining an index generation method according to an embodiment of the present invention, FIG. 6 is a reference diagram for explaining a method for generating a trap door for a keyword search by a user terminal, and FIG. This is a reference that describes the test procedure for retrieving a document through the trap door.

Admissible Bilinear Map based multicast key management method according to an embodiment of the present invention is divided into an index generation process, a trap door generation process, a document search process, as described above. Looking at it as follows.

As shown in FIG. 5, in the index generation process, the user terminal 10 first encrypts m pieces of data to be uploaded to the server 20 with an encryption key ek and stores them.

Next, we generate the keys k ₁ through k _c used in the pseudo random number function by inserting the index / search key into the pseudo random sequence.

를 의사 난수 함수를 사용하여 생성한다. 의사 난수 함수를 통해 추출한 값에 해당하는 블룸 필터의 값을 1로 변경하여 블룸 필터를 생성한다.for representing the n keywords of the i th document d _i

Is generated using a pseudo-random function. The bloom filter is created by changing the value of the bloom filter corresponding to the value extracted through the pseudo random number function to 1.

을 생성한다.Repeat this process for m documents

.

After the index is generated by the index generator 43, the user terminal 10 first generates a trap door when searching for data using keywords.

The trap door generation process proceeds in the following order as shown in FIG.

The user terminal 10 has a key generation process used in the trap door by putting sk in a pseudo random number permutation.

The trap door generation unit 45 generates a trap door necessary for searching a document including a set W of keywords to be searched.

After generating the trap door, the user terminal 10 transmits the trap door to the server 20, and the server 20 tests whether each document has keywords from the index through the trap door.

The document retrieval process is performed in the following order as shown in FIG.

를 획득한다.A bloom filter representing the keywords of the document d _i that you want to test to see if it contains the keywords you want to search.

Acquire it.

에서 트랩 도어 T_W에 해당하는 색인의 값의 행을 순차적으로 탐색하여 값이 전부 1인 경우 i번째 문서인 d_i가 검색하고자하는 키워드들을 모두 포함하고 있음을 나타내며, 검색된 암호화 문서들을 사용자 단말(10)로 전송한다.
Server 20 bloom filter

In order to sequentially search the row of the value of the index corresponding to the trap door T _W , if the value is all 1, it indicates that the i-th document d _i includes all the keywords to be searched. To 10).

As mentioned above, although the invention made by this inventor was demonstrated concretely according to the said Example, this invention is not limited to the said Example and can be variously changed in the range which does not deviate from the summary.

In other words, the above description has been made of a structure in which an agent is provided in the user terminal. However, the present invention is not limited thereto, and an arrangement may be provided in the server.

The symmetric key based encryption generation and retrieval method and the system according to the present invention are used for users to store and access their main data through the network anytime and anywhere without risk of losing the storage medium.

10: user terminal 20: server
30: network 40: agent
50; Database 41: Password Communication
42: index generation unit 43: index generation unit
44: key generator for the trap door
45: trap door generation unit

Claims (4)

By the server, the user terminal, and the encryption generating means installed in the user terminal, the server can learn the keywords that the user wants to search from the trap door without information about the keyword is leaked between communication between the user terminal and the server. As a symmetric key-based password generation method,
(a) the user terminal encrypting and transmitting data to a server using a key known only by the symmetric key;
(b) generating the keys used in the pseudo random number function by inserting a search key used in index generation and retrieval of data from the index into a pseudo random sequence;
(c) the cryptographic generation means applying keywords corresponding to each document to the pseudorandom functions together with the keys generated from the step (b) to generate an index which minimizes the capacity by the Bloom filter method;
(d) a search key used when searching for data in a pseudo-random permutation to generate a trap door that causes the server to not know the keyword information to find data containing the keyword from the index generated by the cipher generating means. Generating keys for use in a pseudo random number function in a pseudo random number permutation, and
(e) Applying the keywords to be searched by the cipher generating means to the pseudo random number function together with the keys generated from the step (d) to generate a trap door using a bloom filter method to store data including several keywords in the field. Symmetric key-based password generation method comprising the step of searching without limitation at one time. delete Search for data between a server having a server, a user terminal, and a cipher generating means installed in the user terminal, the server having an index that securely represents an encrypted document and keywords of the document, and a user who wants to search for a document encrypted with the keyword. As a symmetric key based search method,
Receiving, by the server, a trap door generated by the symmetric key based encryption generation method of claim 1,
A test step of searching for a value of an index corresponding to a bit string represented by 1 in a trap door from an index represented by a bloom filter of the documents owned by the server, and checking whether the document corresponds to each document; and
And transmitting matching documents to a user terminal.

delete

Images