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

Mototsugu NISHIOKA  Naohisa KOMATSU  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E94-A    No.2    pp.735-760
Publication Date: 2011/02/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E94.A.735
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Cryptography and Information Security
public-key encryption,  security reduction,  multi-user setting,  

Full Text: PDF(508KB)>>
Buy this Article

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 indistinguishability 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-CCABBM secure). These schemes never suffer from the underlying key length problem in the BBM model. We present three instances of an SR-invariant IND-CCABBM 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].