Stateful order-preserving encryption method and apparatus for enhancing security

Abstract

Disclosed herein is a method and apparatus for stateful order-preserving encryption for enhancing security. The method includes generating an order-preserving ciphertext by performing order-preserving encryption on a plaintext, generating a plurality of dummy ciphertexts corresponding to a preset variable for the order-preserving ciphertext, and adding the order-preserving ciphertext and the plurality of dummy ciphertexts to a ciphertext set.

Claims

1. A method for order-preserving encryption, comprising: generating an order-preserving ciphertext by performing order-preserving encryption on a plaintext; generating a plurality of dummy ciphertexts corresponding to a preset variable for the order-preserving ciphertext; and adding the order-preserving ciphertext and the plurality of dummy ciphertexts to a ciphertext set.

2. The method of claim 1, wherein the ciphertext set includes a plurality of ciphertext subsets, and a state information variable indicating state information is assigned to each of the plurality of ciphertext subsets.

3. The method of claim 2, wherein an initial value of the state information variable is set to 0, and a value of the state information variable is increased by 1 each time a ciphertext is added to the ciphertext subset to which the state information variable is assigned.

4. The method of claim 2, wherein generating the plurality of dummy ciphertexts includes selecting an arbitrary ciphertext from a ciphertext subset, the state information variable of which has a smallest value, among the plurality of ciphertext subsets; generating a single dummy ciphertext by adding a ciphertext check bit generated in a manner different from the order-preserving encryption to the arbitrary ciphertext; and repeatedly performing a process of generating the single dummy ciphertext a number of times corresponding to the preset variable.

5. The method of claim 2, further comprising: setting a data search range based on a data search condition; extracting at least one candidate ciphertext corresponding to the data search range from the plurality of ciphertext subsets; and providing search data by removing a dummy ciphertext from the at least one candidate ciphertext.

6. The method of claim 5, wherein the data search range is set based on values that are output by performing order-preserving encryption on an upper limit value and a lower limit value included in the data search condition.

7. The method of claim 6, wherein a ciphertext check bit is calculated for each of the at least one candidate ciphertext, and a candidate ciphertext, the ciphertext check bit of which does not match a ciphertext check bit corresponding to the order-preserving encryption, among the at least one candidate ciphertext, is identified as the dummy ciphertext.

8. An apparatus for order-preserving encryption, comprising: a processor for generating an order-preserving ciphertext by performing order-preserving encryption on a plaintext, generating a plurality of dummy ciphertexts corresponding to a preset variable for the order-preserving ciphertext, and adding the order-preserving ciphertext and the plurality of dummy ciphertexts to a ciphertext set; and memory for storing the ciphertext set.

9. The apparatus of claim 8, wherein the ciphertext set includes a plurality of ciphertext subsets, and a state information variable indicating state information is assigned to each of the plurality of ciphertext subsets.

10. The apparatus of claim 9, wherein an initial value of the state information variable is set to 0, and a value of the state information variable is increased by 1 each time a ciphertext is added to the ciphertext subset to which the state information variable is assigned.

11. The apparatus of claim 9, wherein the processor selects an arbitrary ciphertext from a ciphertext subset, the state information variable of which has a smallest value, among the plurality of ciphertext subsets, generates a single dummy ciphertext by adding a ciphertext check bit generated in a manner different from the order-preserving encryption to the arbitrary ciphertext, and repeatedly performs a process of generating the single dummy ciphertext a number of times corresponding to the preset variable.

12. The apparatus of claim 9, wherein the processor sets a data search range based on a data search condition, extracts at least one candidate ciphertext corresponding to the data search range from the plurality of ciphertext subsets, and provides search data by removing a dummy ciphertext from the at least one candidate ciphertext.

13. The apparatus of claim 12, wherein the data search range is set based on values that are output by performing order-preserving encryption on an upper limit value and a lower limit value included in the data search condition.

14. The apparatus of claim 13, wherein a ciphertext check bit is calculated for each of the at least one candidate ciphertext, and a candidate ciphertext, the ciphertext check bit of which does not match a ciphertext check bit corresponding to the order-preserving encryption, among the at least one candidate ciphertext, is identified as the dummy ciphertext.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The above and other objects, features, and advantages of the present disclosure will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings, in which:

(2) FIG. 1 is a view illustrating a system for order-preserving encryption according to an embodiment of the present disclosure;

(3) FIG. 2 is a flowchart illustrating a method for order-preserving encryption according to an embodiment of the present disclosure;

(4) FIG. 3 and FIG. 4 are views illustrating an example of adding a ciphertext check bit to each of an order-preserving ciphertext and a dummy ciphertext according to the present disclosure;

(5) FIG. 5 is a view illustrating an example of a process of enhancing stateful order-preserving encryption according to the present disclosure;

(6) FIG. 6 is a flowchart illustrating a process of searching for data desired by a user according to an embodiment of the present disclosure; and

(7) FIG. 7 is a view illustrating an apparatus for order-preserving encryption according to an embodiment of the present disclosure.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

(8) The present disclosure will be described in detail below with reference to the accompanying drawings. Repeated descriptions and descriptions of known functions and configurations which have been deemed to unnecessarily obscure the gist of the present disclosure will be omitted below. The embodiments of the present disclosure are intended to fully describe the present disclosure to a person having ordinary knowledge in the art to which the present disclosure pertains. Accordingly, the shapes, sizes, etc. of components in the drawings may be exaggerated in order to make the description clearer.

(9) In the present specification, each of expressions such as A or B, at least one of A and B, at least one of A or B, A, B, or C, at least one of A, B, and C, and at least one of A, B, or C may include any one of the items listed in the expression or all possible combinations thereof.

(10) Hereinafter, a preferred embodiment of the present disclosure will be described in detail with reference to the accompanying drawings.

(11) An object of the present disclosure is to provide a method for enhancing security of order-preserving encryption technology, which provides lower security than general encryption technology.

(12) In the case of an order-preserving encryption function, the order information of a plaintext is exposed to everyone through a ciphertext itself. Accordingly, there is a disadvantage in which, when an attacker knows the statistical characteristics of a plaintext set, it is likely that the attacker is able to infer a plaintext from a given ciphertext set when the ciphertext set has a sufficiently large size.

(13) For this reason, security enhancement is required for order-preserving technology in order to make it impossible for an attacker to infer a plaintext set in a statistical manner. For example, a method of encrypting the same plaintext into different ciphertexts in order to hide statistical information may be applied.

(14) However, when an attacker knows which plaintext corresponds to a ciphertext in a target ciphertext set, the attacker is able to infer a plaintext from order information itself even though statistical information is hidden.

(15) In the present disclosure to be described below, a method for including dummy data in a ciphertext set is proposed in order to overcome the fundamental disadvantage of order-preserving encryption technology. Through this method, a user may configure a ciphertext set having a statistical characteristic desired by the user for any plaintext set, whereby an attacker may be prevented from inferring the plaintext set.

(16) Also, because the attacker cannot identify the ciphertext acquired by encrypting the actual plaintext in a given ciphertext set, there is an advantage in which the attacker cannot efficiently reconstruct the plaintext from the ciphertext despite having information about the plaintext set.

(17) FIG. 1 is a view illustrating a system for order-preserving encryption according to an embodiment of the present disclosure.

(18) Referring to FIG. 1, the system for order-preserving encryption according to an embodiment of the present disclosure includes an order-preserving encryption apparatus 100 and a ciphertext DB 110.

(19) The order-preserving encryption apparatus 100 generates an order-preserving ciphertext by performing order-preserving encryption on a plaintext.

(20) Also, the order-preserving encryption apparatus 100 generates a plurality of dummy ciphertexts corresponding to a preset variable for the order-preserving ciphertext.

(21) Also, the order-preserving encryption apparatus 100 adds the order-preserving ciphertext and the plurality of dummy ciphertexts to a ciphertext set managed in the ciphertext DB 110.

(22) Here, the ciphertext set includes a plurality of ciphertext subsets, and a state information variable indicating state information may be assigned to each of the plurality of ciphertext subsets.

(23) Here, the initial value of the state information variable may be set to 0, and the value of the state information variable may be increased by 1 each time a ciphertext is added to the ciphertext subset to which the state information variable is assigned.

(24) Here, an arbitrary ciphertext may be selected from the ciphertext subset, the state information variable of which has the smallest value, among the plurality of ciphertext subsets, a single dummy ciphertext may be generated by adding a ciphertext check bit generated in a manner different from order-preserving encryption to the selected arbitrary ciphertext, and the process of generating a single dummy ciphertext may be repeatedly performed a number of times corresponding to the preset variable.

(25) Also, the order-preserving encryption apparatus 100 sets a data search range based on a data search condition, extracts at least one candidate ciphertext corresponding to the data search range from the plurality of ciphertext subsets, and provides search data by removing a dummy ciphertext from the at least one candidate ciphertext.

(26) Here, the data search range may be set based on values that are output by performing order-preserving encryption on the upper limit value and the lower limit value included in the data search condition.

(27) Here, an encryption check bit is calculated for each of the at least one candidate ciphertext, and a candidate ciphertext, the ciphertext check bit of which does not match a ciphertext check bit corresponding to order-preserving encryption, among the at least one candidate ciphertext, may be identified as a dummy ciphertext.

(28) FIG. 2 is a flowchart illustrating a method for order-preserving encryption according to an embodiment of the present disclosure.

(29) Referring to FIG. 2, in the method for order-preserving encryption according to an embodiment of the present disclosure, an order-preserving ciphertext is generated by performing order-preserving encryption on a plaintext at step S210.

(30) For example, when F is defined as an order-preserving encryption function, a ciphertext acquired for a plaintext m and a secret key k may be F(k, m). Here, F may output an element in a ciphertext space C as the ciphertext by receiving an arbitrary element in a plaintext space M as input.

(31) Also, in the method for order-preserving encryption according to an embodiment of the present disclosure, a plurality of dummy ciphertexts corresponding to a preset variable are generated for the order-preserving ciphertext at step S220.

(32) Also, in the method for order-preserving encryption according to an embodiment of the present disclosure, the order-preserving ciphertext and the plurality of dummy ciphertexts are added to a ciphertext set at step S230.

(33) Here, the ciphertext set includes a plurality of ciphertext subsets, and a state information variable indicating state information may be assigned to each of the plurality of ciphertext subsets.

(34) Here, the initial value of the state information variable may be set to 0, and the value of the state information variable may be increased by 1 each time a ciphertext is added to the ciphertext subset to which the state information variable is assigned.

(35) Here, an arbitrary ciphertext may be selected from the ciphertext subset, the state information variable of which has the smallest value, among the plurality of ciphertext subsets, a single dummy ciphertext may be generated by adding a ciphertext check bit generated in a manner different from order-preserving encryption to the arbitrary ciphertext, and the process of generating a single dummy ciphertext may be repeatedly performed a number of times corresponding to the preset variable.

(36) Hereinafter, the process of adding a dummy ciphertext to a ciphertext set will be described in detail through an embodiment.

(37) First, integers and may be set as variables for enhancing security of order-preserving encryption technology according to the present disclosure.

(38) Here, and may be integers greater than 1. The ciphertext space C of an order-preserving encryption function F may be divided into u subspaces, C.sub.1, C.sub.2, . . . , C.sub.. That is, C.sub.1, C.sub.2, . . . , C.sub. may correspond to a plurality of ciphertext subsets.

(39) Subsequently, N.sub.1, N.sub.2, . . . , N.sub., which are state information variables, may be initialized to 0. Here, N.sub.i may indicate the number of ciphertexts included in a ciphertext subset C.sub.i, among the ciphertext subsets. That is, the values of N.sub.1, N.sub.2, . . . , N.sub., which are the state information variables, may configure state information for order-preserving encryption.

(40) Accordingly, when a plaintext m is given, encryption is performed using c=F (k, m), and the value of N.sub.i may be increased by 1 when cC.sub.i is satisfied.

(41) Subsequently, a ciphertext check bit (1-bit) generated from the ciphertext c is added to an order-preserving ciphertext 300 through c=cmsb (H(ck)), as shown in FIG. 3, whereby a final ciphertext may be generated.

(42) Subsequently, a number of dummy ciphertexts corresponding to the variable may be generated.

(43) Here, N.sub.i having the smallest value is selected from among the state information variables N.sub.1, N.sub.2, . . . , N.sub., an arbitrary ciphertext x within the range of C.sub.i corresponding to N.sub.i is selected, and the value of N.sub.i may be increased by 1. Subsequently, as illustrated in FIG. 4, a ciphertext bit generated from the ciphertext x is added to the ciphertext x through x=xmsb(h(xk))+1, whereby a final dummy ciphertext x may be generated.

(44) When dummy ciphertexts x.sub.1, x.sub.2, . . . , x.sub. are generated in this way, a single order-preserving ciphertext c and dummy ciphertexts x.sub.1, x.sub.2, . . . , x.sub. may be generated through a plaintext m input to an order-preserving encryption apparatus 500, as illustrated in FIG. 5. That is, +1 ciphertexts, c.sub.0, c.sub.1, . . . , c.sub., may be generated for a single plaintext, and the generated +1 ciphertexts, c.sub.0, c.sub.1, . . . , c.sub., may be added to the ciphertext set.

(45) Also, although not illustrated in FIG. 2, in the method for order-preserving encryption according to an embodiment of the present disclosure, a data search range is set based on a data search condition, at least one candidate ciphertext corresponding to the data search range is extracted from the plurality of ciphertext subsets, and search data is provided by removing a dummy ciphertext from the at least one candidate ciphertext.

(46) Here, the data search range may be set based on values that are output by performing order-preserving encryption on the upper limit value and the lower limit value included in the data search condition.

(47) Here, an encryption check bit is calculated for each of the at least one candidate ciphertext, and a candidate ciphertext, the ciphertext check bit of which does not match a ciphertext check bit corresponding to order-preserving encryption, among the at least one candidate ciphertext, may be identified as a dummy ciphertext.

(48) Hereinafter, a process of searching for data desired by a user will be described in detail with reference to FIG. 6.

(49) First, assuming that search data x satisfies axb for a and b, which are specific pieces of data, a data search condition may be set to correspond to axb at step S610.

(50) Subsequently, F(a, k) and F(b, k) may be calculated for a and b, which are the lower limit value and the upper limit value included in the data search condition, in order to perform order-preserving encryption at step S620.

(51) Subsequently, F(a, k)0 and F(b, k)1 are calculated in order to add a ciphertext check bit, whereby F(a, k)0xF(b, k)1 corresponding to a data search range may be set at step S630.

(52) Subsequently, at least one candidate ciphertext x satisfying the data search range, F(a, k)0xF(b, k)1, may be collected from a plurality of ciphertext subsets at step S640.

(53) Subsequently, x=xb, b=msb(h(xk)) may be calculated in order to check the ciphertext check bit corresponding to order-preserving encryption for the at least one candidate ciphertext x at step S650.

(54) Subsequently, among the collected at least one candidate ciphertext x, a candidate ciphertext, the ciphertext check bit of which does not match a ciphertext check bit corresponding to order-preserving encryption (b b), may be removed from a search result at step S660.

(55) Subsequently, the candidate ciphertext x, the ciphertext check bit of which matches the ciphertext check bit corresponding to order-preserving encryption (b=b), may be provided as the search data at step S670.

(56) According to the above-described configuration, dummy ciphertexts may be generated for a single plaintext m, and a user is able to determine statistical characteristics for a final ciphertext set based on state information of each of multiple ciphertext subsets. Therefore, an attacker may be prevented from inferring a plaintext set from the statistical characteristics of the ciphertext set.

(57) Also, because an attacker is not able to distinguish between a ciphertext for an actual plaintext and an arbitrarily generated dummy ciphertext in a given ciphertext set even when the attacker infers a plaintext set, it is difficult to infer a plaintext for the actual ciphertext even though the order information of the ciphertext is used. By applying this technique, the security of the order-preserving technology may be enhanced, and this may be applied to any order-preserving encryption technology.

(58) Through the above-described stateful order-preserving encryption method for enhancing security, an attacker is prevented from inferring a plaintext set from the statistical characteristics of a ciphertext set, whereby security may be enhanced.

(59) Also, even when an attacker infers a plaintext set, the attacker is prevented from distinguishing between a ciphertext for an actual plaintext and an arbitrarily generated ciphertext in a ciphertext set, whereby the security of order-preserving encryption technology may be enhanced.

(60) FIG. 7 is a view illustrating an apparatus for order-preserving encryption according to an embodiment of the present disclosure.

(61) Referring to FIG. 7, the apparatus for order-preserving encryption according to an embodiment of the present disclosure may be implemented in a computer system including a computer-readable recording medium. As illustrated in FIG. 7, the computer system 700 may include one or more processors 710, memory 730, a user-interface input device 740, a user-interface output device 750, and storage 760, which communicate with each other via a bus 720. Also, the computer system 700 may further include a network interface 770 connected to a network 780. The processor 710 may be a central processing unit or a semiconductor device for executing processing instructions stored in the memory 730 or the storage 760. The memory 730 and the storage 760 may be any of various types of volatile or nonvolatile storage media. For example, the memory may include ROM 731 or RAM 732.

(62) Accordingly, an embodiment of the present disclosure may be implemented as a non-transitory computer-readable medium in which methods implemented using a computer or instructions executable in a computer are recorded. When the computer-readable instructions are executed by a processor, the computer-readable instructions may perform a method according to at least one aspect of the present disclosure.

(63) The processor 710 generates an order-preserving ciphertext by performing order-preserving encryption on a plaintext.

(64) Also, the processor 710 generates a plurality of dummy ciphertexts corresponding to a preset variable for the order-preserving ciphertext.

(65) Also, the processor 710 adds the order-preserving ciphertext and the plurality of dummy ciphertexts to a ciphertext set.

(66) Here, the ciphertext set includes a plurality of ciphertext subsets, and a state information variable indicating state information may be assigned to each of the plurality of ciphertext subsets.

(67) Here, the initial value of the state information variable may be set to 0, and the value of the state information variable may be increased by 1 each time a ciphertext is added to the ciphertext subset to which the state information variable is assigned.

(68) Here, an arbitrary ciphertext may be selected from the ciphertext subset, the state information variable of which has the smallest value, among the plurality of ciphertext subsets, a single dummy ciphertext may be generated by adding a ciphertext check bit generated in a manner different from order-preserving encryption to the arbitrary ciphertext, and the process of generating a single dummy ciphertext may be repeatedly performed a number of times corresponding to the preset variable.

(69) Also, the processor 710 sets a data search range based on a data search condition, extracts at least one candidate ciphertext corresponding to the data search range from the plurality of ciphertext subsets, and provides search data by removing a dummy ciphertext from the at least one candidate ciphertext.

(70) Here, the data search range may be set based on values that are output by performing order-preserving encryption on the upper limit value and the lower limit value included in the data search condition.

(71) Here, a ciphertext check bit is calculated for each of the at least one candidate ciphertext, and a candidate ciphertext, the ciphertext check bit of which does not match a ciphertext check bit corresponding to order-preserving encryption, among the at least one candidate ciphertext, may be identified as a dummy ciphertext.

(72) The memory 730 stores the ciphertext set.

(73) Also, the memory 730 stores various kinds of information generated in the apparatus for order-preserving encryption according to an embodiment of the present disclosure, as described above.

(74) According to an embodiment, the memory 730 may separate from the apparatus for order-preserving encryption, and may support the function for order-preserving encryption. Here, the memory 730 may operate as separate mass storage, and may include a control function for performing operations.

(75) Meanwhile, the apparatus for order-preserving encryption includes memory installed therein, whereby information may be stored therein. In an embodiment, the memory is a computer-readable medium. In an embodiment, the memory may be a volatile memory unit, and in another embodiment, the memory may be a nonvolatile memory unit. In an embodiment, the storage device is a computer-readable medium. In different embodiments, the storage device may include, for example, a hard-disk device, an optical disk device, or any other kind of mass storage device.

(76) Through the above-described stateful order-preserving encryption apparatus for enhancing security, an attacker is prevented from inferring a plaintext set from statistical characteristics of a ciphertext set, whereby security may be enhanced.

(77) Also, even when an attacker infers a plaintext set, the attacker is prevented from distinguishing between a ciphertext for an actual plaintext and an arbitrarily generated ciphertext in a ciphertext set, whereby security of order-preserving encryption technology may be enhanced.

(78) According to the present disclosure, order-preserving encryption technology having enhanced security may be provided by preventing an attacker from inferring a plaintext set from the statistical characteristics of a ciphertext set.

(79) Also, the present disclosure may enhance security of order-preserving encryption technology by making it impossible for an attacker to distinguish between a ciphertext for an actual plaintext and an arbitrarily generated ciphertext in a ciphertext set even when the attacker infers a plaintext set.

(80) As described above, the stateful order-preserving encryption method and apparatus for enhancing security according to the present disclosure are not limitedly applied to the configurations and operations of the above-described embodiments, but all or some of the embodiments may be selectively combined and configured, so the embodiments may be modified in various ways.