Public-Key Encryptions with Invariant Security Reductions in the Multi-User Setting

摘要

In 1, Bellare, Boldyreva, and Micali addressed the security of public-key encryptions (PKEs) in a multi-user setting (called the BBM model in this paper). They showed that although the indistinguisha-bility in the BBM model is induced from that in the conventional model, its reduction is far from tight in general, and this brings a serious key length problem. In this paper, we discuss PKE schemes in which the IND-CCA security in the BBM model can be obtained tightly from the IND-CCA security. We call such PKE schemes IND-CCA secure in the BBM model with invariant security reductions {briefly, SR-invariant IND-CCA~(BBM) secure). These schemes never suffer from the underlying key length problem in the BBM model. We present three instances of an SR-invariant IND-CCA~(BBM) secure PKE scheme: the first is based on the Fujisaki-Okamoto PKE scheme 7, the second is based on the Bellare-Rogaway PKE scheme 3, and the last is based on the Cramer-Shoup PKE scheme 5.