Oblivious Transfer Based on the McEliece Assumptions with Unconditional Security for the Sender
Resumo
In this paper we propose the first code-based oblivious transfer protocol with perfect (unconditional) security for one of the parties. To obtain this result we show that the McEliece cryptosystem is rerandomizable, a property that might be of independent interest.Referências
Donald Beaver. Precomputing oblivious transfer. In CRYPTO ’95: Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, pages 97–109, London, UK, 1995. Springer-Verlag.
Mihir Bellare and Silvio Micali. Non-interactive oblivious transfer and applications. In CRYPTO ’89: Proceedings on Advances in cryptology, pages 547–557, New York, NY, USA, 1989. Springer-Verlag New York, Inc.
Elwyn R Berlekamp, Robert McEliece, and Henk C A van Tilborg. On the inherent intractability of certain coding problems (corresp. IEEE Transactions on Information Theory, (24), 1978.
Claude Crépeau, Jeroen van de Graaf, and Alain Tapp. Committed oblivious transfer and private multi-party computation. In Don Coppersmith, editor, CRYPTO, volume 963 of Lecture Notes in Computer Science, pages 110–123. Springer, 1995.
Ivan Damgard, Joe Kilian, and Louis Salvail. 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, 1999. Springer-Verlag.
Rafael Dowsley, Jeroen van de Graaf, Jörn Müller-Quade, and Anderson C. A. Nascimento. Oblivious transfer based on the mceliece assumptions. In Reihaneh SafaviNaini, editor, ICITS, volume 5155 of Lecture Notes in Computer Science, pages 107–117. Springer, 2008.
Shimon Even, Oded Goldreich, and Abraham Lempel. A randomized protocol for signing contracts. In CRYPTO, pages 205–210, 1982.
Shimon Even, Oded Goldreich, and Abraham Lempel. A randomized protocol for signing contracts. Commun. ACM, 28(6):637–647, 1985.
Jean-Bernard Fischer and Jacques Stern. An efficient pseudo-random generator provably as secure as syndrome decoding. In EUROCRYPT’96: Proceedings of the 15th annual international conference on Theory and application of cryptographic techniques, pages 245–255, Berlin, Heidelberg, 1996. Springer-Verlag.
O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In STOC ’87: Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 218–229, New York, NY, USA, 1987. ACM.
Yael Tauman Kalai. Smooth projective hashing and two-message oblivious transfer. In In EUROCRYPT 2005, Springer-Verlag (LNCS 3494, pages 78–95. Springer, 2005.
Joe Kilian. 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, 1988. ACM.
K. Kobara, K. Morozov, and R. Overbeck. Oblivious transfer via mceliece’s pkc and permuted kernels. Cryptology ePrint Archive, Report 2007/382, 2007. http://eprint.iacr.org/.
R J McEliece. A public-key cryptosystem based on algebraic coding theory. dsn progress report. In Jet Propulsion Laboratories, CALTECH, pages 42–44, 1978.
R.J. McEliece. The Theory of Information and Coding, volume 3 of The Encyclopedia of Mathematics and Its Applications. Reading, Mass., Addison-Wesley, 1077.
Moni Naor. Bit commitment using pseudo-randomness. In CRYPTO ’89: Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, pages 128–136, London, UK, 1990. Springer-Verlag.
Ryo Nojima, Hideki Imai, Kazukuni Kobara, and Kirill Morozov. Semantic security for the mceliece cryptosystem without random oracles. Des. Codes Cryptography, 49(1-3):289–305, 2008.
Michael O. Rabin. How to exchange secrets by oblivious transfer. Technical Memo TR-81, Aiken Computation Laboratory, Harvard University, 1981.
Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In STOC ’05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 84–93, New York, NY, USA, 2005. ACM.
Mihir Bellare and Silvio Micali. Non-interactive oblivious transfer and applications. In CRYPTO ’89: Proceedings on Advances in cryptology, pages 547–557, New York, NY, USA, 1989. Springer-Verlag New York, Inc.
Elwyn R Berlekamp, Robert McEliece, and Henk C A van Tilborg. On the inherent intractability of certain coding problems (corresp. IEEE Transactions on Information Theory, (24), 1978.
Claude Crépeau, Jeroen van de Graaf, and Alain Tapp. Committed oblivious transfer and private multi-party computation. In Don Coppersmith, editor, CRYPTO, volume 963 of Lecture Notes in Computer Science, pages 110–123. Springer, 1995.
Ivan Damgard, Joe Kilian, and Louis Salvail. 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, 1999. Springer-Verlag.
Rafael Dowsley, Jeroen van de Graaf, Jörn Müller-Quade, and Anderson C. A. Nascimento. Oblivious transfer based on the mceliece assumptions. In Reihaneh SafaviNaini, editor, ICITS, volume 5155 of Lecture Notes in Computer Science, pages 107–117. Springer, 2008.
Shimon Even, Oded Goldreich, and Abraham Lempel. A randomized protocol for signing contracts. In CRYPTO, pages 205–210, 1982.
Shimon Even, Oded Goldreich, and Abraham Lempel. A randomized protocol for signing contracts. Commun. ACM, 28(6):637–647, 1985.
Jean-Bernard Fischer and Jacques Stern. An efficient pseudo-random generator provably as secure as syndrome decoding. In EUROCRYPT’96: Proceedings of the 15th annual international conference on Theory and application of cryptographic techniques, pages 245–255, Berlin, Heidelberg, 1996. Springer-Verlag.
O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In STOC ’87: Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 218–229, New York, NY, USA, 1987. ACM.
Yael Tauman Kalai. Smooth projective hashing and two-message oblivious transfer. In In EUROCRYPT 2005, Springer-Verlag (LNCS 3494, pages 78–95. Springer, 2005.
Joe Kilian. 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, 1988. ACM.
K. Kobara, K. Morozov, and R. Overbeck. Oblivious transfer via mceliece’s pkc and permuted kernels. Cryptology ePrint Archive, Report 2007/382, 2007. http://eprint.iacr.org/.
R J McEliece. A public-key cryptosystem based on algebraic coding theory. dsn progress report. In Jet Propulsion Laboratories, CALTECH, pages 42–44, 1978.
R.J. McEliece. The Theory of Information and Coding, volume 3 of The Encyclopedia of Mathematics and Its Applications. Reading, Mass., Addison-Wesley, 1077.
Moni Naor. Bit commitment using pseudo-randomness. In CRYPTO ’89: Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, pages 128–136, London, UK, 1990. Springer-Verlag.
Ryo Nojima, Hideki Imai, Kazukuni Kobara, and Kirill Morozov. Semantic security for the mceliece cryptosystem without random oracles. Des. Codes Cryptography, 49(1-3):289–305, 2008.
Michael O. Rabin. How to exchange secrets by oblivious transfer. Technical Memo TR-81, Aiken Computation Laboratory, Harvard University, 1981.
Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In STOC ’05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 84–93, New York, NY, USA, 2005. ACM.
Publicado
11/10/2010
Como Citar
DAVID, Bernardo M.; NASCIMENTO, Anderson C. A.; NOGUEIRA, Rodrigo B..
Oblivious Transfer Based on the McEliece Assumptions with Unconditional Security for the Sender. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 10. , 2010, Fortaleza.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2010
.
p. 147-156.
DOI: https://doi.org/10.5753/sbseg.2010.20584.
