Paper 2016/678

Anonymous RAM

Michael Backes, Amir Herzberg, Aniket Kate, and Ivan Pryvalov

Abstract

We define the concept of and present provably secure constructions for Anonymous RAM (AnonRAM), a novel multi-user storage primitive that offers strong privacy and integrity guarantees. AnonRAM combines privacy features of anonymous communication and oblivious RAM (ORAM) schemes, allowing it to protect, simultaneously, the privacy of content, access patterns and user’s identity, from curious servers and from other (even adversarial) users. AnonRAM further protects integrity, i.e., it prevents malicious users from corrupting data of other users. We present two secure AnonRAM schemes, differing in design and time-complexity. The first scheme has simpler design; like efficient ORAM schemes, its time-complexity is poly-logarithmic in the number of cells (per user), however, it is linear in the number of users. The second AnonRAM scheme reduces the overall complexity to poly-logarithmic in the total number of cells (of all users), at the cost of requiring two (non-colluding) servers.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
anonymityaccess privacyoblivious RAMout-sourced data(universal) re-randomizable encryptionoblivious PRF
Contact author(s)
pryvalov @ cs uni-saarland de
History
2016-07-06: received
Short URL
https://ia.cr/2016/678
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/678,
      author = {Michael Backes and Amir Herzberg and Aniket Kate and Ivan Pryvalov},
      title = {Anonymous RAM},
      howpublished = {Cryptology ePrint Archive, Paper 2016/678},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/678}},
      url = {https://eprint.iacr.org/2016/678}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.