  In this paper, we propose a practically efficient model for securely
computing rank-based statistics, e.g., median, percentiles and quartiles, over
distributed datasets in the malicious setting without leaking individual data
privacy. Based on the binary search technique of Aggarwal et al. (EUROCRYPT
\textquotesingle 04), we respectively present an interactive protocol and a
non-interactive protocol, involving at most $\log ||R||$ rounds, where $||R||$
is the range size of the dataset elements. Besides, we introduce a series of
optimisation techniques to reduce the round complexity. Our computing model is
modular and can be instantiated with either homomorphic encryption or
secret-sharing schemes. Compared to the state-of-the-art solutions, it provides
stronger security and privacy while maintaining high efficiency and accuracy.
Unlike differential-privacy-based solutions, it does not suffer a trade-off
between accuracy and privacy. On the other hand, it only involves $O(N \log
||R||)$ time complexity, which is far more efficient than those
bitwise-comparison-based solutions with $O(N^2\log ||R||)$ time complexity,
where $N$ is the dataset size. Finally, we provide a UC-secure instantiation
with the threshold Paillier cryptosystem and $\Sigma$-protocol zero-knowledge
proofs of knowledge.
