|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Pseudo-Free Families of Finite Computational Elementary Abelian p-Groupsстатья Электронная публикация
- Автор: Anokhin Mikhail
- Журнал: Cryptology ePrint Archive
- Номер: 1127
- Год издания: 2015
- Аннотация: We initiate the study of (weakly) pseudo-free families of computational elementary abelian $p$-groups, where $p$ is an arbitrary fixed prime. We restrict ourselves to families of computational elementary abelian $p$-groups $G_d$ such that for every index $d$, each element of $G_d$ is represented by a single bit string of length polynomial in the length of $d$. First, we prove that pseudo-freeness and weak pseudo-freeness for families of computational elementary abelian $p$-groups are equivalent. Second, we give some necessary and sufficient conditions for a family of computational elementary abelian $p$-groups to be pseudo-free (provided that at least one of two additional conditions holds). These necessary and sufficient conditions are formulated in terms of collision-intractability or one-wayness of certain homomorphic families of knapsack functions. Third, we establish some necessary and sufficient conditions for the existence of pseudo-free families of computational elementary abelian $p$-groups. With one exception, these conditions are the existence of certain homomorphic collision-intractable families of $p$-ary hash functions or certain homomorphic one-way families of functions. As an example, we construct a Diffie-Hellman-like key agreement protocol from an arbitrary family of computational elementary abelian $p$-groups. Unfortunately, we do not know whether this protocol is secure under reasonable assumptions.
- Добавил в систему: Анохин Михаил Игоревич