The Melbourne shuffle algorithm is a method of obscuring the patterns by which cloud-based data is accessed to prevent unauthorized parties from gathering information about the data.
Although data itself may be encrypted, details about the patterns of data access can be revealing. If an attacker can detect the actions of users as they access cloud-based data, they may be able to identify access patterns that suggest the content of that data or activities of the organization that owns the data.
For one example, when a company is about to make stock price-sensitive announcements, there may be an increase in how many times files in particular locations are accessed. An attacker watching for that kind of behavior could recognize the correlation and possibly take advantage of it, even without knowing what information is contained in those files. Access patterns can also allow an intruder to identify the types of programs running against data in a database.
The Melbourne shuffle algorithm moves small pieces of data from the cloud server to the user’s local memory. The pieces of data are then rearranged and returned to the server. That process is repeated until all the data has been moved to a new location on the cloud server. Shuffling the data between locations in this way makes data access pattern recognition ineffectual — even if a user repeatedly accesses the same data — because data is continuously being moved to a different location.
Koki Hamada, Dai Ikarashi, Koji Chida and Katsumi Takahashi published the algorithm in a paper entitled “The Melbourne Shuffle: Improving Oblivious Storage in the Cloud. They named the algorithm for a rave and club dance that arose in the early 1990s, described by The Age, a daily newspaper in Melbourne, Australia as resembling “a cross between the chicken dance and a foot stomping robot.”