**Secure Computation of the $k^\text{th}$-ranked Integer on Blockchains**

*Erik-Oliver Blass and Florian Kerschbaum*

**Abstract: **We focus on securely computing the $k^\text{th}$-ranked
integer in a sequence of integers distributed among $n$ parties, e.g.,
the largest or smallest integer or the median. Our specific objective
is low interactivity between parties to support blockchains or other
scenarios where multiple rounds are time-consuming. Hence, we dismiss
powerful, yet highly-interactive MPC frameworks and propose SCIB, a
special-purpose protocol for secure computation of the
$k^\text{th}$-ranked integer. SCIB uses additively homomorphic
encryption to implement core comparisons, but computes under distinct
keys, chosen by each party to optimize the number of rounds. By
carefully combining ECC Elgamal encryption, encrypted comparisons,
ciphertext blinding, secret sharing, and shuffling, SCIB sets up a
system of multi-scalar equations which we efficiently prove with
Groth-Sahai ZK proofs. SCIB targets slightly weaker security than the
ideal MPC functionality, but is therefore practical, requiring only 3
rounds (blockchain blocks). This number of rounds is constant in both
bit length $\ell$ of integers and the number of parties $n$ which is
optimal. Our implementation shows that SCIB's main bottleneck, ZK
proof computations, is small in practice: even for a large number of
parties ($n=200$) and high-precision integers ($\ell=32$), computation
time of all proofs is less than a single Bitcoin block interval.

**Category / Keywords: **cryptographic protocols / applications, secret sharing, zero knowledge

**Date: **received 11 Mar 2019, last revised 28 Apr 2019

**Contact author: **erik-oliver blass at airbus com

**Available format(s): **PDF | BibTeX Citation

**Version: **20190429:042723 (All versions of this report)

**Short URL: **ia.cr/2019/276

[ Cryptology ePrint archive ]