Pseudo-free families of computational universal algebras
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 (Hd | d ∈ D) of computational Ω-algebras (where D ⊆ {0, 1}*) is called polynomially bounded (resp., having exponentia...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2020-11-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc-2020-0014 |
| _version_ | 1811212814742716416 |
|---|---|
| author | Anokhin Mikhail |
| author_facet | Anokhin Mikhail |
| author_sort | Anokhin Mikhail |
| collection | DOAJ |
| description | 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 (Hd | 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 ∈ Hd 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. |
| first_indexed | 2024-04-12T05:35:33Z |
| format | Article |
| id | doaj.art-6015cfce4ff444d8b06215708cd83294 |
| institution | Directory Open Access Journal |
| issn | 1862-2984 |
| language | English |
| last_indexed | 2024-04-12T05:35:33Z |
| publishDate | 2020-11-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj.art-6015cfce4ff444d8b06215708cd832942022-12-22T03:45:51ZengDe GruyterJournal of Mathematical Cryptology1862-29842020-11-0115119722210.1515/jmc-2020-0014jmc-2020-0014Pseudo-free families of computational universal algebrasAnokhin Mikhail0Information Security Institute, Lomonosov University, Michurinsky prosp. 1, 119192Moscow, RussiaLet Ω 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 (Hd | 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 ∈ Hd 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.https://doi.org/10.1515/jmc-2020-0014universal algebrapseudo-free familyweakly pseudo-free familycollision-resistant family of hash functionsn-ary groupoid94a6008a7008a6268q17 |
| spellingShingle | Anokhin Mikhail Pseudo-free families of computational universal algebras Journal of Mathematical Cryptology universal algebra pseudo-free family weakly pseudo-free family collision-resistant family of hash functions n-ary groupoid 94a60 08a70 08a62 68q17 |
| title | Pseudo-free families of computational universal algebras |
| title_full | Pseudo-free families of computational universal algebras |
| title_fullStr | Pseudo-free families of computational universal algebras |
| title_full_unstemmed | Pseudo-free families of computational universal algebras |
| title_short | Pseudo-free families of computational universal algebras |
| title_sort | pseudo free families of computational universal algebras |
| topic | universal algebra pseudo-free family weakly pseudo-free family collision-resistant family of hash functions n-ary groupoid 94a60 08a70 08a62 68q17 |
| url | https://doi.org/10.1515/jmc-2020-0014 |
| work_keys_str_mv | AT anokhinmikhail pseudofreefamiliesofcomputationaluniversalalgebras |