RASP: Random Space Encryption for Efficient Multidimensional Range Queries on Encrypted Databases

Data Intensive Analysis and Computing (DIAC) Lab
The Ohio Center of Excellence on Knowledge Enabled Computing (Kno.e.sis Center)
Wright State University


Services computing and cloud computing have become the major computing paradigms. To use services or cloud infrastructures, users often need to outsource their data to the service provider. A major concern is preserving the privacy of the outsourced data. Traditional encryption methods can preserve data privacy but not data utility. New encryption methods are to be developed with both privacy and utility in mind.  

RASP method:

We propose the RASP method that preserves convexity of datasets. Concretely, the RASP encryption method transforms a multidimensional dataset to an encrypted one, so that any convex subset in the original dataset will be transformed to another convex subset in the encrypted dataset. This property ensures any query on convex shapes can be translated to another query in the encrypted space. We apply this property to secure and efficient range query service on multidimensional datasets. The following figure shows the intuition behind secure range query using the RASP method (with a two dimensional dataset).


The RASP encryption method is defined as follows.

The RASP based range query service can be described in the following framework.

        The service provider is an honest-but-curious party that says the service provider will honestly follow the protocol and provide services with promised quality, but it may be curious about the data submitted by the user.

        The proxy server in the trusted side needs to handle small amount of work most data/compute intensive tasks should be taken over by the service provider. The proxy server takes the original data from the data owner, encrypts it and submits the encrypted data to the server. The data owner just needs to guarantee the security of the proxy server and manage the right of submitting range queries. The proxy server also encrypts queries and decrypts query results returned by the server.

        The server can build multidimensional indices (e.g., R*trees) on the encrypted data and perform a two-stage query processing strategy to answer queries (1) indexing based processing to find the result in the bounding box (2) filtering the results with the query conditions. An enclosed range query with small range can be processed very efficiently with this strategy.



Related Resources:

1.     A demo system will be available soon:  demo system by Shumin Guo


2.     For more details, please read our paper:

Keke Chen, Ramakanth Kavuluru, Shumin Guo " RASP: Efficient Multidimensional Range Query on Attack-Resilient Encrypted Databases ", ACM Conference on Data and Application Security and Privacy (CODASPY), 2011. [ pdf]