安全多方计算关键技术:茫然传输协议

doi:10.6040/j.issn.1671-9352.9.2021.009

摘要/Abstract

摘要： 目前,云计算、大数据、物联网及人工智能技术的广泛应用,在给人们的工作与生活带来极大便利的同时,也带来了巨大的数据隐私泄露风险。密码技术作为一种基于内容级别的保护,是信息安全的最后一道屏障。安全多方计算技术可以在保护参与方输入的情况下,完成分布式的功能函数计算,在隐私保护下的数据安全协同利用方面具有独到的优势。茫然传输协议是安全多方计算协议中最关键的密码原语之一。本文首先介绍了主流安全多方计算协议中各种基础茫然传输协议的使用原理,包括Yao混乱电路与2选1茫然传输协议、GMW协议与4选1茫然传输协议、Beaver三元组与2选1茫然传输协议;其次,介绍了茫然传输协议的性能优化技术,包括预计算茫然传输协议以及茫然传输扩展协议;第三,介绍了茫然传输协议的各种变体,主要是Cut-and-Choose茫然传输协议及双向Cut-and-Choose茫然传输协议;最后,对茫然传输协议未来研究方向进行了展望。

关键词: 茫然传输, 安全多方计算,茫然传输扩展, 随机茫然传输, 茫然伪随机函数

Abstract: Big data and artificial intelligence data processing technology in cloud computing environment bring huge data privacy risks. As a content-based protection, cryptography is the last line of defense of information security. Secure MultiParty Computation can perform the distributed function evaluation under the condition of protecting the input of participants, it has unique advantages in data privacy protection under cloud computing. The core component of Secure MultiParty Computation is the Oblivious Transfer protocol, which plays an important role in all todays Secure MultiParty Computation protocols. Firstly, the principles of various basic Oblivious Transfer protocols in the Secure MultiParty Computation protocols is introduced, which including the Yao garbled circuit and 1 out of 2 Oblivious Transfer protocol, GMW protocol and 1 out of 4 Oblivious Transfer protocol, beaver triple 1 out of 2 Oblivious Transfer protocol. Secondly, the performance optimization technology of Oblivious Transfer protocol is introduced, including precomputing Oblivious Transfer protocol and Oblivious Transfer extension. Thirdly, various variants of Oblivious Transfer are introduced, mainly including Cut and Choose Oblivious Transfer and Cut and Choose Bilateral Oblivious Transfer. Finally, the future research direction of Oblivious Transfer is prospected.

Key words: oblivious transfer, secure multiparty computation, oblivious transfer extension, random oblivious transfer, oblivious pseudo random function

中图分类号:

TP309

徐秋亮,蒋瀚,赵圣楠. 安全多方计算关键技术:茫然传输协议[J]. 《山东大学学报(理学版)》, 2021, 56(10): 61-71.

XU Qiu-liang, JIANG Han, ZHAO Sheng-nan. Oblivious transfer protocols in secure multiparty computation[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(10): 61-71.

参考文献

[1] YAO Qizhi. Protocols for secure computations[C] //IEEE Symposium on Foundations of Computer Science(FOCS). Los Alamitos: IEEE Computer Society, 1982: 160-164.
[2] RABIN M. How to exchange secrets by oblivious transfer[J]. Technical Memo TR-81, 1981.
[3] EVEN S, GOLDREICH O, LEMPEL A. A randomized protocol for signing contracts[J]. Communications of the ACM, 1985, 28(6):637-647.
[4] BEAVER, D. Precomputing oblivious transfer[C] //COPPERSMITH D. Advances in Cryptology—CRYPT0’95. New York: Springer, 1995: 97-109.
[5] YAO Qizhi. How to generate and exchange secrets[C] //IEEE Symposium on Foundations of Computer Science(FOCS). Los Alamitos: IEEE Computer Society, 1986: 162-167.
[6] GOLDREICH O, MICALI S, WIGDERSON A. How to play any mental game[C] //Proceedings of the nineteenth annual ACM Symposium on Theory of computing. New York: ACM Press, 1987: 218-229.
[7] BEN-Or M, GOLDWASSER S, WIGDERSON A. Completeness theorems for non-cryptographic fault-tolerant distributed computation(extended abstract)[C] //20th Annual ACM Symposium on Theory of Computing. New York: ACM Press, 1988: 1-10.
[8] BEAVER D. Efficient multiparty protocols using circuit randomization[C] //Annual International Cryptology Conference. Berlin: Springer, 1991: 420-432.
[9] PEIKERT C, VAIKUNTANATHAN V, WATERS B. A framework for efficient and composable oblivious transfer[C] //Wagner D. Advances in Cryptology—CRYPTO 2008. New York: Springer, 2008: 554-571. doi:10.1007/978-3-540-85174-5_31.
[10] BRASSARD G, CREPEAU C, ROBERT J M. All-or-nothing disclosure of secrets[C] //ODLYZKO A M. Advances in Cryptology—CRYPTO’ 86. CRYPTO 1986. Lecture Notes in Computer Science, Vol 263. Berlin: Springer, 1987. https://doi.org/10.1007/3-540-47721-7_17.
[11] NAOR Moni, PINKAS Benny. Efficient oblivious transfer protocols[C] //Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms(SODA'01). New York: Society for Industrial and Applied Mathematics, 2001: 448-457.
[12] 张斌, 徐秋亮, 蒋瀚. 新的可抵抗自适应敌手的可组合茫然传输协议[J]. 通信学报, 2011, 32(11A):196-203.
[13] GARAY J A, ISHAI Y, KUMARESAN R, et al. On the complexity of UC commitments[M]. Berlin: Springer, 2014.
[14] 魏晓超, 蒋瀚, 赵川. 一个高效可完全模拟的n取1茫然传输协议[J]. 计算机研究与发展, 2016, 53(11):2475-2481. WEI Xiaochao, JIANG Han, ZHAO Chuan. An efficient 1-out-of-n oblivious transfer protocol with full simulation[J]. Journal of Computer Research and Development, 2016, 53(11):2475-2481.
[15] PULLONEN Pille, BOGDANOV Dan, SCHNEIDER Thomas. The design and implementation of a two-party protocol suite for SHAREMIND 3. CYBERNETICA Institute of Information Security[EB/OL].[2012-04-17]. http://research.cyber.ee/
[16] PAILLIER Pascal. Public-Key cryptosystems based on composite degree residuosity classes[C] //EURO-CRYPT. [S.l.] : Springer, 1999.
[17] DAMGARD Ivan, GEISLER Martin, KRIGARD Mikkel. Homomorphic encryption and secure comparison[J]. International Journal of Applied Cryptography, 2008, 1(1):22-31.
[18] GILBOA Niv. Two party RSA key generation[C] //CRYPTO. [S.l.] : ACM Press, 1999: 116-129.
[19] DEMMLER Daniel, SCHNEIDER Thomas, ZOHNER Michael. ABY: a framework for efficient mixed-protocol secure two-party computation[C] //NDSS.[S.l.] : [s.n.] , 2015. DOI: 10.14722/ndss.2015.23113.
[20] NIELSEN J B, NORDHOLT P S, ORLANDI C, et al. A new approach to practical active-secure two-party computation[C] //Advances in Cryptology-CRYPTO'12, Volume 7417 of LNCS. [S.l.] : Springer, 2012: 681-700.
[21] IMPAGLIAZZO R, RUDICH S. Limits on the provable consequences of one-way permutations[C] //Advances in Cryptology(CRYPTO'88), Volume 403 of LNCS. [S.l.] :Springer, 1988: 8-26.
[22] BEAVER D. Correlated pseudorandomness and the complexity of private computations[C] //Symposium on the Theory of Computing(STOC'96). [S.l.] : ACM, 1996: 479-488.
[23] ISHAI Y, KILIAN J, NISSIM K, et al. Extending oblivious transfers efficiently[C] //Advances in Cryptology-CRYPTO'03, Volume 2729 of LNCS. [S.l.] : Springer, 2003: 145-161.
[24] ASHAROV G, LINDELL Y, SCHNEIDER T, et al. More efficient oblivious transfer and extensions for faster secure computation[C] //ACM CCS'13. [S.l.] : ACM, 2013: 535-548.
[25] KOLESNIKOV V, KUMARESAN R. Improved OT extension for transferring short secrets[C] //Advances in Cryptology-CRYPTO'13, Volume 8043 of LNCS. [S.l.] : Springer, 2013: 54-70.
[26] PINKAS B. Fair secure two-party computation[C] //Advances in Cryptology—Eurocrypt 2003. Berlin: Springer, 2003: 87-105.
[27] LINDELL Y, PINKAS B. An efficient protocol for secure two-party computation in the presence of malicious adversaries[C] //Advances in Cryptology-EUROCRYPT 2007. Berlin: Springer, 2007: 52-78.
[28] LINDELL Y, PINKAS B. An efficient protocol for secure two-party computation in the presence of malicious adversaries[M] //Advances in Cryptology-EUROCRYPT 2007. Berlin: Springer, 2007: 52-78.
[29] LINDELL Y, PINKAS B. Secure two-party computation via cut-and-choose oblivious transfer[J]. Theory of Cryptography, 2011: 329-346.
[30] 赵川, 蒋瀚, 魏晓超,等. Cut-and-Choose双向不经意传输[J]. 软件学报, 2016, 28(2):352-360. ZHAO Chuan, JIANG Han, WEI Xiaochao, et al. Cut-and-Choose bilateral oblivious transfer[J]. Journal of Software, 2016, 28(2):352-360.
[31] JIANG Han, XU Qiuliang, LIU Changyuan, et al. Cut-and-Choose bilateral oblivious transfer protocol based on DDH assumption[J/OL]. Journal of Ambient Intelligence and Humanized Computing, 2018. https://link.springer.com/article/10.1007/s12652-018-0713-7

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed