Cryptology ePrint Archive: Report 2013/331

New Constructions and Applications of Trapdoor DDH Groups

Yannick Seurin

Abstract: Trapdoor Decisional Diffie-Hellman (TDDH) groups, introduced by Dent and Galbraith (ANTS 2006), are groups where the DDH problem is hard, unless one is in possession of a secret trapdoor which enables solving it efficiently. Despite their intuitively appealing properties, they have found up to now very few cryptographic applications. Moreover, among the two constructions of such groups proposed by Dent and Galbraith, only a single one based on hidden pairings remains unbroken. In this paper, we extend the set of trapdoor DDH groups by giving a construction based on composite residuosity. We also introduce a more restrictive variant of these groups that we name \emph{static} trapdoor DDH groups, where the trapdoor only enables to solve the DDH problem with respect to a fixed pair $(G,G^x)$ of group elements. We give two constructions for such groups whose security relies respectively on the RSA and the factoring assumptions. Then, we show that static trapdoor DDH groups yield elementary constructions of convertible undeniable signature schemes allowing delegatable verification. Using our constructions of static trapdoor DDH groups from the RSA or the factoring assumption, we obtain slightly simpler variants of the undeniable signature schemes of respectively Gennaro, Rabin, and Krawczyk (J. Cryptology, 2000) and Galbraith and Mao (CT-RSA 2003). These new schemes are conceptually more satisfying since they can strictly be viewed as instantiations, in an adequate group, of the original undeniable signature scheme of Chaum and van Antwerpen (CRYPTO~'89).

Category / Keywords: public-key cryptography / trapdoor DDH group, hidden pairing, signed quadratic residues, convertible undeniable signature scheme

Publication Info: An abridged version appears at PKC 2013. This is the full version.

Date: received 29 May 2013

Contact author: yannick seurin at m4x org

Available format(s): PDF | BibTeX Citation

Version: 20130602:170459 (All versions of this report)

Short URL: ia.cr/2013/331

Discussion forum: Show discussion | Start new discussion