Cloud-based data is securely retrieved by obfuscating access patterns. A cloud storage system receives a request for data from a remote client that specifies a key. Thereafter, the cloud storage system iterates through an index to identify all locations corresponding to the specified key. Such index is generated by applying a series of j hash functions to each key resulting in a j different tables forming part of the index. Using the index, the cloud storage system returns data from the identified locations to the client. As each write operation works by using non-deterministic encryption, the write operation changes the records stored in this data structure, and when the record is not changed, the algorithm simply rewrites the data which is stored in the data structure by rewriting the same value back again. However since, a nondeterministic encryption is utilized, it makes it indistinguishable as to when new data was written and when existing data is rewritten.