Welcome to the resource topic for 2020/1496
Title:
Pseudo-Free Families and Cryptographic Primitives
Authors: 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 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.
ePrint: https://eprint.iacr.org/2020/1496
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .