CryptoDB
Many-to-one Trapdoor Functions and their Relation to Public-key Cryptosystems
| Authors: | |
|---|---|
| Download: | |
| Abstract: | The heart of the task of building public key cryptosystems is viewed as that of ``making trapdoors;'' in fact, public key cryptosystems and trapdoor functions are often discussed as synonymous. How accurate is this view? In this paper we endeavor to get a better understanding of the nature of ``trapdoorness'' and its relation to public key cryptosystems, by broadening the scope of the investigation: we look at general trapdoor functions; that is, functions that are not necessarily injective (ie., one-to-one). Our first result is somewhat surprising: we show that non-injective trapdoor functions (with super-polynomial pre-image size) can be constructed {from} any one-way function (and hence it is unlikely that they suffice for public key encryption). On the other hand, we show that trapdoor functions with polynomial pre-image size are sufficient for public key encryption. Together, these two results indicate that the pre-image size is a fundamental parameter of trapdoor functions. We then turn our attention to the converse, asking what kinds of trapdoor functions can be constructed from public key cryptosystems. We take a first step by showing that in the random-oracle model one can construct injective trapdoor functions from any public key cryptosystem. |
BibTeX
@misc{eprint-1998-11315,
title={Many-to-one Trapdoor Functions and their Relation to Public-key Cryptosystems},
booktitle={IACR Eprint archive},
keywords={One-way functions, trapdoor functions, public key cryptosystems, trapdoor predicates, encryption.},
url={http://eprint.iacr.org/1998/019},
note={Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. mihir@cs.ucsd.edu. 10500 received June 14th, 1998.},
author={Mihir Bellare and Shai Halevi and Amit Sahai and Salil P. Vadhan},
year=1998
}