Abstract

Most encrypted data formats leak metadata via their plaintext headers, such as format version, encryption schemes used, number of recipients who can decrypt the data, and even the recipients’ identities. This leakage can pose security and privacy risks to users, e.g., by revealing the full membership of a group of collaborators from a single encrypted e-mail, or by enabling an eavesdropper to fingerprint the precise encryption software version and configuration the sender used. We propose that future encrypted data formats improve security and privacy hygiene by producing Padded Uniform Random Blobs or PUR Bs: ciphertexts indistinguishable from random bit strings to anyone without a decryption key. A PURB ’s content leaks nothing at all, even the application that created it, and is padded such that even its length leaks as little as possible. Encoding and decoding ciphertexts with no cleartext markers presents efficiency challenges, however. We present cryptographically agile encodings enabling legitimate recipients to decrypt a PURB efficiently, even when encrypted for any number of recipients’ public keys and/or passwords, and when these public keys are from different cryptographic suites. PUR Bs employ Padmé, a novel padding scheme that limits information leakage via ciphertexts of maximum length M to a practical optimum of O(loglog M) bits, comparable to padding to a power of two, but with lower overhead of at most 12% and decreasing with larger payloads.

Bio: Kirill Nikitin is a fifth-year Ph.D. student in the Decentralized/Distributed Systems lab at École polytechnique fédérale de Lausanne (EPFL) advised by Prof. Bryan Ford. His research spans the topics in Privacy, Systems Security, and Blockchains. His primary interest at the moment is on designing encryption schemes and security protocols that provide improved metadata protection. Currently, Kirill is doing an internship in the Confidential Computing group at Microsoft Research, Cambridge. For the detailed bio, see https://nikirill.com/.