Paper 2016/541

Big-Key Symmetric Encryption: Resisting Key Exfiltration

Mihir Bellare, Daniel Kane, and Phillip Rogaway


This paper aims to move research in the bounded retrieval model (BRM) from theory to practice by considering symmetric (rather than public-key) encryption, giving efficient schemes, and providing security analyses with sharp, concrete bounds. The threat addressed is malware that aims to exfiltrate a user's key. Our schemes aim to thwart this by using an enormously long key, yet paying for this almost exclusively in storage cost, not speed. Our main result is a general-purpose lemma, the subkey prediction lemma, that gives a very good bound on an adversary's ability to guess a (modest length) subkey of a big-key, the subkey consisting of the bits of the big-key found at random, specified locations, after the adversary has exfiltrated partial information about the big key (e.g., half as many bits as the big-key is long). We then use this to design a new kind of key encapsulation mechanism, and, finally, a symmetric encryption scheme. Both are in the random-oracle model. We also give a less efficient standard-model scheme that is based on universal computational extractors (UCE). Finally, we define and achieve hedged BRM symmetric encryption, which provides authenticity in the absence of leakage.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2016
Big-key cryptographybounded-retrieval modelkey exfiltrationleakage resiliencemass surveillancesymmetric encryption
Contact author(s)
mihir @ eng ucsd edu
2016-09-21: last of 3 revisions
2016-05-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mihir Bellare and Daniel Kane and Phillip Rogaway},
      title = {Big-Key Symmetric Encryption: Resisting Key Exfiltration},
      howpublished = {Cryptology ePrint Archive, Paper 2016/541},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.