Paper 2012/220

Hedged Public-key Encryption: How to Protect against Bad Randomness

Mihir Bellare, Zvika Brakerski, Moni Naor, Thomas Ristenpart, Gil Segev, Hovav Shacham, and Scott Yilek

Abstract

Public-key encryption schemes rely for their IND-CPA security on per-message fresh randomness. In practice, randomness may be of poor quality for a variety of reasons, leading to failure of the schemes. Expecting the systems to improve is unrealistic. What we show in this paper is that we can, instead, improve the cryptography to offset the lack of possible randomness. We provide public-key encryption schemes that achieve IND-CPA security when the randomness they use is of high quality, but, when the latter is not the case, rather than breaking completely, they achieve a weaker but still useful notion of security that we call IND-CDA. This hedged public-key encryption provides the best possible security guarantees in the face of bad randomness. We provide simple RO-based ways to make in-practice IND-CPA schemes hedge secure with minimal software changes. We also provide non-RO model schemes relying on lossy trapdoor functions (LTDFs) and techniques from deterministic encryption. They achieve adaptive security by establishing and exploiting the anonymity of LTDFs which we believe is of independent interest.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Preliminary version appeared at Asiacrypt 2009
Contact author(s)
rist @ cs wisc edu
History
2012-04-22: received
Short URL
https://ia.cr/2012/220
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/220,
      author = {Mihir Bellare and Zvika Brakerski and Moni Naor and Thomas Ristenpart and Gil Segev and Hovav Shacham and Scott Yilek},
      title = {Hedged Public-key Encryption: How to Protect against Bad Randomness},
      howpublished = {Cryptology ePrint Archive, Paper 2012/220},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/220}},
      url = {https://eprint.iacr.org/2012/220}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.