Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #5 to TR12-114 | 20th April 2019 23:50

#### Constructing a Pseudo-Free Family of Finite Computational Groups under the General Integer Factoring Intractability Assumption

Revision #5
Authors: Mikhail Anokhin
Accepted on: 20th April 2019 23:50
Keywords:

Abstract:

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.

Changes to previous version:

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

Revision #4 to TR12-114 | 21st March 2015 18:16

#### Constructing a Pseudo-Free Family of Finite Computational Groups under the General Integer Factoring Intractability Assumption

Revision #4
Authors: Mikhail Anokhin
Accepted on: 21st March 2015 18:16
Keywords:

Abstract:

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.

Changes to previous version:

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

Revision #3 to TR12-114 | 22nd May 2013 15:37

#### Constructing a Pseudo-Free Family of Finite Computational Groups under the General Integer Factoring Intractability Assumption

Revision #3
Authors: Mikhail Anokhin
Accepted on: 22nd May 2013 15:37
Keywords:

Abstract:

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.

Changes to previous version:

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.

Revision #2 to TR12-114 | 18th October 2012 12:32

#### Constructing a Pseudo-Free Family of Finite Computational Groups under the General Integer Factoring Intractability Assumption

Revision #2
Authors: Mikhail Anokhin
Accepted on: 18th October 2012 12:32
Keywords:

Abstract:

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.

Changes to previous version:

A grammatical error in the abstract was corrected.

Revision #1 to TR12-114 | 13th October 2012 16:48

#### Constructing a Pseudo-Free Family of Finite Computational Groups under the General Integer Factoring Intractability Assumption

Revision #1
Authors: Mikhail Anokhin
Accepted on: 13th October 2012 16:48
Keywords:

Abstract:

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.

Changes to previous version:

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

### Paper:

TR12-114 | 15th July 2012 17:36

#### Constructing a Pseudo-Free Family of Finite Computational Groups under the General Integer Factoring Intractability Assumption

TR12-114
Authors: Mikhail Anokhin
Publication: 7th September 2012 14:01