Obtaining Efficient Fully Simulatable Oblivious Transfer from General Assumptions

  • Bernardo M. David UnB
  • Anderson C. A. Nascimento UnB
  • Rafael Tonicelli UnB


We introduce a general construction of fully simulatable oblivious transfer based on lossy encryption. Furthermore, we extend the common definition of lossy encryption by introducing the notion of computationally lossy encryption. If the cryptosystem used is computationally lossy, our general construction yields oblivious transfer protocols with computational security for both parties. Otherwise, when regular statistically lossy cryptosystems are employed in this construction, it yields oblivious transfer protocols with statistical security for the sender. The construction introduced in this paper is realizable from rerandomizable, homomorphic and lossy cryptosystems in general. Thus, it yields specific constructions based on different assumptions, such as DDH, LWE and McEliece. Moreover, it proves the equivalence of fully simulatable oblivious transfer and lossy encryption.


Barak, B. and Lindell, Y. (2004). Strict polynomial-time in simulation and extraction. SIAM J. Comput., 33(4):738–818.

Bellare, M., Hofheinz, D., and Yilek, S. (2009). Possibility and impossibility results for encryption and commitment secure under selective opening. In Proceedings of the 28th Annual International Conference on Advances in Cryptology: the Theory and Applications of Cryptographic Techniques, EUROCRYPT ’09, pages 1–35, Berlin, Heidelberg. Springer-Verlag.

Camenisch, J., Neven, G., and Shelat, A. (2007). Simulatable adaptive oblivious transfer. In Naor, M., editor, EUROCRYPT, volume 4515 of Lecture Notes in Computer Science, pages 573–590. Springer.

Damgard, I., Kilian, J., and Salvail, L. (1999). On the (im)possibility of basing oblivious transfer and bit commitment on weakened security assumptions. In EUROCRYPT’99: Proceedings of the 17th international conference on Theory and application of cryptographic techniques, pages 56–73, Berlin, Heidelberg. Springer-Verlag.

David, B. M., Nascimento, A. C. A., and Nogueira, R. B. (2010). Oblivious transfer based on the mceliece assumptions with unconditional security for the sender. In X Simposio Brasileiro de Segurança da Informação e de Sistemas Computacionais.

Dowsley, R., van de Graaf, J., Müller-Quade, J., and Nascimento, A. C. A. (2008). Oblivious transfer based on the mceliece assumptions. In Safavi-Naini, R., editor, ICITS, volume 5155 of Lecture Notes in Computer Science, pages 107–117. Springer.

Goldreich, O. and Kahan, A. (1996). How to construct constant-round zero-knowledge proof systems for np. Journal of Cryptology, 9:167–189. 10.1007/BF00208001.

Green, M. and Hohenberger, S. (2007). Blind identity-based encryption and simulatable oblivious transfer. In Kurosawa, K., editor, ASIACRYPT, volume 4833 of Lecture Notes in Computer Science, pages 265–282. Springer.

Hemenway, B., Libert, B., Ostrovsky, R., and Vergnaud, D. (2009). Lossy encryption: Constructions from general assumptions and efficient selective opening chosen ciphertext security. Cryptology ePrint Archive, Report 2009/088. http://eprint.iacr.org/.

Kilian, J. (1988). Founding crytpography on oblivious transfer. In STOC ’88: Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 20–31, New York, NY, USA. ACM.

Lindell, A. Y. (2008). Efficient fully-simulatable oblivious transfer. In Proceedings of the 2008 The Cryptopgraphers’ Track at the RSA conference on Topics in cryptology, CT-RSA’08, pages 52–70, Berlin, Heidelberg. Springer-Verlag.

Peikert, C., Vaikuntanathan, V., and Waters, B. (2008). A framework for efficient and composable oblivious transfer. In Wagner, D., editor, Advances in Cryptology – CRYPTO 2008, volume 5157 of Lecture Notes in Computer Science, pages 554–571. Springer Berlin / Heidelberg.

Rabin, M. O. (1981). How to exchange secrets by oblivious transfer. Technical Memo TR-81, Aiken Computation Laboratory, Harvard University.
DAVID, Bernardo M.; NASCIMENTO, Anderson C. A.; TONICELLI, Rafael. Obtaining Efficient Fully Simulatable Oblivious Transfer from General Assumptions. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 11. , 2011, Brasília. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2011 . p. 108-121. DOI: https://doi.org/10.5753/sbseg.2011.20567.