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,\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.

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. Groups - Complexity - Cryptology, 9(1):1-18, May 2017
DOI
10.1515/gcc-2017-0001
Keywords
families of computational groupspseudo-freenessweak pseudo-freenesselementary abelian $p$-groupshomomorphic family of functionscollision-intractabilityone-way functionshash functions
Contact author(s)
anokhin @ mccme ru
History
2017-05-07: revised
2015-11-23: received
See all versions
Short URL
https://ia.cr/2015/1127
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1127,
      author = {Mikhail Anokhin},
      title = {Pseudo-Free Families of Finite Computational Elementary Abelian $p$-Groups},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1127},
      year = {2015},
      doi = {10.1515/gcc-2017-0001},
      note = {\url{https://eprint.iacr.org/2015/1127}},
      url = {https://eprint.iacr.org/2015/1127}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.