Paper 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).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. An abridged version appears at PKC 2013. This is the full version.
Keywords
trapdoor DDH grouphidden pairingsigned quadratic residuesconvertible undeniable signature scheme
Contact author(s)
yannick seurin @ m4x org
History
2013-06-02: received
Short URL
https://ia.cr/2013/331
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/331,
      author = {Yannick Seurin},
      title = {New Constructions and Applications of Trapdoor DDH Groups},
      howpublished = {Cryptology ePrint Archive, Paper 2013/331},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/331}},
      url = {https://eprint.iacr.org/2013/331}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.