Cryptology ePrint Archive: Report 2020/1496

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:

[ Cryptology ePrint archive ]