Title: Secure Determining of the k-th Greatest Element Among Distributed Private Values
Abstract: One of the basic operations over distributed data is to find the k-th greatest value among union of these numerical data. The challenge arises when the datasets are private and their owners cannot trust any third party. In this paper, we propose a new secure protocol to find the k-th greatest value by means of secure summation sub-protocol. We compare our proposed protocol with other similar protocols. Specially, we will show that our scheme is more efficient than the well-known protocol of Aggarwal et.al. (2004) in terms of computation and communication complexity. Specifically, in the case of T <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> = 1 secret value for any party P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> our protocol has log m computation overhead and δ log m communication overhead for party P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> , where m and δ are the maximum acceptable value and communication overhead of the secure summation sub-protocol, respectively. The overheads of our protocol is exactly half of the overheads of Aggarwal's protocol.
Publication Year: 2021
Publication Date: 2021-03-03
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot