Paper 2019/276

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.