Paper 2015/1127

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,...,g_m\in G_d, it is computationally hard to find a system of group equations v_i(a_1,...,a_m;x_1,...,x_n)=w_i(a_1,...,a_m;x_1,...,x_n), i=1,...,s, and elements h_1,...,h_n\in G_d such that this system of equations is unsatisfiable in the free group freely generated by a_1,...,a_m (over variables x_1,...,x_n), but v_i(g_1,...,g_m;h_1,...,h_n)=w_i(g_1,...,g_m;h_1,...,h_n) in G_d for all i\in\{1,...,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.