Paper 2018/1178

Pseudo-Free Families of Computational Universal Algebras

Mikhail Anokhin

Abstract

Let $\Omega$ be a finite set of finitary operation symbols. We initiate the study of (weakly) pseudo-free families of computational $\Omega$-algebras in arbitrary varieties of $\Omega$-algebras. Most of our results concern (weak) pseudo-freeness 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 pseudo-free 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 exponential-size pseudo-free family and a polynomially bounded weakly pseudo-free family (both in $\mathfrak O$); (iii) in all other cases, the existence of polynomially bounded weakly pseudo-free families in $\mathfrak O$ implies the existence of collision-resistant families of hash functions. Second, assuming the existence of collision-resistant families of hash functions, we construct a polynomially bounded weakly pseudo-free family and an exponential-size pseudo-free 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 pseudo-free families in the variety of all $m$-ary groupoids exist if and only if collision-resistant 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)
PDF
Category
Foundations
Publication info
Published elsewhere. Major revision. Journal of Mathematical Cryptology, 15(1):197-222, 2021
DOI
10.1515/jmc-2020-0014
Keywords
universal algebraspseudo-freenessweak pseudo-freenesshash functionscollision resistance$n$-ary groupoids
Contact author(s)
anokhin @ mccme ru
History
2020-12-03: last of 3 revisions
2018-12-03: received
See all versions
Short URL
https://ia.cr/2018/1178
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1178,
      author = {Mikhail Anokhin},
      title = {Pseudo-Free Families of Computational Universal Algebras},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1178},
      year = {2018},
      doi = {10.1515/jmc-2020-0014},
      note = {\url{https://eprint.iacr.org/2018/1178}},
      url = {https://eprint.iacr.org/2018/1178}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.