Cryptology ePrint Archive: Report 2016/541

Big-Key Symmetric Encryption: Resisting Key Exfiltration

Mihir Bellare and Daniel Kane and Phillip Rogaway

Abstract: 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.

Category / Keywords: Big-key cryptography, bounded-retrieval model, key exfiltration, leakage resilience, mass surveillance, symmetric encryption

Original Publication (with major differences): IACR-CRYPTO-2016

Date: received 31 May 2016, last revised 21 Sep 2016

Contact author: mihir at eng ucsd edu

Available format(s): PDF | BibTeX Citation

Version: 20160921:234152 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]