Method and apparatus for generating index for encrypted field in database
The present invention relates to a method and an apparatus for generating an index for an encrypted field in order to protect private information in database. The method for generating the index for the encrypted field according to an embodiment of the present invention constructs an index as encrypted data itself without decrypting and storing contents of the encrypted field, constructs an index using distance information between encrypted data and a pre-configured reference value when the index is constructed, calculates a distance value from the reference value even when a search is performed, and performs a search by comparing the distance value with constructed index information table. In particular, when duplicated data exists, the present invention configures the duplicated data as a set of lower leaf nodes for a leaf node, thereby minimizing a search time.
1. A method, performed by at least one processor, of generating indexes on a field encrypted for protection of personal information in a database, the method comprising:
reading encrypted data corresponding to the encrypted field from the data base;
extracting original data which has position information within the encrypted field by decrypting the encrypted data;
generating a reference value;
calculating distance values between the original data and the reference value;
sorting the distance values according to magnitudes and signs of the distance values; and
generating an index information table in which the position information and the distance values are stored by matching the position information of the original data to the distance values,
wherein the generating the reference value comprises generating a random value according to a maximum length and a type of the original data.
2. The method according to claim 1 , further comprising:
when a search of target original data is needed, searching the database for the target original data by calculating an input distance value which is a distance between the target original data and the reference value, and comparing the input distance value with the distance values stored in the index information table.
3. The method according to claim 1 , further comprising, between the generating the reference value and the calculating distance values, encrypting the reference value and storing the encrypted reference value.
4. The method according to claim 2 , wherein the searching the database for the target original data comprises searching the database for the target original data uses at least one of a B+ tree algorithm, a hash algorithm, and a bitmap algorithm.
5. The method according to claim 4 , wherein the at least one of the B+ tree algorithm, the hash algorithm, and the bitmap algorithm is performed using a tree structure comprising internal nodes including reference values for searching the target original data and leaf nodes including index information.
6. The method according to claim 5 , wherein, when lower leaf nodes having different position information and redundant data exist, the lower leaf nodes having different position information and redundant data are grouped into a set so that overhead is minimized.
7. The method according to claim 6 , wherein lower leaf nodes having only position information are generated to form a set, in a lower position of a leaf node among the lower leaf nodes having the redundant data.
8. The method according to claim 1 , wherein the index information table is generated by using a user-defined indexing technique when the database provides the user-defined indexing technique, and the index information table is generated by using a user-defined function and a trigger when the database does not provide the user-defined indexing technique.
9. An apparatus of generating indexes on a field encrypted for protection of personal information in a database, the apparatus comprising:
at least one hardware processor; and
a memory storing instructions to cause the at least one hardware processor to perform:
reading encrypted data corresponding to the encrypted field from the database;
extracting original data which has position information within the encrypted field by decrypting the encrypted data;
generating a reference value;
calculating distance values between the original data and the reference value;
sorting the distance values according to magnitudes and signs of the distance values; and
generating an index information table in which the position information and the distance values are stored by matching the position information of the original data to the distance values, and
wherein the generating the reference value comprises generating a random value according to a maximum length and a type of the original data.
10. The apparatus according to claim 9 , wherein the calculating distance values comprises calculating the distance values by calculating differences between the reference value and the original data based on order information of a first character string of the original data when the original data are constructed as character strings.
11. The apparatus according to claim 9 , wherein the calculating distance values comprises sorting the distance values according to magnitudes and signs of the distance values.
12. The apparatus according to claim 9 , wherein the instructions cause the at least one hardware processor to further perform calculating an input distance value which is a distance between target original data and the reference value and searching for the target original data by comparing the input distance value with the distance values stored in the index information table.