Welcome to the resource topic for
**2017/1131**

**Title:**

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

**Authors:**
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.

**ePrint:**
https://eprint.iacr.org/2017/1131

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .