Public-Key Encryption in the Bounded-Retrieval Model
Venue
Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30 - June 3, 2010. Proceedings, Springer, pp. 113-134
Publication Year
2010
Authors
Joel Alwen, Yevgeniy Dodis, Moni Naor, Gil Segev, Shabsi Walfish, Daniel Wichs
BibTeX
Abstract
We construct the first public-key encryption scheme in the Bounded-Retrieval Model
(BRM), providing security against various forms of adversarial "key leakage"
attacks. In this model, the adversary is allowed to learn arbitrary information
about the decryption key, subject only to the constraint that the overall amount of
"leakage" is bounded by at most L bits. The goal of the BRM is to design
cryptographic schemes that can flexibly tolerate arbitrarily leakage bounds L (few
bits or many Gigabytes), by only increasing the size of secret key proportionally,
but keeping all the other parameters -- including the size of the public key,
ciphertext, encryption/decryption time, and the number of secret-key bits accessed
during decryption -— small and independent of L. As our main technical tool, we
introduce the concept of an Identity-Based Hash Proof System (IB-HPS), which
generalizes the notion of hash proof systems of Cramer and Shoup [CS02] to the
identity-based setting. We give three different constructions of this primitive
based on: (1) bilinear groups, (2) lattices, and (3) quadratic residuosity. As a
result of independent interest, we show that an IB-HPS almost immediately yields an
Identity-Based Encryption (IBE) scheme which is secure against (small) partial
leakage of the target identity’s decryption key. As our main result, we use IB-HPS
to construct public-key encryption (and IBE) schemes in the Bounded-Retrieval
Model.
