**Pseudo-Free Families and Cryptographic Primitives**

*Mikhail Anokhin*

**Abstract: **In this paper, 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 $(H_d)_{d\in D}$ of computational $\Omega$-algebras (where $D\subseteq\{0,1\}^*$) such that for every $d\in 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\ge2$, 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 $\Omega$ and a certain variety $\mathfrak V$ of $\Omega$-algebras, the existence of pseudo-free families of computational $\Omega$-algebras in $\mathfrak V$ implies the existence of families of trapdoor permutations.

**Category / Keywords: **foundations / universal algebras, families of computational universal algebras, pseudo-freeness, unary algebras, mono-unary algebras, one-way functions, one-way families of permutations, claw-resistant families of tuples of permutations, families of trapdoor permutations

**Date: **received 29 Nov 2020

**Contact author: **anokhin at mccme ru

**Available format(s): **PDF | BibTeX Citation

**Version: **20201129:192153 (All versions of this report)

**Short URL: **ia.cr/2020/1496

[ Cryptology ePrint archive ]