Paper 2009/512

Public-Key Encryption in the Bounded-Retrieval Model

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

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.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Leakage ResilienceBounded Retreival ModelIBE
Contact author(s)
wichs @ cs nyu edu
History
2009-10-28: revised
2009-10-26: received
See all versions
Short URL
https://ia.cr/2009/512
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/512,
      author = {Joel Alwen and Yevgeniy Dodis and Moni Naor and Gil Segev and Shabsi Walfish and Daniel Wichs},
      title = {Public-Key Encryption in the Bounded-Retrieval Model},
      howpublished = {Cryptology ePrint Archive, Paper 2009/512},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/512}},
      url = {https://eprint.iacr.org/2009/512}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.