Pseudo-free families and cryptographic primitives

Journal of Mathematical Cryptology

Anokhin Mikhail¹ 

[1] Information Security Center, Faculty of Computational Mathematics and Cybernetics, Lomonosov University, Michurinsky prosp. 1, 119192 Moscow, Russia;

关键词: 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;   

DOI  :  10.1515/jmc-2020-0055

来源: DOAJ

【 摘 要 】

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 Ω\Omegaof 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 Ω\Omegaand 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.

【 授权许可】

Unknown