How encryption with standard security copes under stronger forms of attack, with applications to computational soundness
Mohammad Hajiabadi
Abstract:
Key-dependent message (KDM) security allows the exposure of encryptions of functions of a secret key without jeopardizing the key's "secrecy". It is by now known how to realize basic forms of KDM security (e.g., circular security) under a variety of cryptographic assumptions. It is also known that certain types of key-cycles are not secure for encryption schemes with standard semantic security.
In this talk we consider to what extent any encryption scheme with standard security withstands stronger forms of attack, including adaptive corruption of keys and certain forms of KDM attack. We consider a multiple-key-based encryption-indistinguishability experiment and, in addition to standard attacks, we allow the adversary to adaptively perform certain forms of KDM attack as well as the ability to adaptively corrupt keys, all performed in a possibly interleaving fashion. The mixture of adaptive corruptions and KDM attacks make this problem especially interesting as one needs to argue about secrecy of keys which, e.g., are not trivially corrupted. We ask, without relying on additional assumptions and assuming only semantic security, can we prove at the end of the game that certain keys still maintain "computational secrecy"? To this end, we characterize a "benign" form of circular encryption, and show that, if a certain condition is met, the secrecy of any key which is not trivially corrupted and appears only in benign key-cycles reduces to semantic security of the scheme.
Finally we show an application of this result in the context of "computationally-sound symbolic security", by proving a computational soundness theorem which allows one to generically instantiate (under standard encryption primitives) certain symbolic encryption-based protocols in such a way that if the protocol is symbolically-secure then the resulting instantiation is computationally secure against active, adaptively-corrupting adversaries.
(Joint work with Bruce Kapron)
Slides: [ pdf ]