zbMATH — the first resource for mathematics

Secure computation of the $$k$$th-ranked element. (English) Zbl 1122.68422
Cachin, Christian (ed.) et al., Advances in cryptology – EUROCRYPT 2004. International conference on the theory and applications of cryptographic techniques, Interlaken, Switzerland, May 2–6, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21935-8/pbk). Lecture Notes in Computer Science 3027, 40-55 (2004).
Summary: Given two or more parties possessing large, confidential datasets, we consider the problem of securely computing the $$k$$th-ranked element of the union of the datasets, e.g. the median of the values in the datasets. We investigate protocols with sublinear computation and communication costs. In the two-party case, we show that the $$k$$th-ranked element can be computed in $$\log k$$ rounds, where the computation and communication costs of each round are $$O(\log M)$$, where $$\log M$$ is the number of bits needed to describe each element of the input data. The protocol can be made secure against a malicious adversary, and can hide the sizes of the original datasets. In the multi-party setting, we show that the $$k$$th-ranked element can be computed in log $$M$$ rounds, with $$O(s \log M)$$ overhead per round, where $$s$$ is the number of parties. The multi-party protocol can be used in the two-party case and can also be made secure against a malicious adversary.
For the entire collection see [Zbl 1051.94003].

MSC:
 68P25 Data encryption (aspects in computer science) 94A62 Authentication, digital signatures and secret sharing
Full Text: