Hedged Public-Key Encryption: How to Protect Against Bad Randomness
Authors:
Mihir Bellare,
Zvika Brakerski,
Moni Naor,
Thomas Ristenpart,
Gil Segev, and
Hovav Shacham, and
Scott Yilek,
Abstract:
Public-key encryption schemes rely for their IND-CPA security on per-message fresh random-
ness. 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 en-
cryption 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.
References:
Proceedings of Advances in Cryptology -- Asiacrypt '09
Versions:
Full version will be coming soon.
List of Updates: