Defending Against Key Exfiltration: Efficiency Improvements for Big-Key Cryptography via Large-Alphabet Subkey Prediction
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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Related papers
- SEAL: Attack Mitigation for Encrypted Databases via Adjustable LeakageIoannis Demertzis, Dimitrios Papadopoulos, Charalampos Papamanthou, Saurabh ShintreUSENIX Security 2020
- Fast and Secure Updatable EncryptionColin Boyd, Gareth T. Davies, Kristian Gjøsteen, Yao JiangCRYPTO 2020 · 52 citations
- Generic Attacks on Secure Outsourced DatabasesGeorgios Kellaris, George Kollios, Kobbi Nissim, Adam O'NeillCCS 2016 · 327 citations
- Uncompressing Dilithium's Public KeyPaco Azevedo Oliveira, Andersson Calle Viera, Benoît Cogliati, Louis GoubinCRYPTO 2025 · 10 citations
- Realizing Flexible Broadcast Encryption: How to Broadcast to a Public-Key DirectoryRachit Garg, George Lu, Brent Waters, David J. WuCCS 2023 · 6 citations
