Description

This paper deals with ordered bucketization (OB) as a cryptographic object. In OB, plaintext-space is divided into a pre-defined number of buckets. Consider the number p , then assign a number to each bucket, from 1 to p. With bucketization, including OB, various types of SQL queries over encrypted data are possible, if the bucket number, which corresponds to the original plaintext before encryption, is attached to each encrypted data. For example, if a client program wants to retrieve the data in the range between 100,000 and 200,000, it first calculates the numbers of buckets whose union is the smallest set that covers the queried range. This paper defines an encryption scheme with OB (EOB) and suggests a new security model for EOB, IND-OCPA-P, which assumes an adversary has reasonable power. Bucketization is particulary more helpful for range queries if the bucket number is assigned in an ordered manner. For example, in the same case reported in the above paragraph, the client needs to send two bucket numbers: one that includes 100,000 and the other that includes 200,000. In this sense, OB can be a replacement for an order-preserving encryption (OPE). This approach is very efficient compared to the case where the client receives all the encrypted data from the server and decrypts all data items to obtain the correct query result. Therefore, this method is very useful when users cannot store their data without encryption such as in a cloud computing environment.