Paper 2020/1496
Pseudo-Free Families and Cryptographic Primitives
, Lomonosov University, Moscow, RussiaAbstract
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 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\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.
Note: We have added a reference to the journal version of the paper and made some other minor changes.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Journal of Mathematical Cryptology, 16(1):114-140, 2022
- Keywords
- universal algebras pseudo-freeness one-way functions collision resistance families of trapdoor permutations
- Contact author(s)
- anokhin @ mccme ru
- History
- 2022-07-22: revised
- 2020-11-29: received
- See all versions
- Short URL
- https://ia.cr/2020/1496
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1496,
author = {Mikhail Anokhin},
title = {Pseudo-Free Families and Cryptographic Primitives},
howpublished = {Cryptology ePrint Archive, Paper 2020/1496},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1496}},
url = {https://eprint.iacr.org/2020/1496}
}
