Cryptology ePrint Archive: Report 2018/217

Defending Against Key Exfiltration: Efficiency Improvements for Big-Key Cryptography via Large-Alphabet Subkey Prediction

Mihir Bellare and Wei Dai

Abstract: Towards advancing the use of BIG keys as a practical defense against key exfiltration, this paper provides efficiency improvements for cryptographic schemes in the bounded retrieval model (BRM). We identify probe complexity (the number of scheme accesses to the slow storage medium storing the big key) as the dominant cost. Our main technical contribution is what we call the large-alphabet subkey prediction lemma. It gives good bounds on the predictability under leakage of a random sequence of blocks of the big key, as a function of the block size. We use it to significantly reduce the probe complexity required to attain a given level of security. Together with other techniques, this yields security-preserving performance improvements for BRM symmetric encryption schemes and BRM public-key identification schemes.

Category / Keywords: foundations / Random oracle model, bounded retrieval model, big-key cryptography, key exfiltration

Original Publication (with major differences): ACM CCS 2017

Date: received 22 Feb 2018

Contact author: weidai at eng ucsd edu

Available format(s): PDF | BibTeX Citation

Version: 20180226:195351 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]