LI Shundong, GUO Yimin, ZHOU Sufang, DOU Jiawei, WANG Daoshun. Efficient Protocols for the General Millionaires' Problem[J]. Chinese Journal of Electronics, 2017, 26(4): 696-702. doi: 10.1049/cje.2017.06.014
Citation: LI Shundong, GUO Yimin, ZHOU Sufang, DOU Jiawei, WANG Daoshun. Efficient Protocols for the General Millionaires' Problem[J]. Chinese Journal of Electronics, 2017, 26(4): 696-702. doi: 10.1049/cje.2017.06.014

Efficient Protocols for the General Millionaires' Problem

doi: 10.1049/cje.2017.06.014
Funds:  This work is supported by National Natural Science Foundation of China (No.61272435, No.61373020).
  • Received Date: 2015-05-06
  • Rev Recd Date: 2015-11-07
  • Publish Date: 2017-07-10
  • Secure multiparty computation (SMC) is a research focusing in the international cryptographic community. The protocols used to address the millionaires' problem are the basic building blocks of most SMC protocols and their efficiency dominates that of many other SMC protocols. To the best of our knowledge, almost all protocols used to address the millionaires' problem are based on integers, which means that their applications are limited. In this study, we propose precise and efficient protocols for rational numbers based on additively homomorphic encryptions. One of our protocols is inspired by computational geometry and it reduces the millionaires' problem to computing the area of a triangle formed by three private points. This approach can determine whether the relationship between two private inputs is greater than, equal to or less than, and it has a much lower computational complexity compared with existing methods. We proved that these protocols are secure using simulation paradigm. Our approaches can be used in many SMC protocols that involve rational numbers and integers, and they can also be used directly to solve some secure multiparty computational geometry problem in rational number field.
  • loading
  • A.C. Yao, “Protocols for secure computations”, Proc. of the 23th IEEE Symposium on Foundations of Computer Science, Washington, USA, pp.160-164, 1982.
    O. Goldreich, S. Micali and A. Wigderson, “How to play any mental game”, Proc. of the Nineteenth Annual ACM Conference on Theory of Computing, New York, USA, pp.218-229, 1987.
    O. Goldreich, The Fundamental of Cryptography: Basic Applications, Cambridge University Press, London, UK, 2004.
    M. Fischlin, “A cost-effective pay-per-multiplication comparison method for millionaires”, Proc. of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA, London, UK, pp.457-471, 2001.
    S.D. Li, Y.Q. Dai and Q.Y. You, “Efficient solution to Yao's Millionaires' problem”, Acta Electronica Sinica, Vol.33, No.5, pp.769-773, 2005. (in Chinese)
    H.Y. Lin and W.G. Tzeng, “An efficient solution to the millionaires' problem based on homomorphic encryption”, Lecture Notes in Computer Science, pp.456-466, 2005.
    J. Garay, B. Schoenmakers and J. Villegas, “Practical and secure solutions for integer comparison”, Proc. of the 10th International Conference on Practice and Theory in Public-Key Cryptography, Heidelberg, Berlin, German, pp.330-342, 2007.
    S.D. Li and D.S. Wang, “Efficient secure multiparty computation based on homomorphic encryption”, Acta Electronica Sinica, Vol.41, No.4, pp.798-803, 2013. (in Chinese)
    S.D. Gordon, C. Hazay and J. Katz, “Complete fairness in secure two-party computation”, Journal of the ACM, Vol.58, No.6, pp.24, 2011.
    S.D. Li, D.S. Wang and Y.Q. Dai, “Symmetric cryptographic solution to Yao's millionaires' problem and an evaluation of secure multiparty computations”, Information Sciences, Vol.178, No.1, pp.244-255, 2008.
    C.M. Tang, G.H. Shi and Z.A. Yao, “Secure multi-party computation protocol for sequencing problem”, Science China Information Sciences, Vol.54, No.8, pp.1654-1662, 2011.
    H. Huang, X.Y. Li, Y. Sun, et al., “PPS: Privacy-preserving strategy proof social-efficient spectrum auction mechanisms”, IEEE Transactions on Parallel and Distributed Systems, Vol.26, No.5, pp.1393-1404, 2015.
    P.K. Fong and J.H. Weber-Jahnke, “Privacy preserving decision tree learning using unrealized data sets”, IEEE Transactions on Knowledge and Data Engineering, Vol.24, No.2, pp.353-364, 2012.
    S. Niksefat, B. Sadeghiyan, P. Mohassel, et al., “ZIDS: A privacy-preserving intrusion detection system using secure twoparty computation protocols”, Computer Journal, Vol.57, No.4, pp.494-509, 2014.
    Y. Wang, Z. Liu, H. Wang, et al., “Social rational secure multiparty computation”, Concurrency and Computation: Practice and Experience, Vol.26, No.5, pp.1067-1083, 2014.
    S.D. Li, C.Y. Wu, D.S. Wang, et al., “Secure multiparty computation of solid geometric problems and their applications”, Information Sciences, Vol.282, pp.401-413, 2014.
    S.D. Li, D.S. Wang and Y.Q. Dai, “Efficient secure multiparty computational geometry”, Chinese Journal of Electronics, Vol.19, No.2, pp.324-328, 2010.
    S. Bruce, Applied Cryptography, Protocols, Algorithm and Source Code in C, John Wiley & Sons, New York, USA, 2007.
    R.L. Rivest, L. Adleman and M.L. Dertouzos, “On data banks and privacy homomorphisms”, Foundations of Secure Computation, Vol.4, No.11, pp.169-180, 1978.
    P. Paillier, “Public-key cryptosystems based on composite degree residuosity classes”, Proc. of the 17th International Conference on Theory and Application of Cryptographic Techniques, Heidelberg, Berlin, German, pp.223-238, 1999.
  • 加载中


    通讯作者: 陈斌,
    • 1. 

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

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

    Article Metrics

    Article views (168) PDF downloads(681) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint