Journal of Computer Science and Technology ›› 2022, Vol. 37 ›› Issue (2): 443-458.doi: 10.1007/s11390-022-0878-6

Special Issue: Surveys; Theory and Algorithms

• Theory and Algorithms • Previous Articles     Next Articles

Unconditionally Secure Oblivious Polynomial Evaluation: A Survey and New Results

Louis Cianciullo and Hossein Ghodosi        

  1. College of Science and Engineering, James Cook University, Townsville, QLD 4811, Australia
  • Received:2020-09-23 Revised:2021-12-12 Accepted:2022-01-20 Online:2022-03-31 Published:2022-03-31
  • Contact: Louis Cianciullo E-mail:louis.cianciullo@my.jcu.edu.au
  • About author:Louis Cianciullo received his Bachelor's degree (Hons) in information technology from James Cook University (JCU), Townsville, in 2016. He is now employed as a software engineer and is also working on completing his Ph.D. degree in computer science from JCU, Townsville. His research focuses on multi-party computation and information theoretic cryptography protocols.

Oblivious polynomial evaluation (OPE) is a two-party protocol that allows a receiver, R to learn an evaluation f(α), of a sender, S's polynomial f(x), whilst keeping both α and f(x) private. This protocol has attracted a lot of attention recently, as it has wide ranging applications in the field of cryptography. In this article we review some of these applications and, additionally, take an in-depth look at the special case of information theoretic OPE. Specifically, we provide a current and critical review of the existing information theoretic OPE protocols in the literature. We divide these protocols into two distinct cases (three-party and distributed OPE) allowing for the easy distinction and classification of future information theoretic OPE protocols. In addition to this work, we also develop several modifications and extensions to existing schemes, resulting in increased security, flexibility and efficiency. Lastly, we also identify a security flaw in a previously published OPE scheme.


Key words: oblivious polynomial evaluation; unconditionally secure; information theoretic ;

[1] Naor M, Pinkas B. Oblivious transfer and polynomial evaluation. In Proc. the 31st Annual ACM Symposium on Theory of Computing, May 1999, pp.245-254. DOI: 10.1145/301250.301312.
[2] Even S, Goldreich O, Lempel A. A randomized protocol for signing contracts. In Proc. CRYPTO'82, Aug. 1982, pp.205-210. DOI: 10.1007/978-1-4757-0602-4_19.
[3] Cianciullo L, Ghodosi H. Efficient information theoretic multi-party computation from oblivious linear evaluation. In Proc. the 12th IFIP WG 11.2 International Conference on Information Security Theory and Practice, Dec. 2019, pp.78-90. DOI: 10.1007/978-3-030-20074-9_7.
[4] Chang Y C, Lu C J. Oblivious polynomial evaluation and oblivious neural learning. In Proc. the 7th International Conference on the Theory and Application of Cryptology and Information Security Gold Coast, Dec. 2001, pp.369-384. DOI: 10.1007/3-540-45682-1_22.
[5] Cianciullo L, Ghodosi H. Unconditionally secure distributed oblivious polynomial evaluation. In Proc. the 21st International Conference on Information Security and Cryptology, Nov. 2018, pp.132-142. DOI: 10.1007/978-3-030-12146-4_9.
[6] Ghosh S, Nielsen J B, Nilges T. Maliciously secure oblivious linear function evaluation with constant overhead. In Proc. the 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Dec. 2017, pp.629-659. DOI: 10.1007/978-3-319-70694-8_22.
[7] Hazay C, Lindell Y. Efficient oblivious polynomial evaluation with simulation-based security. IACR Cryptology ePrint Archive, 2009, 2009: Article No. 459.
[8] Zhu H, Bao F. Augmented oblivious polynomial evaluation protocol and its applications. In Proc. the 10th European Symposium on Research in Computer Security, Sept. 2005, pp.222-230. DOI: 10.1007/11555827_13.
[9] Li H D, Yang X, Feng D G, Li B. Distributed oblivious function evaluation and its applications. Journal of Computer Science and Technology, 2004, 19(6): 942-947. DOI: 10.1007/BF02973458.
[10] Naor M, Pinkas B. Oblivious polynomial evaluation. SIAM Journal on Computing, 2006, 35(5): 1254-1281. DOI: 10.1137/S0097539704383633.
[11] Tonicelli R, Nascimento A C A, Dowsley R, Müller-Quade J, Imai H, Hanaoka G, Otsuka A. Information-theoretically secure oblivious polynomial evaluation in the commodity-based model. International Journal of Information Security, 2015, 14(1): 73-84. DOI: 10.1007/s10207-014-0247-8.
[12] Döttling N, Ghosh S, Nielsen J B, Nilges T, Trifiletti R. TinyOLE: Efficient actively secure two-party computation from oblivious linear function evaluation. In Proc. the 2017 ACM SIGSAC Conference on Computer and Communications Security, October 30-November 3, 2017, pp.2263-2276. DOI: 10.1145/3133956.3134024.
[13] özarar M, özgit A. Secure multiparty overall mean computation via oblivious polynomial evaluation. In Proc. the 1st International Conference on Security of Information and Networks, May 2007, pp.84-95.
[14] Chang Y C, Lu C J. Oblivious polynomial evaluation and oblivious neural learning. Theoretical Computer Science, 2005, 341(1/2/3): 39-54. DOI: 10.1016/j.tcs.2005.03.049.
[15] Ogata W, Kurosawa K. Oblivious keyword search. Journal of Complexity, 2004, 20(2/3): 356-371. DOI: 10.1016/j.jco.2003.08.023.
[16] Lindell P. Privacy preserving data mining. Journal of Cryptology, June 2002, 15(3): 177-206. DOI: 10.1007/s00145-001-0019-2.
[17] Damgard I, Haagh H, Nielsen M, Orlandi C. Commodity-based 2PC for arithmetic circuits. In Proc. the 17th IMA International Conference on Cryptography and Coding, Dec. 2019, pp.154-177. DOI: 10.1007/978-3-030-35199-1_8.}
[18] Damgard I, Pastro V, Smart N, Zakarias S. Multiparty computation from somewhat homomorphic encryption. In Proc. the 32nd Annual Cryptology Conference, Aug. 2012, pp.643-662. DOI: 10.1007/978-3-642-32009-5_38.
[19] Keller M, Orsini E, Scholl P. MASCOT: Faster malicious arithmetic secure computation with oblivious transfer. In Proc. the 2016 ACM SIGSAC Conference on Computer and Communications Security, Oct. 2016, pp.830-842.
[20] Lindell Y, Pinkas B, Smart N P, Yanai A. Efficient constant round multi-party computation combining BMR and SPDZ. In Proc. the 35th Annual Cryptology Conference, Aug. 2015, pp.319-338. DOI: 10.1007/978-3-662-48000-7_16.
[21] Hazay C. Oblivious polynomial evaluation and secure set-intersection from algebraic PRFs. Journal of Cryptology, 2018, 31(2): 537-586. DOI: 10.1007/s00145-017-9263-y.
[22] Otsuka A, Imai H. Unconditionally secure electronic voting. In Towards Trustworthy Elections: New Directions in Electronic Voting, Chaum D, Jakobsson M, Rivest R, Ryan P, Benaloh J, Kutylowski M, Adida B (eds.), Springer, 2010, pp.107-123. DOI: 10.1007/978-3-642-12980-3_6.
[23] Corniaux C L F, Ghodosi H. An information-theoretically secure threshold distributed oblivious transfer protocol. In Proc. the 15th International Conference on Information Security and Cryptology, Nov. 2012, pp.184-201. DOI: https://doi.org/10.1007/978-3-642-37682-5_14.
[24] Crépeau C, Morozov K, Wolf S. Efficient unconditional oblivious transfer from almost any noisy channel. In Proc. the 4th International Conference on Security in Communication Networks, Sept. 2004, pp.47-59. DOI: 10.1007/978-3-540-30598-9_4.
[25] Rivest R L. Unconditionally secure commitment and oblivious transfer schemes using private channels and a trusted initializer. http://people.csail.mit.edu/rivest/Rivest-commitment.pdf, Nov. 2021.
[26] Bo Y, Wang Q, Cao Y. An efficient and unconditionally-secure oblivious polynomial evaluation protocol. In Proc. the 1st International Symposium on Data, Privacy, and E-Commerce, Nov. 2007, pp.181-184. DOI: 10.1109/ISDPE.2007.60.
[27] Chor B, Kushilevitz E. A zero-one law for Boolean privacy. SIAM Journal on Discrete Mathematics, 1991, 4(1): 36-47. DOI: 10.1137/0404004.
[28] Cramer R, Damgard I B, Nielsen J B. Secure Multiparty Computation and Secret Sharing. Cambridge University Press, 2015. DOI: 10.1017/CBO9781107337756.
[29] Corniaux C L F, Ghodosi H. A verifiable distributed oblivious transfer protocol. In Proc. the 16th Australasian Conference on Information Security and Privacy, July 2011, pp.444-450. DOI: 10.1007/978-3-642-22497-3_33.
[30] Blundo C, D'Arco P, De Santis A, Stinson D. On unconditionally secure distributed oblivious transfer. Journal of Cryptology, 2007, 20(3): 323-373. DOI: 10.1007/s00145-007-0327-2.}
[31] Shamir A. How to share a secret. Commun. ACM, 1979, 22(11): 612-613. DOI: 10.1145/359168.359176.
[32] Cheong K Y, Koshiba T, Nishiyama S. Strengthening the security of distributed oblivious transfer. In Proc. the 14th Australasian Conference on Information Security and Privacy, July 2009, pp.377-388. DOI: 10.1007/978-3-642-02620-1_26.
[33] Naor M, Pinkas B. Distributed oblivious transfer. In Proc. the 6th International Conference on the Theory and Application of Cryptology and Information Security, Dec. 2000, pp.205-219. DOI: 10.1007/3-540-44448-3_16.
[34] Hanaoka G, Imai H, Mueller-Quade J, Nascimento A C A, Otsuka A, Winter A. Information theoretically secure oblivious polynomial evaluation: Model, bounds, and constructions. In Proc. the 9th Australasian Conference on Information Security and Privacy, July 2004, pp.62-73. DOI: 10.1007/978-3-540-27800-9_6.
[35] Beaver D. Commodity-based cryptography (extended abstract). In Proc. the 29th Annual ACM Symposium on Theory of Computing, May 1997, pp.446-455. DOI: 10.1145/258533.258637.
[1] Hong-Da Li, Xiong Yang, Deng-Guo Feng, and Bao Li. Distributed Oblivious Function Evaluation and Its Applications [J]. , 2004, 19(6): 0-0.
[2] Hong-Da Li, Dong-Yao Ji, Deng-Guo Feng, and Bao Li. Oblivious Polynomial Evaluation [J]. , 2004, 19(4): 0-0.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] . Online First Under Construction [J]. Journal of Computer Science and Technology, 0, (): 1 .
[2] Li Zhang, Jia-Hao Tian, Jing Jiang, Yi-Jun Liu, Meng-Yuan Pu, Tao Yue. Empirical Research in Software Engineering-A Literature Survey[J]. Journal of Computer Science and Technology, 2018, 33(5): 876 -899 .
[3] Xue-Jun Yang (杨学军), Senior Member, CCF, Member, ACM, IEEE, Xiang-Ke Liao (廖湘科), Senior Member CCF, Member, ACM, Kai Lu . The TianHe-1A Supercomputer: Its Hardware and Software[J]. , 2011, 26(3): 344 -351 .
[4] Zhi-Neng Chen, Chong-Wah Ngo, Wei Zhang, Juan Cao, Yu-Gang Jiang. Name-Face Association in Web Videos: A Large-Scale Dataset, Baselines, and Open Issues[J]. , 2014, 29(5): 785 -798 .
[5] Fei Xia, De-Jun Jiang, Jin Xiong, Ning-Hui Sun. A Survey of Phase Change Memory Systems[J]. , 2015, 30(1): 121 -144 .
[6] Yue-Feng Du, De-Rong Shen, Tie-Zheng Nie, Yue Kou, Ge Yu. Content-Related Repairing of Inconsistencies in Distributed Data[J]. , 2016, 31(4): 741 -758 .
[7] Xue-Yan Wang, Qiang Zhou, Yi-Ci Cai, Gang Qu. Spear and Shield: Evolution of Integrated Circuit Camouflaging[J]. , 2018, 33(1): 42 -57 .
[8] Xianzhi Wang, Chaoran Huang, Lina Yao, Boualem Benatallah, Manqing Dong. A Survey on Expert Recommendation in Community Question Answering[J]. Journal of Computer Science and Technology, 2018, 33(4): 625 -653 .
[9] André Brinkmann, Kathryn Mohror, Weikuan Yu, Philip Carns, Toni Cortes, Scott A. Klasky, Alberto Miranda, Franz-Josef Pfreundt, Robert B. Ross, Marc-André Vef. Ad Hoc File Systems for High-Performance Computing[J]. Journal of Computer Science and Technology, 2020, 35(1): 4 -26 .
[10] Yu-Tong Lu, Peng Cheng, Zhi-Guang Chen. Design and Implementation of the Tianhe-2 Data Storage and Management System[J]. Journal of Computer Science and Technology, 2020, 35(1): 27 -46 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved