|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
A certain family of subgroups of Z_n^* is weakly pseudo-free under the general integer factoring intractability assumptionстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 6 декабря 2018 г.
- Автор: Anokhin M.
- Журнал: Groups - Complexity - Cryptology
- Том: 10
- Номер: 2
- Год издания: 2018
- Издательство: Walter de Gruyter GmbH & Co. KG
- Местоположение издательства: Germany
- Первая страница: 99
- Последняя страница: 110
- DOI: 10.1515/gcc-2018-0007
- Аннотация: Let $\mathbb G_n$ be the subgroup of elements of odd order in the group $\mathbb Z_n^*$ 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: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.
- Добавил в систему: Анохин Михаил Игоревич