Аннотация: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.