Cryptology ePrint Archive: Report 2012/014

On Indifferentiable Hash Functions in Multi-Stage Security Games

Yusuke Naito and Kazuki Yoneyama and Kazuo Ohta

Abstract: Ristenpart, Shacham, and Shrimpton (EUROCRYPT 2011) demonstrated that for multi-stage security games, composability of indifferentiable hash functions does not sufficiently work. An open problem from their result is how to obtain multi-stage security when a random oracle (RO) is replaced with indifferentiable hash functions. In this paper, we positively solve this problem so that for a large class of public key encryption (PKE) scheme and ID-based encryption (IBE) scheme an important multi-stage security, the CDA security, is obtained even when the RO is replaced with important indifferentiable hash functions, Sponge, Prefix-free Merkle-Damg{\aa}rd, or chop Merkle-Damg{\aa}rd. Especially, Sponge is employed in the SHA-3 winner Keccak. First, we introduce a new weakened RO model, called Versatile Oracle ($\vo$) model, as a tool for bridging the multi-stage security and such hash functions. We prove {\it reset} indifferentiability of these hash functions from a $\vo$; thus, if a cryptosystem is secure in the $\vo$ model, then it is also secure when instantiating the $\vo$ by these hash functions. Next, we show that if a PKE or IBE scheme satisfies the CPA security in the RO model, then there exists a CDA secure PKE or IBE scheme in the $\vo$ model. Combining these two results, we have that for a large class of PKE and IBE schemes the CDA security is guaranteed when the RO is replaced with a large class of practical hash functions.

Category / Keywords: indifferentiability, reset indifferentiability, multi-stage security game

Date: received 9 Jan 2012, last revised 3 Mar 2013

Contact author: Naito Yusuke at ce MitsubishiElectric co jp

Available formats: PDF | BibTeX Citation

Note: The paper is updated according to the result of SHA-3 competition. A result of IBE is added.

Version: 20130304:002612 (All versions of this report)

Discussion forum: Show discussion | Start new discussion