Pseudo-free families and cryptographic primitives

Abstract

In this article, we study the connections between pseudo-free families of computational Ω\Omega -algebras (in appropriate varieties of Ω\Omega -algebras for suitable finite sets Ω\Omega of finitary operation symbols) and certain standard cryptographic primitives. We restrict ourselves to families (Hd∣d∈D)\left({H}_{d}\hspace{0.33em}| \hspace{0.33em}d\in D) of computational Ω\Omega -algebras (where D⊆{0,1}∗D\subseteq {\left\{0,1\right\}}^{\ast }) such that for every d∈Dd\in D, each element of Hd{H}_{d} is represented by a unique bit string of the length polynomial in the length of dd. 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≥2m\ge 2, pseudo-free families of computational mm-unary algebras with one to one fundamental operations (in the variety of all mm-unary algebras) exist if and only if claw resistant families of mm-tuples of permutations exist; (iii) for a certain Ω\Omega and a certain variety V{\mathfrak{V}} of Ω\Omega -algebras, the existence of pseudo-free families of computational Ω\Omega -algebras in V{\mathfrak{V}} implies the existence of families of trapdoor permutations.

Keywords

• universal algebra
• pseudo-free family
• unary algebra
• one-way family of permutations
• claw resistant family of tuples of permutations
• family of trapdoor permutations
• 94a60
• 08a70
• 08a60
• 08a62