Paper 2017/1131

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.

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 groupsweak pseudo-freenessabelian groupsfactoring
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.