Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

RSS-Feed




Revision #5
Authors: Mikhail Anokhin
Accepted on: 20th April 2019 23:50
Downloads: 277
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


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


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


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


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


Abstract:

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.



ISSN 1433-8092 | Imprint