Paper 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Major revision. ACM CCS 2017
DOI
10.1145/3133956.3133965
Keywords
Random oracle modelbounded retrieval modelbig-key cryptographykey exfiltration
Contact author(s)
weidai @ eng ucsd edu
History
2018-02-26: received
Short URL
https://ia.cr/2018/217
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/217,
      author = {Mihir Bellare and Wei Dai},
      title = {Defending Against Key Exfiltration: Efficiency Improvements for Big-Key Cryptography via Large-Alphabet Subkey Prediction},
      howpublished = {Cryptology ePrint Archive, Paper 2018/217},
      year = {2018},
      doi = {10.1145/3133956.3133965},
      note = {\url{https://eprint.iacr.org/2018/217}},
      url = {https://eprint.iacr.org/2018/217}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.