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.