无条件安全不经意多项式估值：综述与新发现

doi:10.1007/s11390-022-0878-6

Abstract

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 ;

Louis Cianciullo and Hossein Ghodosi. Unconditionally Secure Oblivious Polynomial Evaluation: A Survey and New Results[J].Journal of Computer Science and Technology, 2022, 37(2): 443-458.

References

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 10

[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 .

Unconditionally Secure Oblivious Polynomial Evaluation: A Survey and New Results

PDF (PC)

Supplement

Abstract

Cite this article

share this article

References

Related Articles 2

Metrics

Comments

Recommended 10

[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.