Oblivious transfer based on the McEliece assumptions. (English) Zbl 1162.94353
Safavi-Naini, Reihaneh (ed.), Information theoretic security. Third international conference, ICITS 2008, Calgary, Canada, August 10–13, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85092-2/pbk). Lecture Notes in Computer Science 5155, 107-117 (2008).
Summary: 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.
For the entire collection see [Zbl 1152.94003].
For the entire collection see [Zbl 1152.94003].
References:
| [1] | Aiello, W.; Ishai, Y.; Reingold, O.; Pfitzmann, B., Priced Oblivious Transfer: How to Sell Digital Goods, Advances in Cryptology - EUROCRYPT 2001, 119-135 (2001), Heidelberg: Springer, Heidelberg · Zbl 0981.94042 · doi:10.1007/3-540-44987-6_8 |
| [2] | Beaver, D.; Coppersmith, D., Precomputing Oblivious Transfer, Advances in Cryptology - CRYPTO ’95, 97-109 (1995), Heidelberg: Springer, Heidelberg · Zbl 0876.94021 |
| [3] | Bellare, M.; Micali, S.; Brassard, G., Non-Interactive Oblivious Transfer and Applications, Advances in Cryptology - CRYPTO ’89, 547-557 (1990), Heidelberg: Springer, Heidelberg · Zbl 0722.68041 |
| [4] | 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) · Zbl 0377.94018 · doi:10.1109/TIT.1978.1055873 |
| [5] | Blum, A.; Furst, M.; Kearns, M.; Lipton, R. J.; Stinson, D. R., Cryptographic primitives based on hard learning problems, Advances in Cryptology - CRYPTO ’93, 278-291 (1994), Heidelberg: Springer, Heidelberg · Zbl 0870.94021 |
| [6] | 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) · Zbl 1053.94558 · doi:10.1109/18.651067 |
| [7] | Courtois, N.; Finiasz, M.; Sendrier, N.; Boyd, C., How to Achieve a McEliece Digital Signature Scheme, Advances in Cryptology - ASIACRYPT 2001, 157-174 (2001), Heidelberg: Springer, Heidelberg · Zbl 1062.94556 · doi:10.1007/3-540-45682-1_10 |
| [8] | Crépeau, C.; Pomerance, C., Equivalence between two flavors of oblivious transfers, Advances in Cryptology - CRYPTO ’87, 350-354 (1988), Heidelberg: Springer, Heidelberg |
| [9] | Crépeau, C.; van de Graaf, J.; Tapp, A.; Coppersmith, D., Committed Oblivious Transfer and Private Multi-Party Computations, Advances in Cryptology - CRYPTO ’95, 110 (1995), Heidelberg: Springer, Heidelberg · Zbl 0876.94026 |
| [10] | Damgård, I.; Kilian, J.; Salvail, L.; Stern, J., On the (Im)possibility of Basing Oblivious Transfer and Bit Commitment on Weakened Security Assumptions, Advances in Cryptology - EUROCRYPT ’99, 56-73 (1999), Heidelberg: Springer, Heidelberg · Zbl 0932.68045 |
| [11] | Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. In: Proceedings CRYPTO 1982, pp. 205-210. Plenum Press (1983) · Zbl 0538.94011 |
| [12] | Fischer, J.; Stern, J.; Maurer, U. M., An Efficient Pseudo-Random Generator Provably as Secure as Syndrome Decoding, Advances in Cryptology - EUROCRYPT ’96, 245-255 (1996), Heidelberg: Springer, Heidelberg · Zbl 1304.94056 |
| [13] | 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) |
| [14] | Goldreich, O., Foundations of Cryptography (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1068.94011 |
| [15] | 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) |
| [16] | Goldreich, O.; Micali, S.; Wigderson, A., How to Play Any Mental Game, or: A completeness theorem for protocols with honest majority, Proc. 19th ACM STOC, 218-229 (1987), New York: ACM Press, New York |
| [17] | Haitner, I.; Naor, M., implementing Oblivious Transfer Using Collection of Dense Trapdoor Permutations, Theory of Cryptography, 394-409 (2004), Heidelberg: Springer, Heidelberg · Zbl 1197.94189 |
| [18] | Kalai, Y.; Cramer, R. J.F., Smooth Projective Hashing and Two-Message Oblivious Transfer, Advances in Cryptology - EUROCRYPT 2005, 78-95 (2005), Heidelberg: Springer, Heidelberg · Zbl 1137.94348 |
| [19] | Kobara, K., Morozov, K., Overbeck, R.: Oblivious Transfer via McEliece’s PKC and Permuted Kernels, Cryptology ePrint Archive 2007/382 (2007) |
| [20] | Kilian, J., Founding Cryptography on Oblivious Transfer, 20th ACM STOC, 20-31 (1988), New York: ACM Press, New York |
| [21] | Kobara, K.; Imai, H.; Kim, K.-c., Semantically Secure McEliece Cryptosystems - Conversions for McEliece PKC, Public Key Cryptography, 19-35 (2001), Heidelberg: Springer, Heidelberg · Zbl 0988.94021 · doi:10.1007/3-540-44586-2_2 |
| [22] | McEliece, R. J., The Theory of Information and Coding (1977), Reading: Addison-Wesley, Reading · Zbl 0376.94011 |
| [23] | McEliece, R.J.: A Public-Key Cryptosystem Based on Algebraic Coding Theory. In: Deep Space Network progress Report (1978) |
| [24] | Naor, M.; Brassard, G., Bit Commitment using Pseudo-Randomness, Advances in Cryptology - CRYPTO ’89, 128-136 (1990), Heidelberg: Springer, Heidelberg · Zbl 0719.68007 |
| [25] | Naor, M., Pinkas, B.: Efficient Oblivious Transfer Protocols. In: SODA 2001 (SIAM Symposium on Discrete Algorithms) (2001) · Zbl 0991.94045 |
| [26] | Nojima, R., Imai, H., Kobara, K., Morozov, K.: Semantic Security for the McEliece Cryptosystem without Random Oracles. WCC 2007, Versailles, France (April 2007) · Zbl 1196.94062 |
| [27] | Rabin, M.O.: How to Exchange Secrets by Oblivious Transfer. Technical Memo TR-81, Aiken Computation Laboratory, Harvard University (1981) |
| [28] | Regev, O.: On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. In: Proc. 37th STOC, pp. 84-93 (2005) · Zbl 1192.94106 |
| [29] | Sendrier, N., Finding the Permutation Between Equivalent Linear Codes: The Support Splitting Algorithm, IEEE Trans. Inf. Theory, 46, 4, 1193-1203 (2000) · Zbl 1002.94037 · doi:10.1109/18.850662 |
| [30] | Shamir, A.; Brassard, G., An efficient identification scheme based on permuted kernels, Advances in Cryptology - CRYPTO ’89, 606-609 (1990), Heidelberg: Springer, Heidelberg |
| [31] | Wiesner, S., Conjugate coding, Sigact News, 15, 1, 78-88 (1983) · Zbl 0521.94003 · doi:10.1145/1008908.1008920 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
