ZHAO Chuan, JIANG Han, XU Qiuliang, WANG Yilei, WEI Xiaochao, CUI Shujie. Fast Two-Output Secure Computation with Optimal Error Probability[J]. Chinese Journal of Electronics, 2017, 26(5): 933-941. doi: 10.1049/cje.2016.06.025
Citation: ZHAO Chuan, JIANG Han, XU Qiuliang, WANG Yilei, WEI Xiaochao, CUI Shujie. Fast Two-Output Secure Computation with Optimal Error Probability[J]. Chinese Journal of Electronics, 2017, 26(5): 933-941. doi: 10.1049/cje.2016.06.025

Fast Two-Output Secure Computation with Optimal Error Probability

doi: 10.1049/cje.2016.06.025
Funds:  This work is supported by the National Natural Science Foundation of China (No.61572294, No.61502218, No.61173139), the Outstanding Young Scientists Foundation Grant of Shandong Province (No.BS2014DX016), and the Natural Science Foundation of Shandong Province (No.ZR2013FQ021).
More Information
  • Corresponding author: JIANG Han (corresponding author) was born in 1974. He received the Ph.D. degree in technology of computer application from Shandong University in 2008. He is now a lecturer in School of Computer Science and Technology, Shandong University. His research interests include practical secure multi-party computation. (Email:jianghan@sdu.edu.cn)
  • Received Date: 2015-07-15
  • Rev Recd Date: 2015-12-06
  • Publish Date: 2017-09-10
  • Cut-and-choose paradigm makes Yao's protocol for two-party computation secure in malicious model with an error probability. In CRYPTO 2013, based on multi-phase cut-and-choose, Lindell reduced this probability to the optimal value. However, this work can only compute single-output functions with optimal error probability. We transform multi-phase cut-and-choose for singleoutput case into one that can deal with two-output functions, meanwhile maintaining the optimal error probability. Based on this new paradigm, we propose an efficient two-output secure computation protocol. Besides, by utilizing the specific property of the output garbled keys, we solve the authenticity issue of the generator's output with only symmetric cryptographic operations linear in the output length of the generator, which is the most efficient method so far in standard model without Random oracle (RO).
  • loading
  • M. Naor and B. Pinkas, "Efficient oblivious transfer protocols", Proc. of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Washington, D.C., USA, pp.448-457, 2001.
    C. Peikert, V. Vaikuntanathan and B. Waters, "A framework for efficient and composable oblivious transfer", Advances in Cryptology-CRYPTO, Santa Barbara, CA, USA, pp.554-571, 2008.
    S. Goldwasser, S. Micali and C. Rackoff, "The knowledge complexity of interactive proof-systems", Proc. of the 17th Annual ACM Symposium on Theory of Computing, Providence, Rhode Island, USA, pp.291-304, 1985.
    A. Shamir, "How to share a secret", Communications of the ACM, Vol.22, No.11, pp.612-613, 1979.
    F. Zhang and J. Zhang, "Efficient and information-theoretical secure verifiable secret sharing over bilinear groups", Chinese Journal of Electronics, Vol.23, No.1, pp.13-17, 2014.
    W. Diffie and M.E. Hellman, "New directions in cryptography", IEEE Transactions on Information Theory, Vol.22, No.6, pp.644-654, 1976.
    Y. Li, J. Zhu, N. Zhang, et al., "RYY++:A novel provably secure identity-based authenticated key agreement protocol", Chinese Journal of Electronics, Vol.24, No.2, pp.332-337, 2015.
    A.C. Yao, "Protocols for secure computations", Proc. of the 23rd Annual IEEE Symposium on Foundations of Computer Science, Chicago, Illinois, USA, pp.160-164, 1982.
    A.C. Yao, "How to generate and exchange secrets", Proc. of the 27th Annual IEEE Symposium on Foundations of Computer Science, Toronto, Ontario, Canada, pp.162-167, 1986.
    Y. Lindell and B. Pinkas, "An efficient protocol for secure twoparty computation in the presence of malicious adversaries", Advances in Cryptology-EUROCRYPT 2007, Barcelona, Spain, pp.52-78, 2007.
    O. Goldreich, Foundations of Cryptography:Volume 2, Basic Applications, Cambridge University Press, New York, USA, 2004.
    Y. Lindell and B. Pinkas, "Secure two-party computation via cut-and-choose oblivious transfer", Journal of Cryptology, Vol.25, No.4, pp.680-722, 2012.
    A. Shelat and C.H. Shen, "Two-output secure computation with malicious adversaries", Advances in Cryptology-EUROCRYPT, Tallinn, Estonia, pp.386-405, 2011.
    Y. Lindell, "Fast cut-and-choose based protocols for malicious and covert adversaries", Advances in Cryptology-CRYPTO, Santa Barbara, CA, USA, pp.1-17, 2013.
    Y. Huang, J. Katz and D. Evans, "Efficient secure two-party computation using symmetric cut-and-choose", Advances in Cryptology-CRYPTO, Santa Barbara, CA, USA, pp.18-35, 2013.
    L.T. Brandão, "Secure two-party computation with reusable bit-commitments, via a cut-and-choose with forge-and-lose technique", Advances in Cryptology-ASIACRYPT, Bangalore, India, pp.441-463, 2013.
    T.K. Frederiksen, T.P. Jakobsen and J.B. Nielsen, "Faster maliciously secure two-party computation using the GPU", Security and Cryptography for Networks, Amalfi, Italy, pp.358-379, 2014.
    A. Afshar, P. Mohassel, B. Pinkas, et al., "Non-interactive secure computation based on cut-and-choose", Advances in Cryptology-EUROCRYPT, Copenhagen, Denmark, pp.387-404, 2014.
    Y. Lindell and B. Riva, "Cut-and-choose Yao-based secure computation in the online/offline and batch settings", Advances in Cryptology-CRYPTO, Santa Barbara, CA, USA, pp.476-494, 2014.
    Y. Lindell and B. Riva, "Blazing fast 2PC in the offline/online setting with security for malicious adversaries", Proc. of the 22nd ACM-SIGSAC Conference on Computer and Communications Security, Denver, Colorado, USA, pp.579-590, 2015.
    A. Shelat and C.H. Shen, "Fast two-party secure computation with minimal assumptions", Proc. of the 20th ACM-SIGSAC Conference on Computer and Communications Security, Berlin, Germany, pp.523-534, 2013.
    P. Mohassel and B. Riva, "Garbled circuits checking garbled circuits:More efficient and secure two-party computation", Advances in Cryptology-CRYPTO 2013, Santa Barbara, CA, USA, pp.36-53, 2013.
    Y. Lindell and B. Pinkas, "A proof of security of Yao's protocol for two-party computation", Journal of Cryptology, Vol.22, No.2, pp.161-188, 2009.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (144) PDF downloads(440) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return