On the pseudo-freeness and the CDH assumption

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.