TY - GEN
T1 - RASP
T2 - 1st ACM Conference on Data and Application Security and Privacy, CODASPY'11
AU - Chen, Keke
AU - Kavuluru, Ramakanth
AU - Guo, Shumin
PY - 2011
Y1 - 2011
N2 - Range query is one of the most frequently used queries for online data analytics. Providing such a query service could be expensive for the data owner. With the development of services computing and cloud computing, it has become possible to outsource large databases to database service providers and let the providers maintain the range-query service. With outsourced services, the data owner can greatly reduce the cost in maintaining computing infrastructure and data-rich applications. However, the service provider, although honestly processing queries, may be curious about the hosted data and received queries. Most existing encryption based approaches require linear scan over the entire database, which is inappropriate for online data analytics on large databases. While a few encryption solutions are more focused on efficiency side, they are vulnerable to attackers equipped with certain prior knowledge. We propose the Random Space Encryption (RASP) approach that allows efficient range search with stronger attack resilience than existing efficiency-focused approaches. We use RASP to generate indexable auxiliary data that is resilient to prior knowledge enhanced attacks. Range queries are securely transformed to the encrypted data space and then efficiently processed with a two-stage processing algorithm. We thoroughly studied the potential attacks on the encrypted data and queries at three different levels of prior knowledge available to an attacker. Experimental results on synthetic and real datasets show that this encryption approach allows efficient processing of range queries with high resilience to attacks.
AB - Range query is one of the most frequently used queries for online data analytics. Providing such a query service could be expensive for the data owner. With the development of services computing and cloud computing, it has become possible to outsource large databases to database service providers and let the providers maintain the range-query service. With outsourced services, the data owner can greatly reduce the cost in maintaining computing infrastructure and data-rich applications. However, the service provider, although honestly processing queries, may be curious about the hosted data and received queries. Most existing encryption based approaches require linear scan over the entire database, which is inappropriate for online data analytics on large databases. While a few encryption solutions are more focused on efficiency side, they are vulnerable to attackers equipped with certain prior knowledge. We propose the Random Space Encryption (RASP) approach that allows efficient range search with stronger attack resilience than existing efficiency-focused approaches. We use RASP to generate indexable auxiliary data that is resilient to prior knowledge enhanced attacks. Range queries are securely transformed to the encrypted data space and then efficiently processed with a two-stage processing algorithm. We thoroughly studied the potential attacks on the encrypted data and queries at three different levels of prior knowledge available to an attacker. Experimental results on synthetic and real datasets show that this encryption approach allows efficient processing of range queries with high resilience to attacks.
KW - Attack analysis
KW - Multidimensional range query
KW - Outsourced databases
KW - Random space encryption
UR - http://www.scopus.com/inward/record.url?scp=79952779059&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79952779059&partnerID=8YFLogxK
U2 - 10.1145/1943513.1943547
DO - 10.1145/1943513.1943547
M3 - Conference contribution
AN - SCOPUS:79952779059
SN - 9781450304665
T3 - CODASPY'11 - Proceedings of the 1st ACM Conference on Data and Application Security and Privacy
SP - 249
EP - 260
BT - CODASPY'11 - Proceedings of the 1st ACM Conference on Data and Application Security and Privacy
Y2 - 21 February 2011 through 23 February 2011
ER -