Fast Two-Output Secure Computation with Optimal Error Probability

ZHAO Chuan; JIANG Han; XU Qiuliang; WANG Yilei; WEI Xiaochao; CUI Shujie

doi:10.1049/cje.2016.06.025

Volume 26 Issue 5

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2017 > 26(5): 933-941

ZHAO Chuan, JIANG Han, XU Qiuliang, et al., “Fast Two-Output Secure Computation with Optimal Error Probability,” Chinese Journal of Electronics, vol. 26, no. 5, pp. 933-941, 2017, doi: 10.1049/cje.2016.06.025

Citation:

ZHAO Chuan, JIANG Han, XU Qiuliang, et al., “Fast Two-Output Secure Computation with Optimal Error Probability,” Chinese Journal of Electronics, vol. 26, no. 5, pp. 933-941, 2017, doi: 10.1049/cje.2016.06.025

Citation:

PDF( 278 KB)

Fast Two-Output Secure Computation with Optimal Error Probability

doi: 10.1049/cje.2016.06.025

1.
School of Computer Science and Technology, Shandong University, Jinan 250101, China;
2.
School of Information Science and Engineering, University of Jinan, Jinan 250022, China;
3.
School of Information and Electrical Engineering, Ludong University, Yantai 264025, China

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

Abstract

Abstract

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).
- Secure two-party computation,
- Yao's protocol,
- Malicious model,
- Cut-and-choose,
- Two-output function,
- Optimal error probability

FullText(HTML)

References(23)

References

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.

Relative Articles

Supplements(0)

Cited By

Proportional views