Welcome to the resource topic for 2018/1178
Title:
Pseudo-Free Families of Computational Universal Algebras
Authors: 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.
ePrint: https://eprint.iacr.org/2018/1178
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .