logo

SCIENTIA SINICA Informationis, Volume 51 , Issue 1 : 75(2021) https://doi.org/10.1360/SSI-2019-0226

Protocol for millionaires' problem in malicious models

More info
  • ReceivedSep 24, 2019
  • AcceptedNov 29, 2019
  • PublishedDec 22, 2020

Abstract


Funded by

国家自然科学基金(61272435)


References

[1] Goldreich O. Foundations of Cryptography-Volume 2: Basic Applications. London: Cambridge University Press, 2009. Google Scholar

[2] Yao A C. Protocols for secure computations. In: Proceedings of the 23rd Annual Symposium on Foundation of Computer Science, Chicago, 1982. 160--164. Google Scholar

[3] Ishai Y, Rijmen V. Advances in Cryptology-EUROCRYPT 2019. In: Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, 2019. 97--185, 351--406, 473--561. Google Scholar

[4] Goldwasser S. Multi party computations: past and present. In: Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, Santa Barbara. 1997. 1--6. Google Scholar

[5] Cramer R, Damgard I B. Secure Multiparty Computation. London: Cambridge University Press, 2015. Google Scholar

[6] Goldreich O, Micali S, Wigderson A. How to play any mental game. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, New York, 1987. 218--229. Google Scholar

[7] Kreuter B, Shelat A, Shen C H. Billion-gate secure computation with malicious adversaries. In: Proceedings of USENIX Security Symposium 2012, Bellevue, 2012. 285--300. Google Scholar

[8] Marszalek Z. Parallel fast sort algorithm for secure multiparty computation. J Univ Comput Sci, 2018, 24: 488--514. Google Scholar

[9] Freedman M J, Hazay C, Nissim K. Efficient Set Intersection with Simulation-Based Security. J Cryptol, 2016, 29: 115-155 CrossRef Google Scholar

[10] Kissner L, Song D. Privacy-preserving set operations. In: Proceedings of Annual International Cryptology Conference, Santa Barbara, 2005. 241--257. Google Scholar

[11] Agrawal R, Srikant R. Privacy-preserving data mining. SIGMOD Rec, 2000, 29: 439-450 CrossRef Google Scholar

[12] Li S, Mu N, Le J. Privacy preserving frequent itemset mining: Maximizing data utility based on database reconstruction. Comput Security, 2019, 84: 17-34 CrossRef Google Scholar

[13] Du W, Atallah M J. Privacy-preserving cooperative statistical analysis. In: Proceedings of the 17th Annual Computer Security Applications Conference, New Orleans, 2001. 102--110. Google Scholar

[14] Wang Z, Pang X, Chen Y. Privacy-Preserving Crowd-Sourced Statistical Data Publishing with An Untrusted Server. IEEE Trans Mobile Comput, 2019, 18: 1356-1367 CrossRef Google Scholar

[15] Atallah M J, Du W. Secure multi-party computational geometry. In: Proceedings of Workshop on Algorithms and Data Structures, Providence, 2001. 165--179. Google Scholar

[16] Chen L, Zhang W, Li S. Fully privacy-preserving determination of point-range relationship. Sci Sin-Inf, 2018, 48: 187-204 CrossRef Google Scholar

[17] Zhao C, Zhao S, Zhao M. Secure Multi-Party Computation: Theory, practice and applications. Inf Sci, 2019, 476: 357-372 CrossRef Google Scholar

[18] Choudhuri A R, Goyal V, Jain A. Founding secure computation on blockchains. In: Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, 2019. 351--380. Google Scholar

[19] Yao Z A, Tang C M, Shi G H. 排序问题的安全多方计算协议. Sci Sin-Inf, 2011, 41: 789-797 CrossRef Google Scholar

[20] Shelat A, Shen C H. Two-output secure computation with malicious adversaries. In: Proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, 2011. 386--405. Google Scholar

[21] Canetti R, Poburinnaya O, Venkitasubramaniam M. Equivocating yao: constant-round adaptively secure multiparty computation in the plain model. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, Montreal, 2017. 497--509. Google Scholar

[22] Lindell Y, Pinkas B. An efficient protocol for secure two-party computation in the presence of malicious adversaries. In: Proceedings of the 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, 2007. 52--78. Google Scholar

[23] Lindell Y. Fast Cut-and-Choose-Based Protocols for Malicious and Covert Adversaries. J Cryptol, 2016, 29: 456-490 CrossRef Google Scholar

[24] Ben D A, Nisan B, Pinkas B. FairplayMP: a system for secure multi-party computation. In: Proceedings of ACM Conference on Computer and Communications Security, Virginia, 2008. 257--266. Google Scholar

[25] Pinkas B, Schneider T, Smart N, et al. Secure two-party computation is practical. In: Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, 2009. 250--267. Google Scholar

[26] Peng K, Boyd C, Dawson E, et al. An Efficient and Verifiable Solution to the Millionaire Problem. In: Proceedings of International Conferecnec of Information Security and Cryptology, Seoul, 2004. 51--66. Google Scholar

[27] Garay J A, Schoenmakers B, Villegas J. Practical and Secure Solutions for Integer Comparison. In: Proceedings of International Conference on Theory and Practice of Public Key Cryptography, Harbin, 2007. 330--342. Google Scholar

[28] Damgard I, Geisler M, Kroigard M. Homomorphic encryption and secure comparison. IJACT, 2008, 1: 22 CrossRef Google Scholar

[29] Veugen T. Improving the DGK comparison protocol. In: Proceedings of IEEE International Workshop on Information Forensics and Security, Costa Adeje, 2012. 49--54. Google Scholar

[30] Paillier P. Public-key cryptosystems based on composite degree residuosity classes. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques, Prague, 1999. 223--238. Google Scholar

[31] Fouque P A, Poupard G, Stern J. Sharing decryption in the context of voting or lotteries. In: Proceedings of International Conference on Financial Cryptography, Anguilla, 2000. 90--104. Google Scholar

[32] Liu X, Choo K K R, Deng R H. Efficient and Privacy-Preserving Outsourced Calculation of Rational Numbers. IEEE Trans Depend Secure Comput, 2018, 15: 27-39 CrossRef Google Scholar

  • Table 1   Efficiency comparison of different protocols (the benchmark is modular exponentation)
    Protocol 2 Protocol of [26] Protocol of [27]Protocol of [29]
    $5m+12$ $L^2+12L+8k^2-4k-2$ $124L$ $\frac{1}{2}(L-1)L$(semi-honest)
    112 662 2480 190(semi-honest)