Daniel Wichs

Public-Key Encryption in the Bounded-Retrieval Model

AUTHORS: Joel Alwen and Yevgeniy Dodis and Moni Naor and Gil Segev and
Shabsi Walfish and Daniel Wichs

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.


[ADNSWW09]: http://eprint.iacr.org/2009/512.pdf