Pseudo-free families of computational universal algebras

Journal of mathematical cryptology

article

Mikhail Anokhin¹ 

[1] Information Security Institute, Lomonosov University

关键词: Universal algebra;    pseudo-free family;    weakly pseudo-free family;    collision-resistant family of hash functions;    n-ary groupoid;   

DOI  :  10.1515/jmc-2020-0014

学科分类：社会科学、人文和艺术（综合）

来源: De Gruyter

【 摘 要 】

Let Ω be a finite set of finitary operation symbols. We initiate the study of (weakly) pseudo-free families of computational Ω -algebras in arbitrary varieties of Ω -algebras. A family ( H d | d ∈ D ) of computational Ω -algebras (where D ⊆ {0, 1} * ) is called polynomially bounded (resp., having exponential size) if there exists a polynomial η such that for all d ∈ D , the length of any representation of every h ∈ H d is at most η(|d|)( resp., |Hd|≤2η(|d|)).$\eta (|d|)\left( \text{ resp}\text{., }\left| {{H}_{d}} \right|\le {{2}^{\eta (|d|)}} \right).$ First, we prove the following trichotomy: (i) if Ω consists of nullary operation symbols only, then there exists a polynomially bounded pseudo-free family; (ii) if Ω = Ω 0 ∪ { ω }, where Ω 0 consists of nullary operation symbols and the arity of ω is 1, then there exist an exponential-size pseudo-free family and a polynomially 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 Ω -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.

【 授权许可】

CC BY|CC BY-NC-ND