International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Smooth Projective Hashing and Two-Message Oblivious Transfer

Shai Halevi
Yael Tauman Kalai
Search ePrint
Search Google
Abstract: We present a general framework for constructing two-message oblivious transfer protocols using a modification of Cramer and Shoup's notion of smooth projective hashing (2002). This framework is an abstraction of the two-message oblivious transfer protocols of Naor and Pinkas (2001) and Aiello et al. (2001), whose security is based on the Decisional Diffie Hellman Assumption. In particular, we give two new oblivious transfer protocols. The security of one is based on the Quadratic Residuosity Assumption, and the security of the other is based on the $N$'th Residuosity Assumption. Our security guarantees are not simulation based, but are similar to the guarantees of the aforementioned two constructions. Compared to other applications of smooth projective hashing, in our context we must deal also with maliciously chosen parameters, which raises new technical difficulties. We also improve on prior constructions of factoring-based smooth universal hashing, in that our constructions *do not require that the underlying RSA-composite is a product of safe primes*. In fact, we observe that the safe-prime requirement is unnecessary for many prior constructions. In particular, we observe that the factoring-based CCA secure encryption schemes due to Cramer-Shoup, Gennaro-Lindell and Camenisch-Shoup remain secure even if the underlying RSA-composite is not a product of safe primes. (This holds for the schemes based on the Quadratic Residuosity Assumption as well as the ones based on the $N$'th Residuosity Assumption.)
  title={Smooth Projective Hashing and Two-Message Oblivious Transfer},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / CCA-secure encryption, Oblivious Transfer, Safe primes, Smooth Projective Hashing},
  note={Preliminary version of this work appeared in Eurocrypt 2005 13603 received 30 Mar 2007, last revised 30 Mar 2007},
  author={Shai Halevi and Yael Tauman Kalai},