Paper 2020/1496

Pseudo-Free Families and Cryptographic Primitives

Abstract

In this paper, we study the connections between pseudo-free families of computational $\mathrm{\Omega }$-algebras (in appropriate varieties of $\mathrm{\Omega }$-algebras for suitable finite sets $\mathrm{\Omega }$ of finitary operation symbols) and certain standard cryptographic primitives. We restrict ourselves to families $(H_d|d\in D)$ of computational $\mathrm{\Omega }$-algebras (where $D\subseteq \{0,1{\}}^{\ast }$) such that for every $d\in D$, each element of $H_d$ is represented by a unique 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 operation (in the variety of all mono-unary algebras) exist if and only if one-way families of permutations exist; (ii) for any $m\ge 2$, pseudo-free families of computational $m$-unary algebras with one-to-one fundamental operations (in the variety of all $$-unary algebras) exist if and only if claw-resistant families of $$-tuples of permutations exist; (iii) for a certain $$ and a certain variety $$ of $$-algebras, the existence of pseudo-free families of computational $$-algebras in $$ implies the existence of families of trapdoor permutations.

Note: We have added a reference to the journal version of the paper and made some other minor changes.