Pseudo-free families of computational universal algebras

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. A family (H-d vertical bar d is an element of D) of computational Omega-algebras (where D subset of {0, 1} * ) is called polynomially bounded (resp., having exponential size) if there exists a polynomial n such that for all d is an element of D, the length of any representation of every h is an element of H-d is at most eta(vertical bar d vertical bar) (resp., &VERBARH(d)&VERBAR <= 2(eta(vertical bar d vertical bar))). First, we prove the following trichotomy: (i) if Omega consists of nullary operation symbols only, then there exists a polynomially bounded pseudo-free family; (ii) if Omega = Omega(0) boolean OR {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 poly-nomially bounded weakly pseudo-free family; (iii) in all other cases, the existence of polynomially bounded weakly pseudo-free families implies the existence of collision-resistant families of hash functions. In this trichotomy, (weak) pseudo-freeness is meant in the variety of all Omega-algebras. 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.