Pseudo-free families and cryptographic primitivesстатьяИсследовательская статьяЭлектронная публикация
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 13 июля 2022 г.
Аннотация:In this article, 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 unique bit string of the 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 operation (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.