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.