BigGate: Access Control Framework for Outsourced Key-Value Stores

Due to its scalable design, key-value stores have become the backbone of many large-scale Internet companies that need to cope with millions of transactions every day. It is also an attractive cloud outsourcing technology: driven by economical benefits, many major companies like Amazon, Google, and Microsoft provide key-value storage services to their customers. However, customers are reluctant to utilize such services due to security and privacy concerns. Outsourced sensitive key-value data (e.g., social security numbers as keys, and health reports as value) may be stolen by third-party adversaries and/or malicious insiders. Furthermore, an institution, who is utilizing key-value storage services, may naturally desire to have access control mechanisms among its departments or users, while leaking as little information as possible to the cloud provider to preserve data privacy. We believe that addressing these security and privacy concerns are crucial in further adoption of key-value storage services. In this paper, we present a novel system, BigGate, that provides secure outsourcing and efficient processing of encrypted key-value data, and enforces access control policies. We formally prove the security of our system, and by carefully implemented empirical analysis, show that the overhead induced by \sysname can be as low as 2%.