Oblivious transfer (OT) protocols mainly contain three categories: 1-out-of-2 OT, 1-out-of-n OT, and k-out-of-n OT. In most cases, they are treated as cryptographic primitives and are usually executed without consideration of possible attacks that might frequently occur in an open network, such as an impersonation, replaying, or man-in-the-middle attack. Therefore, when used in certain applications, such as mental poker games and fair contract signings, some extra mechanisms must be combined to ensure the security of the protocol. However, after a combination, we found that very few of the resulting schemes are efficient enough in terms of communicational cost, which is a significant concern for generic commercial transactions. Therefore, we propose a novel k-out-of-n oblivious transfer protocol based on bilinear pairing, which not only satisfies the requirements of a k-out-of-n OT protocol, but also provides mutual authentication to resist malicious attacks. Meanwhile, it is efficient in terms of communication cost. 1. Introduction An oblivious transfer (OT) is an important primitive for designing security services. It can be used in various applications like the signing of fair contracts, oblivious database searches, mental poker games, privacy-preserving auctions, secure multiparty computations [1], and so on. In 1981, Rabin [2] first proposed an interactive OT scheme in which the probability of the receiver’s capability to decrypt a message sent by the sender is 1/2. Rabin used the proposed OT to design a 3-pass secret exchange (EOS) protocol, hoping that two parties can exchange their secrets fairly. In 1985, Even et al. [3] presented a more generalized OT, called 1-out-of-2 OT ( ), in which a sender sends two encrypted messages to a chooser with only one of which the chooser can decrypt. They also presented a contract-signing protocol by evoking multiple times to prevent one party from obtaining the other party’s contract signature without first showing his own. In 1986, Brassard et al. [4] further extended into a 1-out-of-n OT ( , also known as “all-or-nothing”), in which only one out of n sent messages can actually be obtained by the chooser. The authors pointed out that their scheme can be used to implement a multiparty mental poker game [5] against a player coalition. In contrast to the interactive versions described above, Bellare and Micali [6] first proposed a noninteractive scheme in 1989. In this scheme, a user obliviously transfers two messages to another party equipped with two public keys to decrypt one of the messages. From 1999 to
References
[1]
F. Kerschbaum, N. Oertel, and L. W. F. Chaves, “Privacy-preserving computation of benchmarks on item-level data using RFID,” in Proceedings of the 3rd ACM Conference on Wireless Network Security (WiSec '10), pp. 105–110, March 2010.
[2]
M. O. Rabin, “How to exchange secrets with oblivious transfer,” Tech. Rep. TR-81, Aiken Computation Lab, Harvard University, Cambridge, Mass, USA, 1981.
[3]
S. Even, O. Goldreich, and A. Lempel, “A randomized protocol for signing contracts,” Communications of the ACM, vol. 28, no. 6, pp. 637–647, 1985.
[4]
G. Brassard, C. Crepeau, and J.-M. Robert, “All-or-nothing disclosure of secrets,” in Proceedings of the International Conference on Advances in Cryptology (CRYPTO '86), vol. 263 of Lecture Notes in Computer Science, pp. 234–238, 1986.
[5]
J. S. Chou and Y. S. Yeh, “Mental poker game based on a bit commitment scheme through network,” Computer Networks, vol. 38, no. 2, pp. 247–255, 2002.
[6]
M. Bellare and S. Micali, “Non-interactive oblivious transfer and application,” in Proceedings of the International Conference on Advances in Cryptology (CRYPTO '89), vol. 435 of Lecture Notes in Computer Science, pp. 547–557, 1989.
[7]
M. Naor and B. Pinkas, “Oblivious transfer with adaptive queries,” in Proceedings of the International Conference on Advances in Cryptology (CRYPTO '99), Lecture Notes in Computer Science, pp. 573–590, 1999.
[8]
M. Naor, B. Pinkas, and R. Sumner, “Privacy preserving auctions and mechanism design,” in Proceedings of the 1st ACM Conference on Electronic Commerce, 1999.
[9]
M. Naor and B. Pinkas, “Distributed oblivious transfer,” in Proceedings of the International Conference on Advances in Cryptology (CRYPTO '00), vol. 1976 of Lecture Notes in Computer Science, 2000.
[10]
M. Naor and B. Pinkast, “Oblivious transfer and polynomial evaluation,” in Proceedings of the 31st Annual ACM Symposium on Theory of Computing (FCRC '99), pp. 245–254, May 1999.
[11]
M. Naor and B. Pinkas, “Efficient oblivious transfer protocols,” in Proceedings of the 12th annual ACM-SIAM symposium on Discret Mathematics (SODA '01), pp. 448–457, 2001.
[12]
H. Ghodosi, “On insecurity of Naor-Pinkas' distributed oblivious transfer,” Information Processing Letters, vol. 104, no. 5, pp. 179–182, 2007.
[13]
Y. Mu, J. Zhang, and V. Varadharajan, “m out of n oblivious transfer,” in Proceedings of the 7th Australasian Conference on Information Security and Privacy (ACISP '02), vol. 2384 of Lecture Notes in Computer Science, pp. 395–405, 2002.
[14]
H. Ghodosi and R. Zaare-Nahandi, “Comments on the ‘m out of n oblivious transfer’,” Information Processing Letters, vol. 97, no. 4, pp. 153–155, 2006.
[15]
W. Ogata and K. Kurosawa, “Oblivious keyword search,” Journal of Complexity, vol. 20, no. 2-3, pp. 356–371, 2004.
[16]
C. K. Chu and W. G. Tzeng, “Efficient k-out-of-n oblivious transfer schemes with adaptive and non-adaptive queries,” in Proceedings of the 8th International Workshop on Theory and Practice in Public Key Cryptography (PKC '05), pp. 172–183, January 2005.
[17]
J. Zhang and Y. Wang, “Two provably secure k-out-of-n oblivious transfer schemes,” Applied Mathematics and Computation, vol. 169, no. 2, pp. 1211–1220, 2005.
[18]
H. F. Huang and C. C. Chang, “A new design for efficient t-out-n oblivious transfer scheme,” in Proceedings of the 19th International Conference on Advanced Information Networking and Applications (AINA '05), pp. 28–30, March 2005.
[19]
A. Parakh, “Oblivious transfer using elliptic curves,” in Proceedings of the 15th International Conference on Computing (CIC '06), pp. 323–328, November 2006.
[20]
S. Kim and G. Lee, “Secure verifiable non-interactive oblivious transfer protocol using RSA and Bit commitment on distributed environment,” Future Generation Computer Systems, vol. 25, no. 3, pp. 352–357, 2009.
[21]
Y. F. Chang and W. C. Shiao, “The essential design principles of verifiable non-interactive OT protocols,” in Proceedings of the 8th International Conference on Intelligent Systems Design and Applications (ISDA '08), pp. 241–245, November 2008.
[22]
L. M. Kohnfelder, “On the signature reblocking problem in public-key cryptography,” Communications of the ACM, vol. 21, no. 2, p. 179, 1978.
[23]
S. Halevi and Y. T. Kalai, “Smooth projective hashing and two-message oblivious transfer,” Cryptology ePrint Archive 2007/118, 2007.
[24]
J. Camenisch, G. Neven, and A. Shelat, “Simulatable adaptive oblivious transfer,” in Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, vol. 4515 of Lecture Notes in Computer Science, pp. 573–590, 2007.
[25]
M. Green and S. Hohenberger, “Blind identity-based encryption and simulatable oblivious transfer,” Cryptology ePrint Archive 2007/235, 2007.
[26]
J. Qin, H. W. Zhao, and M. Q. Wang, “Non-interactive oblivious transfer protocols,” in Proceedings of the International Forum on Information Technology and Applications (IFITA '09), pp. 120–124, May 2009.
[27]
C. C. Chang and J. S. Lee, “Robust t-out-of-n oblivious transfer mechanism based on CRT,” Journal of Network and Computer Applications, vol. 32, no. 1, pp. 226–235, 2009.
[28]
X. Ma, L. Xu, and F. Zhang, “Oblivious transfer with timed-release receiver's privacy,” Journal of Systems and Software, vol. 84, no. 3, pp. 460–464, 2011.
[29]
W. Stallings, Cryptography and Network Security—Principals and Practices, Prentice Hall, Upper Saddle River, NJ, USA, 3rd edition, 2003.
[30]
S. Goldwasser and S. Micali, “Probabilistic encryption & how to play mental poker keeping secret all partial information,” in Proceedings of the 40th annual ACM symposium on Theory of Computing (STOC '82), pp. 365–377, 1982.
[31]
D. Boneh and M. K. Franklin, “Identity-based encryption from the Weil pairing,” in Proceedings of the International Conference on Advances in Cryptology (CRYPTO '01), vol. 2139 of Lecture Notes in Computer Science, pp. 213–229, 2001.
[32]
D. R. Stinson, Cryptography—Theory & Practice, Chapman & Hall/CRC Taylor & Francis Group, 3rd edition, 2006.
[33]
A. Boldyreva, “Threshold signatures, multisignatures and blind signatures based on the Gap-Diffie-Hellman-group signature scheme,” in Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography, vol. 2567 of Lecture Notes in Computer Science, pp. 31–46, 2003.
[34]
M. Bellare, C. Namprempre, D. Pointcheval, and M. Semanko, “The one-more-RSA-inversion problems and the security of chaum's blind signature scheme,” in Proceedings of Financial Cryptography (FC '01), vol. 2248 of Lecture Notes in Computer Science, pp. 319–338, 2003.