Cryptology ePrint Archive: Report 2012/653

How powerful are the DDH hard groups?

Periklis A. Papakonstantinou and Charles W. Rackoff and Yevgeniy Vahlis

Abstract: The question whether Identity-Based Encryption (IBE) can be based on the Decisional Diffie-Hellman (DDH) assumption is one of the most prominent questions in Cryptography related to DDH. We study limitations on the use of the DDH assumption in cryptographic constructions, and show that it is impossible to construct a secure Identity-Based Encryption system using, in a black box way, only the DDH (or similar) assumption about a group. Our impossibility result is set in the generic groups model, where we describe an attack on any IBE construction that relies on oracle access to the group operation of randomly labelled group elements -- a model that formalizes naturally DDH hardness.

The vast majority of existing separation results typically give separation from general primitives, whereas we separate a primitive from a class of number theoretic hardness assumptions. Accordingly, we face challenges in creating an attack algorithm that will work against constructions which leverage the underlying algebraic structure of the group. In fact, we know that this algebraic structure is powerful enough to provide generic constructions for several powerful primitives including oblivious transfer and chosen ciphertext secure public-key cryptosystems (note that an IBE generalizes such systems). Technically, we explore statistical properties of the group algebra associated with a DDH oracle, which can be of independent interest.

Category / Keywords: foundations / Generic Groups, DDH, IBE, black-box separation

Publication Info: (first part of the result appears in the PhD thesis of P.A.Papakonstantinou (March 2010) )

Date: received 16 Nov 2012

Contact author: ppapakons at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20121121:184451 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]