Multi-Key Searchable Encryption

Raluca Ada Popa (MIT/CSAIL), Emily Stark (Meteor), Steven Valdez, Jonas Helfer, Nickolai Zeldovich, Hari Balakrishnan (MIT/CSAIL); Building Web Applications on Top of Encrypted Data Using Mylar; Usenix Symposium on Networks Systems Design and Implementation (NSDI); 2014-04-02; landing.


Web applications rely on servers to store and process confidential information. However, anyone who gains access to the server (e.g., an attacker, a curious administrator, or a government) can obtain all of the data stored there. This paper presents Mylar, a platform for building web applications, which protects data confidentiality against attackers with full access to servers. Mylar stores sensitive data encrypted on the server, and decrypts that data only in users’ browsers. Mylar addresses three challenges in making this approach work. First, Mylar allows the server to perform keyword search over encrypted documents, even if the documents are encrypted with different keys. Second, Mylar allows users to share keys and encrypted data securely in the presence of an active adversary. Finally, Mylar ensures that client-side application code is authentic, even if the server is malicious. Results with a prototype of Mylar built on top of the Meteor framework are promising: porting 6 applications required changing just 36 lines of code on average, and the performance overheads are modest, amounting to a 17% throughput loss and a 50 ms latency increase for sending a message in a chat application.

Raluca Ada Popa, Nickolai Zeldovich; Multi-Key Searchable Encryption; Cryptology ePrint Archive, 2013/508; 18 pages; landing.


We construct a searchable encryption scheme that enables keyword search over data encrypted with {\em different} keys. The scheme is practical and was designed to be included in a new system for protecting data confidentiality in client-server applications against attacks on the server.


  • Problem Statement
    • (distributed) key generation
    • (centralized) document storage
    • document sharing with access controls
    • an access graph
    • document search capability
  • Multiple users keys, multiple document keys
  • Scheme
    • search token
    • delta of the token
    • adjust converts deltas from user key to document keys
  • Definition of Multi-Key Search (MK), page 4
    • MK.Setup
    • MK.KeyGen
    • MK.Delta
    • MK.Token
    • MK.Enc
    • MK.Adjust
    • MK.Match
  • Assumptions
    • Bilinear Diffie-Hellman Variant (BDHV)
    • External Diffie-Hellman Variant (XDHV)
  • Fully-Homomorphic Encryption (FHE)
  • MHC Protocol
  • Implementation

Via: backfill

The Darknet and the Future of Content Distribution

Four dudes (Microsoft); The Darknet and the Future of Content Distribution; In Digital Rights Management Workshop; Washington DC, 2002-11-18; memorialized as Lecture Notes in Computer Science 2696 Springer 2003, ISBN 3-540-40410-4.

Timothy B. Lee; How 4 Microsoft engineers proved that the “darknet” would defeat DRM; In Ars Technica; 2012-11-30.

Not clear now all this gushing “DRM is doomed to fail” can even be considered anything but laughable now that Microsoft has created the locked, signed UEFI bootloader and effectively closed off the Intel platforms from loading anything but signed Microsoft code. None of the teleology in the second part of the piece will be true once the lockdown bios becomes ubiquitous. Think 3 years as the current generation of “open” PC-class machines age out and are replaced with the new closed lockdown platform that can only run Microsoft’s OS.


  • Palladium
  • TCPA
  • Next-Generation Secure Computing Base