Loosely speaking, a family of computational groups is a family of groups $(G_d)_{d\in D}$ (where $D\subseteq\{0,1\}^*$) whose elements are represented by bit strings in such a way that equality testing, multiplication, inversion, computing the identity element, and sampling random elements in $G_d$ can be performed efficiently when $d$ is given. A family of computational groups $(G_d)_{d\in D}$ is called pseudo-free if, given a random index $d$ (for an arbitrary value of the security parameter) and random elements $f_1,\dots,f_m\in G_d$, it is computationally hard to find a system of group equations $v_i(a_1,\dots,a_m;x_1,\dots,x_l)=w_i(a_1,\dots,a_m;x_1,\dots,x_l)$, $i=1,\dots,s$, and elements $g_1,\dots,g_l\in G_d$ such that this system of equations is unsatisfiable in the free group freely generated by $a_1,\dots,a_m$ (over variables $x_1,\dots,x_l$), but $v_i(f_1,\dots,f_m;g_1,\dots,g_l) =w_i(f_1,\dots,f_m;g_1,\dots,g_l)$ in $G_d$ for all $i\in\{1,\dots,s\}$.

In this paper, we construct a provably pseudo-free family of finite computational groups $(G_d)_{d\in D}$ under the general integer factoring intractability assumption. This family has exponential size, i.e., $|G_d|\le2^{\mathop{\mathrm{poly}}(|d|)}$ for all $d\in D$. But each element of $G_d$ (for any $d\in D$) is represented by infinitely many bit strings.

We provide a correct version of Remark 3.5 and fix a typo in Remark 4.4.

Loosely speaking, a family of computational groups is a family of groups $(G_d)_{d\in D}$ (where $D\subseteq\{0,1\}^*$) whose elements are represented by bit strings in such a way that equality testing, multiplication, inversion, computing the identity element, and sampling random elements in $G_d$ can be performed efficiently when $d$ is given. A family of computational groups $(G_d)_{d\in D}$ is called pseudo-free if, given a random index $d$ (for an arbitrary value of the security parameter) and random elements $f_1,\dots,f_m\in G_d$, it is computationally hard to find a system of group equations $v_i(a_1,\dots,a_m;x_1,\dots,x_l)=w_i(a_1,\dots,a_m;x_1,\dots,x_l)$, $i=1,\dots,s$, and elements $g_1,\dots,g_l\in G_d$ such that this system of equations is unsatisfiable in the free group freely generated by $a_1,\dots,a_m$ (over variables $x_1,\dots,x_l$), but $v_i(f_1,\dots,f_m;g_1,\dots,g_l) =w_i(f_1,\dots,f_m;g_1,\dots,g_l)$ in $G_d$ for all $i\in\{1,\dots,s\}$.

In this paper, we construct a provably pseudo-free family of finite computational groups $(G_d)_{d\in D}$ under the general integer factoring intractability assumption. This family has exponential size, i.e., $|G_d|\le2^{\mathop{\mathrm{poly}}(|d|)}$ for all $d\in D$. But each element of $G_d$ (for any $d\in D$) is represented by infinitely many bit strings.

We replaced the term "pseudo-random" by "pseudo-free" in the introduction and extended the abstract in the HTML representation (but not in the paper).

We construct a provably pseudo-free family of finite computational groups under the general integer factoring intractability assumption. This family has exponential size. But each element of a group in our pseudo-free family is represented by infinitely many bit strings.

1. We added a reference to the journal version of the paper.

2. The numbering of theorem-like structures was done as in the journal version of the paper (for convenience of citation).

3. Some other minor changes were made.

We construct a provably pseudo-free family of finite computational groups under the general integer factoring intractability assumption. This family has exponential size. But each element of a group in our pseudo-free family is represented by infinitely many bit strings.

A grammatical error in the abstract was corrected.

We construct a provably pseudo-free family of finite computational groups under the general integer factoring intractability assumption. This family has exponential size. But each element of a group in our pseudo-free family is represented by many bit strings.

We provide additional comments on some issues. Also, some minor changes were made.

We construct a provably pseudo-free family of finite computational groups under the general integer factoring intractability assumption. Moreover, this family has exponential size. But each element of a group in our pseudo-free family is represented by many bit strings.