**Pseudo-Free Families of Finite Computational Elementary Abelian $p$-Groups**

*Mikhail Anokhin*

**Abstract: **Loosely speaking, a family of computational groups is a family $(G_d)_{d\in D}$ of groups (where $D$ is a set of bit strings) whose elements are represented by bit strings in such a way that equality testing, multiplication, inversion, computing the identity element, and sampling random elements in $G_d$ can be performed efficiently when $d$ is given. A family $(G_d)_{d\in D}$ of computational groups is called pseudo-free if, given a random index $d$ (for an arbitrary value of the security parameter) and random elements $g_1,\ldots,g_m\in G_d$, it is computationally hard to find a system of group equations $v_i(a_1,\ldots,a_m;x_1,\ldots,x_n)=w_i(a_1,\ldots,a_m;x_1,\ldots,x_n)$, $i=1,\ldots,s$, and elements $h_1,\ldots,h_n\in G_d$ such that this system of equations is unsatisfiable in the free group freely generated by $a_1,\ldots,a_m$ (over variables $x_1,\ldots,x_n$), but $v_i(g_1,\ldots,g_m;h_1,\ldots,h_n)=w_i(g_1,\ldots,g_m;h_1,\ldots,h_n)$ in $G_d$ for all $i\in\{1,\ldots,s\}$. If a family of computational groups satisfies this definition with the additional requirement that $n=0$, then this family is said to be weakly pseudo-free. The definition of a (weakly) pseudo-free family of computational groups can be easily generalized to the case when all groups in the family belong to a fixed variety of groups.

In this paper, 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 $(G_d)_{d\in D}$ of computational elementary abelian $p$-groups 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.

**Category / Keywords: **families of computational groups, pseudo-freeness, weak pseudo-freeness, elementary abelian $p$-groups, homomorphic family of functions, collision-intractability, one-way functions, hash functions

**Original Publication**** (with minor differences): **Groups - Complexity - Cryptology, 9(1):1-18, May 2017
**DOI: **10.1515/gcc-2017-0001

**Date: **received 22 Nov 2015, last revised 7 May 2017

**Contact author: **anokhin at mccme ru

**Available format(s): **PDF | BibTeX Citation

**Note: **We have added a reference to the journal version of the paper, made the submission MathJax friendly, changed equation numbering style, and fixed some typos.

**Version: **20170507:201006 (All versions of this report)

**Short URL: **ia.cr/2015/1127

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]