×

Efficient \(k\)-out-of-\(n\) oblivious transfer scheme with the ideal communication cost. (English) Zbl 1425.94067

Summary: In this paper, we propose a two-round \(k\)-out-of-\(n\) oblivious transfer scheme with the minimum communication cost. In our proposed scheme, the messages sent by the receiver \(R\) to the sender \(S\) consist of only three elements, which is independent of \(n\) and \(k\), while the messages from \(S\) to \(R\) are \((n + 1)\) elements when the sender holds \(n\) secrets. Our scheme features a nice property of universal parameter, where the system parameter can be used by all senders and receivers. The proposed \(k\)-out-of-\(n\) oblivious transfer scheme is the most efficient two-round scheme in terms of the number of messages transferred between two communicating parties in known constructions. The scheme preserves the privacy of receiver’s choice and sender’s security.

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Asharov, G.; Lindell, Y.; Schneider, T.; Zohner, M., More efficient oblivious transfer and extensions for faster secure computation, (Sadeghi, A.; Gligor, V. D.; Yung, M., 2013 ACM SIGSAC Conference on Computer and Communications Security. 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS’13 (2013), ACM), 535-548
[2] Asharov, G.; Lindell, Y.; Schneider, T.; Zohner, M., More efficient oblivious transfer extensions with security for malicious adversaries, (Oswald, E.; Fischlin, M., EUROCRYPT 2015. EUROCRYPT 2015, LNCS, vol. 9056 (2015), Springer), 673-701 · Zbl 1370.94481
[3] Boneh, D.; Boyen, X.; Goh, E., Hierarchical identity based encryption with constant size ciphertext, (Cramer, R., EUROCRYPT 2005. EUROCRYPT 2005, LNCS, vol. 3494 (2005), Springer), 440-456 · Zbl 1137.94340
[4] Brassard, G.; Crépeau, C.; Robert, J., All-or-nothing disclosure of secrets, (Odlyzko, A. M., CRYPTO 1986. CRYPTO 1986, LNCS, vol. 263 (1987), Springer), 234-238
[5] Camenisch, J.; Neven, G.; Shelat, A., Simulatable adaptive oblivious transfer, (Naor, M., EUROCRYPT 2007. EUROCRYPT 2007, LNCS, vol. 4515 (2007), Springer), 573-590 · Zbl 1141.94344
[6] Chor, B.; Kushilevitz, E.; Goldreich, O.; Sudan, M., Private information retrieval, J. ACM, 45, 6, 965-981 (1998) · Zbl 1065.68524
[7] Chu, C.; Tzeng, W., Efficient k-out-of-n oblivious transfer schemes, J. UCS, 14, 3, 397-415 (2008) · Zbl 1217.68083
[8] Chu, C.-K.; Tzeng, W.-G., Efficient k-out-of-n oblivious transfer schemes with adaptive and non-adaptive queries, (Vaudenay, S., PKC 2005. PKC 2005, LNCS, vol. 3386 (2005), Springer), 172-183 · Zbl 1081.94020
[9] Delerablée, C., Identity-based broadcast encryption with constant size ciphertexts and private keys, (Kurosawa, K., ASIACRYPT 2007. ASIACRYPT 2007, LNCS, vol. 4833 (2007), Springer), 200-215 · Zbl 1153.94366
[10] Delerablée, C.; Paillier, P.; Pointcheval, D., Fully collusion secure dynamic broadcast encryption with constant-size ciphertexts or decryption keys, (Takagi, T.; Okamoto, T.; Okamoto, E.; Okamoto, T., Pairing 2007. Pairing 2007, LNCS, vol. 4575 (2007), Springer), 39-59 · Zbl 1151.94502
[11] Even, S.; Goldreich, O.; Lempel, A., A randomized protocol for signing contracts, Commun. ACM, 28, 6, 637-647 (1985)
[12] Goldreich, O.; Vainish, R., How to solve any protocol problem - an efficiency improvement, (Pomerance, C., CRYPTO 1987. CRYPTO 1987, LNCS, vol. 293 (1988), Springer), 73-86 · Zbl 0644.68077
[13] Green, M.; Hohenberger, S., Blind identity-based encryption and simulatable oblivious transfer, (Kurosawa, K., ASIACRYPT 2007. ASIACRYPT 2007, LNCS, vol. 4833 (2007), Springer), 265-282 · Zbl 1153.94385
[14] Guo, F.; Mu, Y.; Susilo, W.; Varadharajan, V., Membership encryption and its applications, (Boyd, C.; Simpson, L., Information Security and Privacy - 18th Australasian Conference. Information Security and Privacy - 18th Australasian Conference, ACISP 2013. Information Security and Privacy - 18th Australasian Conference. Information Security and Privacy - 18th Australasian Conference, ACISP 2013, LNCS, vol. 7959 (2013), Springer), 219-234 · Zbl 1316.94076
[15] Guo, F.; Mu, Y.; Susilo, W., Subset membership encryption and its applications to oblivious transfer, IEEE Trans. Inform. Forensics Secur., 9, 7, 1098-1107 (2014)
[16] Huang, Y.; Katz, J.; Kolesnikov, V.; Kumaresan, R.; Malozemoff, A. J., Amortizing garbled circuits, (Garay, J. A.; Gennaro, R., CRYPTO 2014. CRYPTO 2014, LNCS, vol. 8617 (2014), Springer), 458-475 · Zbl 1335.94052
[17] Ishai, Y.; Kilian, J.; Nissim, K.; Petrank, E., Extending oblivious transfers efficiently, (Boneh, D., CRYPTO 2003. CRYPTO 2003, LNCS, vol. 2729 (2003), Springer), 145-161 · Zbl 1122.94422
[18] Kolesnikov, V.; Kumaresan, R., Improved OT extension for transferring short secrets, (Canetti, R.; Garay, J. A., CRYPTO 2013. CRYPTO 2013, LNCS, vol. 8043 (2013), Springer), 54-70 · Zbl 1316.94080
[19] Kolesnikov, V.; Kumaresan, R., On cut-and-choose oblivious transfer and its variants, (Iwata, T.; Cheon, J. H., ASIACRYPT 2015. ASIACRYPT 2015, LNCS, vol. 9452 (2015), Springer), 386-412 · Zbl 1408.94941
[20] Kurosawa, K.; Nojima, R.; Phong, L. T., Generic fully simulatable adaptive oblivious transfer, (Lopez, J.; Tsudik, G., ACNS 2011. ACNS 2011, LNCS, vol. 6715 (2011)), 274-291 · Zbl 1288.94070
[21] Larraia, E., Extending oblivious transfer efficiently - or - how to get active security with constant cryptographic overhead, (Aranha, D. F.; Menezes, A., LATINCRYPT 2014. LATINCRYPT 2014, LNCS, vol. 8895 (2015), Springer), 368-386 · Zbl 1370.94524
[22] Lindell, A. Y., Efficient fully-simulatable oblivious transfer, (Malkin, T., CT-RSA 2008. CT-RSA 2008, LNCS, vol. 4964 (2008), Springer), 52-70 · Zbl 1153.94406
[23] Lindell, Y., Fast cut-and-choose based protocols for malicious and covert adversaries, (Canetti, R.; Garay, J. A., CRYPTO 2013. CRYPTO 2013, LNCS, vol. 8043 (2013), Springer), 1-17 · Zbl 1316.94082
[24] Lindell, Y.; Pinkas, B., An efficient protocol for secure two-party computation in the presence of malicious adversaries, (Naor, M., EUROCRYPT 2007. EUROCRYPT 2007, LNCS, vol. 4515 (2007), Springer), 52-78 · Zbl 1141.94362
[25] Lindell, Y.; Pinkas, B., Secure two-party computation via cut-and-choose oblivious transfer, (Ishai, Y., TCC 2011. TCC 2011, LNCS, vol. 6597 (2011), Springer), 329-346 · Zbl 1281.94037
[26] Lindell, Y.; Riva, B., Cut-and-choose Yao-based secure computation in the online/offline and batch settings, (Garay, J. A.; Gennaro, R., CRYPTO 2014. CRYPTO 2014, LNCS, vol. 8617 (2014), Springer), 476-494 · Zbl 1335.94067
[27] Mu, Y.; Zhang, J.; Varadharajan, V., m out of n oblivious transfer, (Batten, L. M.; Seberry, J., Information Security and Privacy, 7th Australian Conference. Information Security and Privacy, 7th Australian Conference, ACISP 2002. Information Security and Privacy, 7th Australian Conference. Information Security and Privacy, 7th Australian Conference, ACISP 2002, LNCS, vol. 2384 (2002), Springer), 395-405 · Zbl 1024.94515
[28] Naor, M.; Pinkas, B., Oblivious transfer with adaptive queries, (Wiener, M. J., CRYPTO 1999. CRYPTO 1999, LNCS, vol. 1666 (1999), Springer), 573-590 · Zbl 0942.94011
[29] Naor, M.; Pinkas, B., Efficient oblivious transfer protocols, (Kosaraju, S. R., Proceedings of the Twelfth Annual Symposium on Discrete Algorithms (2001), ACM/SIAM), 448-457 · Zbl 0991.94045
[30] Nielsen, J. B.; Nordholt, P. S.; Orlandi, C.; Burra, S. S., A new approach to practical active-secure two-party computation, (Safavi-Naini, R.; Canetti, R., CRYPTO 2012. CRYPTO 2012, LNCS, vol. 7417 (2012), Springer), 681-700 · Zbl 1296.94134
[31] Ogata, W.; Kurosawa, K., Oblivious keyword search, J. Complexity, 20, 2-3, 356-371 (2004) · Zbl 1059.68050
[32] Rabin, M. O., How to Exchange Secrets by Oblivious Transfer (1981), Aiken Computation Laboratory, Harvard University, Technical Report TR-81
[33] Zhang, B.; Lipmaa, H.; Wang, C.; Ren, K., Practical fully simulatable oblivious transfer with sublinear communication, (Sadeghi, A., Financial Cryptography and Data Security - 17th International Conference. Financial Cryptography and Data Security - 17th International Conference, FC 2013. Financial Cryptography and Data Security - 17th International Conference. Financial Cryptography and Data Security - 17th International Conference, FC 2013, LNCS, vol. 7859 (2013), Springer), 78-95
[34] Zhang, J.; Wang, Y., Two provably secure k-out-of-n oblivious transfer schemes, Appl. Math. Comput., 169, 2, 1211-1220 (2005) · Zbl 1081.94036
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.