Paper 2018/1178
PseudoFree Families of Computational Universal Algebras
Mikhail Anokhin
Abstract
Let $\Omega$ be a finite set of finitary operation symbols. We initiate the study of (weakly) pseudofree families of computational $\Omega$algebras in arbitrary varieties of $\Omega$algebras. Most of our results concern (weak) pseudofreeness in the variety $\mathfrak O$ of all $\Omega$algebras. A family $(H_d)_{d\in D}$ of computational $\Omega$algebras (where $D\subseteq\{0,1\}^*$) is called polynomially bounded (resp., having exponential size) if there exists a polynomial $\eta$ such that for all $d\in D$, the length of any representation of every $h\in H_d$ is at most $\eta(\lvert d\rvert)$ (resp., $\lvert H_d\rvert\le2^{\eta(\lvert d\rvert)}$). First, we prove the following trichotomy: (i) if $\Omega$ consists of nullary operation symbols only, then there exists a polynomially bounded pseudofree family in $\mathfrak O$; (ii) if $\Omega=\Omega_0\cup\{\omega\}$, where $\Omega_0$ consists of nullary operation symbols and the arity of $\omega$ is $1$, then there exist an exponentialsize pseudofree family and a polynomially bounded weakly pseudofree family (both in $\mathfrak O$); (iii) in all other cases, the existence of polynomially bounded weakly pseudofree families in $\mathfrak O$ implies the existence of collisionresistant families of hash functions. Second, assuming the existence of collisionresistant families of hash functions, we construct a polynomially bounded weakly pseudofree family and an exponentialsize pseudofree family in the variety of all $m$ary groupoids, where $m$ is an arbitrary positive integer. In particular, for arbitrary $m\ge2$, polynomially bounded weakly pseudofree families in the variety of all $m$ary groupoids exist if and only if collisionresistant families of hash functions exist.
Note: We have added a reference to the journal version of the paper and made some other minor changes.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. MAJOR revision.Journal of Mathematical Cryptology, 15(1):197222, 2021
 DOI
 10.1515/jmc20200014
 Keywords
 universal algebraspseudofreenessweak pseudofreenesshash functionscollision resistance$n$ary groupoids
 Contact author(s)
 anokhin @ mccme ru
 History
 20201203: last of 3 revisions
 20181203: received
 See all versions
 Short URL
 https://ia.cr/2018/1178
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/1178, author = {Mikhail Anokhin}, title = {PseudoFree Families of Computational Universal Algebras}, howpublished = {Cryptology ePrint Archive, Paper 2018/1178}, year = {2018}, doi = {10.1515/jmc20200014}, note = {\url{https://eprint.iacr.org/2018/1178}}, url = {https://eprint.iacr.org/2018/1178} }