|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Pseudo-Free Families of Computational Universal Algebrasстатья Электронная публикация
- Автор: Anokhin M.
- Журнал: Cryptology ePrint Archive
- Номер: 1178
- Год издания: 2018
- Аннотация: Let Ω be a finite set of operation symbols. We initiate the study of (weakly) pseudo-free families of computational Ω-algebras in arbitrary varieties of Ω-algebras. Most of our results concern (weak) pseudo-freeness in the variety O of all Ω-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., ∣H_d∣≤2^{η(∣d∣)}). First, we prove the following trichotomy: (i) if Ω consists of nullary operation symbols only, then there exists a polynomially bounded pseudo-free family in O; (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 (both in O); (iii) in all other cases, the existence of polynomially bounded weakly pseudo-free families in 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 of computational m-ary groupoids (both in O), where m is an arbitrary positive integer. In particular, for arbitrary m≥2, polynomially bounded weakly pseudo-free families of computational m-ary groupoids in O exist if and only if collision-resistant families of hash functions exist. Moreover, we present some simple constructions of cryptographic primitives from pseudo-free families satisfying certain additional conditions. These constructions demonstrate the potential of pseudo-free families.
- Добавил в систему: Анохин Михаил Игоревич