Abstract
We implement one-out-of-two bit oblivious transfer (OT) based on the assumptions used in the McEliece cryptosystem: the hardness of decoding random binary linear codes, and the difficulty of distinguishing a permuted generating matrix of Goppa codes from a random matrix. To our knowledge this is the first OT reduction to these problems only.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
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)
Beaver, D.: Precomputing Oblivious Transfer. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 97–109. Springer, Heidelberg (1995)
Bellare, M., Micali, S.: Non-Interactive Oblivious Transfer and Applications. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 547–557. Springer, Heidelberg (1990)
Berlekamp, E.R., McEliece, R.J., Avan Tilborg, H.C.: On the Inherent Intractability of Certain Coding Problems. IEEE Trans. Inf. Theory 24, 384–386 (1978)
Blum, A., Furst, M., Kearns, M., Lipton, R.J.: Cryptographic primitives based on hard learning problems. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 278–291. Springer, Heidelberg (1994)
Canteaut, A., Chabaud, F.: A new algorithm for finding minimum-weight words in a linear code: application to primitive narrow-sense BCH codes of length 511. IEEE Trans. Inf. Theory 44(1), 367–378 (1998)
Courtois, N., Finiasz, M., Sendrier, N.: How to Achieve a McEliece Digital Signature Scheme. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 157–174. Springer, Heidelberg (2001)
Crépeau, C.: Equivalence between two flavors of oblivious transfers. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 350–354. Springer, Heidelberg (1988)
Crépeau, C., van de Graaf, J., Tapp, A.: Committed Oblivious Transfer and Private Multi-Party Computations. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, p. 110. Springer, Heidelberg (1995)
Damgård, I., Kilian, J., Salvail, L.: On the (Im)possibility of Basing Oblivious Transfer and Bit Commitment on Weakened Security Assumptions. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 56–73. Springer, Heidelberg (1999)
Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. In: Proceedings CRYPTO 1982, pp. 205–210. Plenum Press (1983)
Fischer, J., Stern, J.: An Efficient Pseudo-Random Generator Provably as Secure as Syndrome Decoding. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 245–255. Springer, Heidelberg (1996)
Gertner, Y., Kannan, S., Malkin, T., Reingold, O., Viswanathan, M.: The Relationship between Public Key Encryption and Oblivious Transfer. In: FOCS 2000, pp. 325–335 (2000)
Goldreich, O.: Foundations of Cryptography (Basic Applications), vol. 2. Cambridge University Press, Cambridge (2004)
Goldreich, O., Levin, L.A.: Hard-Core Predicates for Any One-Way Function. In: 21st ACM Symposium on the Theory of Computing, pp. 25–32 (1989)
Goldreich, O., Micali, S., Wigderson, A.: How to Play Any Mental Game, or: A completeness theorem for protocols with honest majority. In: Proc. 19th ACM STOC, pp. 218–229. ACM Press, New York (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)
Kalai, Y.: Smooth Projective Hashing and Two-Message Oblivious Transfer. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 78–95. Springer, Heidelberg (2005)
Kobara, K., Morozov, K., Overbeck, R.: Oblivious Transfer via McEliece’s PKC and Permuted Kernels, Cryptology ePrint Archive 2007/382 (2007)
Kilian, J.: Founding Cryptography on Oblivious Transfer. In: 20th ACM STOC, pp. 20–31. ACM Press, New York (1988)
Kobara, K., Imai, H.: Semantically Secure McEliece Cryptosystems – Conversions for McEliece PKC. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 19–35. Springer, Heidelberg (2001)
McEliece, R.J.: The Theory of Information and Coding. The Encyclopedia of Mathematics and Its Applications, vol. 3. Addison-Wesley, Reading (1977)
McEliece, R.J.: A Public-Key Cryptosystem Based on Algebraic Coding Theory. In: Deep Space Network progress Report (1978)
Naor, M.: Bit Commitment using Pseudo-Randomness. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 128–136. Springer, Heidelberg (1990)
Naor, M., Pinkas, B.: Efficient Oblivious Transfer Protocols. In: SODA 2001 (SIAM Symposium on Discrete Algorithms) (2001)
Nojima, R., Imai, H., Kobara, K., Morozov, K.: Semantic Security for the McEliece Cryptosystem without Random Oracles. WCC 2007, Versailles, France (April 2007)
Rabin, M.O.: How to Exchange Secrets by Oblivious Transfer. Technical Memo TR-81, Aiken Computation Laboratory, Harvard University (1981)
Regev, O.: On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. In: Proc. 37th STOC, pp. 84–93 (2005)
Sendrier, N.: Finding the Permutation Between Equivalent Linear Codes: The Support Splitting Algorithm. IEEE Trans. Inf. Theory 46(4), 1193–1203 (2000)
Shamir, A.: An efficient identification scheme based on permuted kernels. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 606–609. Springer, Heidelberg (1990)
Wiesner, S.: Conjugate coding. Sigact News 15(1), 78–88 (1983) (original manuscript written circa 1970)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dowsley, R., van de Graaf, J., Müller-Quade, J., Nascimento, A.C.A. (2008). Oblivious Transfer Based on the McEliece Assumptions. In: Safavi-Naini, R. (eds) Information Theoretic Security. ICITS 2008. Lecture Notes in Computer Science, vol 5155. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85093-9_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-85093-9_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85092-2
Online ISBN: 978-3-540-85093-9
eBook Packages: Computer ScienceComputer Science (R0)