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.

PDF (PC)

3

Supplement

1

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] Zhou Di;. A Recovery Technique for Distributed Communicating Process Systems[J]. , 1986, 1(2): 34 -43 .
[2] Li Wei;. A Structural Operational Semantics for an Edison Like Language(2)[J]. , 1986, 1(2): 42 -53 .
[3] Chen Shihua;. On the Structure of Finite Automata of Which M Is an(Weak)Inverse with Delay τ[J]. , 1986, 1(2): 54 -59 .
[4] Li Wanxue;. Almost Optimal Dynamic 2-3 Trees[J]. , 1986, 1(2): 60 -71 .
[5] Feng Yulin;. Recursive Implementation of VLSI Circuits[J]. , 1986, 1(2): 72 -82 .
[6] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[7] Wang Xuan; Lü Zhimin; Tang Yuhai; Xiang Yang;. A High Resolution Chinese Character Generator[J]. , 1986, 1(2): 1 -14 .
[8] C.Y.Chung; H.R.Hwa;. A Chinese Information Processing System[J]. , 1986, 1(2): 15 -24 .
[9] Sun Zhongxiu; Shang Lujun;. DMODULA:A Distributed Programming Language[J]. , 1986, 1(2): 25 -31 .
[10] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .

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