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). Our framework is actually 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 N’th-Residuosity Assumption, and the security of the other is based on both the Quadratic Residuosity Assumption and the Extended Riemann Hypothesis. Our security guarantees are not simulation based, and are similar to those of previous constructions.
When using smooth projective hashing in this context, we must deal with maliciously chosen smooth projective hash families. This raises new technical difficulties, and in particular it is here that the Extended Riemann Hypothesis comes into play.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aiello, W., Ishai, Y., Reingold, O.: Priced Oblivious Transfer: How to Sell Digital Goods. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 119–135. Springer, Heidelberg (2001)
Bach, E., Shallit, J.: Algorithmic Number Theory, Vol. 1: Efficient Algorithms. MIT Press, Cambridge (1996)
Bellare, M., Micali, S.: Non-Interactive Oblivious Transfer and Applications. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 547–557. Springer, Heidelberg (1989)
Cramer, R., Shoup, V.: A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 13–25. Springer, Heidelberg (1998)
Cramer, R., Shoup, V.: Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 45–64. Springer, Heidelberg (2002)
Crépeau, C.: Equivalence between two flavours of oblivious transfers. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 350–354. Springer, Heidelberg (1987)
Cachin, C., Crépeau, C., Marcil, J.: Oblivious Transfer with a Memory-Bounded Receiver. In: FOCS 1998, pp. 493–502 (1998)
Ding, Y.Z., Harnik, D., Rosen, A., Shaltiel, R.: Constant-Round Oblivious Transfer in the Bounded Storage Model. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 446–472. Springer, Heidelberg (2004)
Fraleigh, J.B.: A first course in abstract algebra, 7th edn. Addison-Wesley, Reading (1998)
Even, S., Goldreich, O., Lempel, A.: A Randomized Protocol for Signing Contracts. Communications of the ACM 28(6), 637–647 (1985)
Gennaro, R., Lindell, Y.: A Framework for Password-Based Authenticated Key Exchange. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 524–543. Springer, Heidelberg (2003)
Goldreich, O.: Foundations of Cryptography - Volume 2 (Basic Applications). Cambridge University Press, Cambridge (2004)
Goldreich, O., Micali, S., Wigderson, A.: How to Play any Mental Game - A completeness Theorem for Protocols with Honest Majority. In: STOC 1987, pp. 218–229 (1987)
Haitner, I.: Implementing Oblivious Transfer Using Collection of Dense Trapdoor Permutations. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 394–409. Springer, Heidelberg (2004)
Impagliazzo, R., Rudich, S.: Limits on the Provable Consequences of One-Way Permutations. In: STOC 1989, pp. 44–61 (1989)
Katz, J., Ostrovsky, R., Yung, M.: Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 475–494. Springer, Heidelberg (2001)
Kilian, J.: Founding Cryptography on Oblivious Transfer. In: 20th ACM Symposium on the Theory of Computing, pp. 20–31 (1988)
Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: SODA 2001, pp. 448–457 (2001)
Paillier, P.: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)
Rabin, M.O.: How to Exchange Secrets by Oblivious Transfer. TR-81, Harvard (1981)
Yao, A.C.: How to Generate and Exchange Secrets. In: FOCS 1986, pp. 162–167 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kalai, Y.T. (2005). Smooth Projective Hashing and Two-Message Oblivious Transfer. In: Cramer, R. (eds) Advances in Cryptology – EUROCRYPT 2005. EUROCRYPT 2005. Lecture Notes in Computer Science, vol 3494. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11426639_5
Download citation
DOI: https://doi.org/10.1007/11426639_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25910-7
Online ISBN: 978-3-540-32055-5
eBook Packages: Computer ScienceComputer Science (R0)