|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Pseudo-Free Families and Cryptographic Primitivesстатья Электронная публикация
- Автор: Anokhin M.
- Журнал: Cryptology ePrint Archive
- Год издания: 2020
- Номер статьи: 1496
- Аннотация: In this paper, we study the connections between pseudo-free families of computational Ω-algebras (in appropriate varieties of Ω-algebras for suitable finite sets Ω of finitary operation symbols) and certain standard cryptographic primitives. We restrict ourselves to families (H_d)_{d∈D} of computational Ω-algebras (where D⊆{0,1}^∗) such that for every d∈D, each element of H_d is represented by a single bit string of length polynomial in the length of d. Very loosely speaking, our main results are as follows: (i) pseudo-free families of computational mono-unary algebras with one-to-one fundamental operations (in the variety of all mono-unary algebras) exist if and only if one-way families of permutations exist; (ii) for any m≥2, pseudo-free families of computational m-unary algebras with one-to-one fundamental operations (in the variety of all m-unary algebras) exist if and only if claw-resistant families of m-tuples of permutations exist; (iii) for a certain Ω and a certain variety V of Ω-algebras, the existence of pseudo-free families of computational Ω-algebras in V implies the existence of families of trapdoor permutations.
- Добавил в систему: Анохин Михаил Игоревич