|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
A Certain Family of Subgroups of Z_n^* Is Weakly Pseudo-Free under the General Integer Factoring Intractability Assumptionстатья Электронная публикация
- Автор: Anokhin M.
- Журнал: Cryptology ePrint Archive
- Номер: 1131
- Год издания: 2017
- Аннотация: 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.
- Добавил в систему: Анохин Михаил Игоревич