×

zbMATH — the first resource for mathematics

Oblivious transfer from any non-trivial elastic noisy channel via secret key agreement. (English) Zbl 1369.94522
Hirt, Martin (ed.) et al., Theory of cryptography. 14th international conference, TCC 2016-B, Beijing, China, October 31 – November 3, 2016. Proceedings. Part I. Berlin: Springer (ISBN 978-3-662-53640-7/pbk; 978-3-662-53641-4/ebook). Lecture Notes in Computer Science 9985, 204-234 (2016).
Summary: A \((\gamma,\delta)\)-elastic channel is a binary symmetric channel between a sender and a receiver where the error rate of an honest receiver is \(\delta\) while the error rate of a dishonest receiver lies within the interval \([\gamma, \delta]\). In this paper, we show that from any non-trivial elastic channel (i.e., \(0<\gamma<\delta <\frac{1}{2}\)) we can implement oblivious transfer with information-theoretic security. This was previously [D. Khurana et al., Eurocrypt 2016, Lect. Notes Comput. Sci. 9666, 184–212 (2016; Zbl 1369.94544)] only known for a subset of these parameters. Our technique relies on a new way to exploit protocols for information-theoretic key agreement from noisy channels. We also show that information-theoretically secure commitments where the receiver commits follow from any non-trivial elastic channel.
For the entire collection see [Zbl 1347.94003].
MSC:
94A60 Cryptography
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Brassard, G., Chaum, D., Crépeau, C.: Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci. 37(2), 156–189 (1988) · Zbl 0656.68109 · doi:10.1016/0022-0000(88)90005-0
[2] Brassard, G., Crépeau, C., Santha, M.: Oblivious transfers and intersecting codes. IEEE Trans. Inf. Theory 42(6), 1769–1780 (1996) · Zbl 0873.94015 · doi:10.1109/18.556673
[3] Brassard, G., Salvail, L.: Secret-key reconciliation by public discussion. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 410–423. Springer, Heidelberg (1994). doi: 10.1007/3-540-48285-7_35 · Zbl 0951.94536 · doi:10.1007/3-540-48285-7_35
[4] Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: Proceedings of 42nd IEEE Symposium on Foundations of Computer Science, pp. 136–145. IEEE (2001) · doi:10.1109/SFCS.2001.959888
[5] Crépeau, C., Kilian, J.: Achieving oblivious transfer using weakened security assumptions (Extended Abstract). In: 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24–26 October 1988, pp. 42–52 (1988)
[6] Crépeau, C., Morozov, K., Wolf, S.: Efficient unconditional oblivious transfer from almost any noisy channel. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 47–59. Springer, Heidelberg (2005). doi: 10.1007/978-3-540-30598-9_4 · Zbl 1116.94319 · doi:10.1007/978-3-540-30598-9_4
[7] Crépeau, C.: Efficient cryptographic protocols based on noisy channels. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 306–317. Springer, Heidelberg (1997). doi: 10.1007/3-540-69053-0_21 · doi:10.1007/3-540-69053-0_21
[8] Crépeau, C., Savvides, G.: Optimal reductions between oblivious transfers using interactive hashing. In: Proceedings of Advances in Cryptology - EUROCRYpPT, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28–June 1, pp. 201–221 (2006) · Zbl 1140.94332 · doi:10.1007/11761679_13
[9] Crépeau, C., Graaf, J., Tapp, A.: Committed oblivious transfer and private multi-party computation. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 110–123. Springer, Heidelberg (1995). doi: 10.1007/3-540-44750-4_9 · Zbl 0876.94026 · doi:10.1007/3-540-44750-4_9
[10] Damgård, I., Fehr, S., Morozov, K., Salvail, L.: Unfair noisy channels and oblivious transfer. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 355–373. Springer, Heidelberg (2004). doi: 10.1007/978-3-540-24638-1_20 · Zbl 1197.94183 · doi:10.1007/978-3-540-24638-1_20
[11] 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). doi: 10.1007/3-540-48910-X_5 · Zbl 0932.68045 · doi:10.1007/3-540-48910-X_5
[12] Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.D.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97–139 (2008) · Zbl 1165.94326 · doi:10.1137/060651380
[13] Estren, G.: Universally composable committed oblivious transfer and multi-party computation assuming only basic black-box primitives. Ph.D. thesis, McGill University (2004)
[14] Goldreich, O., Micali, S., Wigderson, A.: How to prove all NP statements in zero-knowledge and a methodology of cryptographic protocol design (Extended Abstract). In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 171–185. Springer, Heidelberg (1987). doi: 10.1007/3-540-47721-7_11 · Zbl 0636.94010 · doi:10.1007/3-540-47721-7_11
[15] Harnik, D., Kilian, J., Naor, M., Reingold, O., Rosen, A.: On robust combiners for oblivious transfer and other primitives. In: Proceedings of Advances in Cryptology - EUROCRYpPT, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, pp. 96–113, 22–26 May 2005 · Zbl 1137.94346 · doi:10.1007/11426639_6
[16] Ishai, Y., Kushilevitz, E., Ostrovsky, R., Prabhakaran, M., Sahai, A., Wullschleger, J.: Constant-rate oblivious transfer from noisy channels. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 667–684. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-22792-9_38 · Zbl 1290.94092 · doi:10.1007/978-3-642-22792-9_38
[17] Kilian, J.: Founding cryptography on oblivious transfer. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 20–31. ACM (1988)
[18] Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pp. 723–732. ACM (1992)
[19] Khurana, D., Maji, H.K., Sahai, A.: Secure computation from elastic noisy channels. In: Proceedings of Advances in Cryptology - EUROCRYpPT - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, Part II, pp. 184–212, 8–12 May 2016 · Zbl 1369.94544 · doi:10.1007/978-3-662-49896-5_7
[20] Maurer, U.M.: Secret key agreement by public discussion from common information. IEEE Trans. Inf. Theory 39(3), 733–742 (1993) · Zbl 0784.94018 · doi:10.1109/18.256484
[21] Pinto, A.C.B., Dowsley, R., Morozov, K., Nascimento, A.C.A.: Achieving oblivious transfer capacity of generalized erasure channels in the malicious model. IEEE Trans. Inf. Theory 57(8), 5566–5571 (2011) · Zbl 1365.94129 · doi:10.1109/TIT.2011.2158898
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.