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 .