On the (Im)possibility Results for Strong Attack Models for Public Key Cryptsystems

Yutaka Kawai¹, Yusuke Sakai² and Noboru Kunihiro¹

¹University of Tokyo

5-1-5 Kashiwanoha, Kashiwa-shi

Chiba 277-8561, Japan

kawai@it.k.u-tokyo.ac.jp, kunihiro@k.u-tokyo.ac.jp

²The University of Electro-Communications

1-5-1 Chofugaoka, Chofu-shi, Tokyo 182-8585, Japan

y-sakai@uec.uec.ac.jp

Abstract

In this paper, we discuss the strong attack model security for public key encryption scheme and

digital signature scheme. Recently, Barbosa and Farshim introduced strong chosen ciphertext attack

(SCCA) which is stronger than chosen ciphertext attack. The main motivation of this paper is to find

an essential mechanism of secure schemes under strong attack model. So, we prove several impossibility

results under SCCA model. For the purpose, we classify two types of public key encryption

schemes: First model is ∏ = (Gen;Enc;Dec) which we call the setup-free model, second model is

∏ = (Setup;Gen;Enc;Dec) which we call the setup model. We prove that it is impossible to reduce

indistinguishability under strong chosen ciphertext attack (IND-SCCA) security to any other weaker

security notion under black-box analysis in the standard model. Second, when a public key encryption

scheme is modeled as ∏ = (Setup;Gen;Enc;Dec), we show that it is impossible that the security

of SCCA is proven if the reduction is setup-preserving black-box reductions which we define in this

paper. From the similar discussion, we prove impossibilities for digital signature schemes. Finally,

we discuss the essential mechanism to construct IND-SCCA secure public key encryption scheme in

the standard model.

Keywords: public key cryptsystems, attack models, encryptions