Open AccessEfficient Protocols for the General Millionaires' Problem
Author(s) -
Li Shundong,
Guo Yimin,
Zhou Sufang,
Dou Jiawei,
Wang Daoshun
Publication year - 2017
Publication title -
chinese journal of electronics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.267
H-Index - 25
eISSN - 2075-5597
pISSN - 1022-4653
DOI - 10.1049/cje.2017.06.014
Subject(s) - homomorphic encryption , computer science , computation , secure multi party computation , theoretical computer science , computational complexity theory , cryptography , cryptographic primitive , cryptographic protocol , field (mathematics) , communication complexity , protocol (science) , distributed computing , mathematics , algorithm , computer network , encryption , medicine , alternative medicine , pathology , pure mathematics
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.