**A Certain Family of Subgroups of $\mathbb Z_n^\star$ Is Weakly Pseudo-Free under the General Integer Factoring Intractability Assumption**

*Mikhail Anokhin*

**Abstract: **Let $\mathbb G_n$ be the subgroup of elements of odd order in the group $\mathbb Z_n^\star$ and let $\mathcal U(\mathbb G_n)$ be the uniform probability distribution on $\mathbb G_n$. In this paper, we establish a probabilistic polynomial-time reduction from finding a nontrivial divisor of a composite number $n$ to finding a nontrivial relation between $l$ elements chosen independently and uniformly at random from $\mathbb G_n$, where $l\ge1$ is given in unary as a part of the input. Assume that finding a nontrivial divisor of a random number in some set $N$ of composite numbers (for a given security parameter) is a computationally hard problem. Then, using the above-mentioned reduction, we prove that the family $\{(\mathbb G_n,\mathcal U(\mathbb G_n))\}_{n\in N}$ of computational abelian groups is weakly pseudo-free. The disadvantage of this result is that the probability ensemble $\{\mathcal U(\mathbb G_n)\}_{n\in N}$ is not polynomial-time samplable. To overcome this disadvantage, we construct a polynomial-time computable function $\nu\colon D\to N$ (where $D\subseteq\{0,1\}^*$) and a polynomial-time samplable probability ensemble $\{\mathcal G_d\}_{d\in D}$ (where $\mathcal G_d$ is a distribution on $\mathbb G_{\nu(d)}$ for each $d\in D$) such that the family $\{(\mathbb G_{\nu(d)},\mathcal G_d)\}_{d\in D}$ of computational abelian groups is weakly pseudo-free.

**Category / Keywords: **foundations / families of computational groups, weak pseudo-freeness, abelian groups, factoring

**Original Publication**** (with major differences): **Groups, Complexity, Cryptology, 10(2):99-110, November 2018
**DOI: **10.1515/gcc-2018-0007

**Date: **received 22 Nov 2017, last revised 6 Nov 2018

**Contact author: **anokhin at mccme ru

**Available format(s): **PDF | BibTeX Citation

**Note: **We have added a reference to the journal version of the paper, changed equation numbering style, and made some other minor changes.

**Version: **20181106:145703 (All versions of this report)

**Short URL: **ia.cr/2017/1131

[ Cryptology ePrint archive ]