On the pseudo-freeness and the CDH assumption

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


The notion of pseudo-free group was first introduced by Hohenberger (Master's thesis, EECS Dept., MIT, 2003). Rivest (TCC 2004. LNCS 2951, 505-521, 2004) formalized it and showed that several standard cryptographic assumptions hold on pseudo-free groups, such as the RSA assumption, the strong RSA assumption and the discrete logarithm assumption. Rivest (TCC 2004. LNCS 2951, 505-521, 2004) also proposed some variations of pseudo-free group, and those were formalized by Hirano and Tanaka (Research Reports, Series C: Computer Science, C-239, Tokyo Institute of Technology, 2007). In this paper, we study the relationships among such variations of pseudo-free group. We show that the pseudo-freeness implies the weak pseudo-freeness, and that the pseudo- freeness is equivalent to the pseudo-freeness with generalized exponential expressions. We also show that the computational Diffie-Hellman assumption holds on pseudo-free groups in a slightly varied form.

Original languageEnglish
Pages (from-to)347-355
Number of pages9
JournalInternational Journal of Information Security
Issue number5
Publication statusPublished - 2009


  • CDH assumption
  • Pseudo-free group
  • Pseudo-free group with generalized exponential expressions
  • Weak pseudo-free group


Dive into the research topics of 'On the pseudo-freeness and the CDH assumption'. Together they form a unique fingerprint.

Cite this