Microsoft co-develops way to sidestep cloud data privacy concerns

Do the Melbourne shuffle to reduce risk of data leakage, say researchers

Cloud customers could have greater peace of mind thanks to new research from Microsoft, the University of California and Brown University. The researchers have proposed a new way to make data stored in the cloud more secure and private.

In a report entitled The Melbourne Shuffle: Improving Oblivious Storage in the Cloud, co-authors Olga Ohrimenko, Michael T Goodrich, Roberto Tamassia and Eli Upfal argue that encryption is not enough to protect information stored in clouds from data mining carried out by storage providers or from potential government searches.

“The data access patterns that users exhibit can reveal information about the content of their data,” the researchers claimed.

Data-oblivious shuffling, where data access patterns are hidden through a series of dummy requests and the continuous internal cycling of the data within the cloud service, is one way of dealing with this problem.

However, the algorithms used to do this are costly in terms of both time and money, Ohrimenko et al claim.

Therefore, they have devised a process based on card shuffling that, they claim, could successfully disguise the true nature of the data being accessed without making it prohibitively expensive.

Dubbed the Melbourne shuffle, it focuses on obfuscating the data most likely to be sought by someone trying to spy on transactions, called “probabilistic encryption”.

“Everything stored at the server is encrypted and every time an item is read from the server, the user decrypts it, re-encrypts it and writes it back. Since we use CPA- secure encryption, the ciphertexts produced for the same item always look different and, hence, the server, aka the adversary, cannot tell whether the ciphertexts correspond to the same item or not,” the researchers explain.

“The goal of our oblivious shuffle is to reveal to the adversary only information that she would expect to see in a random permutation with very high probability.”

It also uses dummy items – real items of data with a fake key and nonce value (an arbitrary number used only once) – as a decoy.

Furthermore, the team claims to have optimised the Melbourne shuffle for the cloud, given that most cloud storage providers charge for memory usage and IOPS.

The full research, including methodology and example uses, can be read here.