Presentation 2004-09-17
New Notions of Security for Public-Key Cryptosystems with Adversarial Random Oracles (Survey)
Mototsugu NISHIOKA,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) We have begun studying of the security of public-key encryption schemes with adversarial random oracles. Informally, an adversarial random oracle means a random oracle that is secretly set as a trap by an adversary. We first present new security notions, SEC-ATK+ and SEC-ATK++ (SEC ∈ {OW,IND,NM}, ATK ∈ {CPA,CCA1,CCA2}), which are strengthened versions of SEC-ATK in the random oracle model. In the definitions of previous security notions (e.g., IND-CCA1, NM-CCA1, and IND-CCA2), the random oracles are given fairly. The definition of SEC-ATK+, however, allows an adversary to determine adversarial random oracles before the underlying public key is given, while the definition of SEC-ATK++ allows the adversary to determine the adversarial random oracles even after the underlying public key has been given. That is, in these attacks, the adversary can force users to use malicious random oracles to break the encryption scheme. We show that many known public-key encryption schemes that are secure in the sense of IND-CCA2 can be completely broken, or that have some cases in which they are broken, by an adversary with this additional power. It follows that "PA, IND-CCA2 〓 OW-CPA+". Thus, our new security notions provide stronger security than previous notions. Next, we present the extended notions of "semantic security" and "indistinguishable security" in order to give the conditions required for a public-key encryption scheme to be secure against an attack with adversarial random oracles, and we show that "H-IND-DCPA ⇒ IND-CPA++" and "H-IND-DCCA3 ⇒ IND-CCA2-". Finally, we present a new, practical public-key encryption scheme that is secure in the sense of IND-CCA2++.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) public-key encryption scheme / random oracle / chosen-ciphertext attack / semantic security / indistinguishable security / plaintext awareness
Paper # ISEC2004-76
Date of Issue

Conference Information
Committee ISEC
Conference Date 2004/9/10(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To Information Security (ISEC)
Language ENG
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) New Notions of Security for Public-Key Cryptosystems with Adversarial Random Oracles (Survey)
Sub Title (in English)
Keyword(1) public-key encryption scheme
Keyword(2) random oracle
Keyword(3) chosen-ciphertext attack
Keyword(4) semantic security
Keyword(5) indistinguishable security
Keyword(6) plaintext awareness
1st Author's Name Mototsugu NISHIOKA
1st Author's Affiliation Systems Lab, HITACHI, Ltd()
Date 2004-09-17
Paper # ISEC2004-76
Volume (vol) vol.104
Number (no) 315
Page pp.pp.-
#Pages 8
Date of Issue