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

Mikhail Anokhin

Paper 2017/1131

A Certain Family of Subgroups of Is Weakly Pseudo-Free under the General Integer Factoring Intractability Assumption

Mikhail Anokhin

Abstract

Let be the subgroup of elements of odd order in the group and let be the uniform probability distribution on . In this paper, we establish a probabilistic polynomial-time reduction from finding a nontrivial divisor of a composite number to finding a nontrivial relation between elements chosen independently and uniformly at random from , where is given in unary as a part of the input. Assume that finding a nontrivial divisor of a random number in some set of composite numbers (for a given security parameter) is a computationally hard problem. Then, using the above-mentioned reduction, we prove that the family of computational abelian groups is weakly pseudo-free. The disadvantage of this result is that the probability ensemble is not polynomial-time samplable. To overcome this disadvantage, we construct a polynomial-time computable function (where ) and a polynomial-time samplable probability ensemble (where is a distribution on for each ) such that the family of computational abelian groups is weakly pseudo-free.

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

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Major revision. Groups, Complexity, Cryptology, 10(2):99-110, November 2018
DOI: 10.1515/gcc-2018-0007
Keywords: families of computational groups weak pseudo-freeness abelian groups factoring
Contact author(s): anokhin @ mccme ru
History: 2018-11-06: revised; 2017-11-27: received; See all versions
Short URL: https://ia.cr/2017/1131
License: CC BY

BibTeX

@misc{cryptoeprint:2017/1131,
      author = {Mikhail Anokhin},
      title = {A Certain Family of Subgroups of $\mathbb Z_n^\star$ Is Weakly Pseudo-Free under the General Integer Factoring Intractability Assumption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/1131},
      year = {2017},
      doi = {10.1515/gcc-2018-0007},
      url = {https://eprint.iacr.org/2017/1131}
}