**BOREALIS: Building Block for Sealed Bid Auctions on Blockchains**

*Erik-Oliver Blass and Florian Kerschbaum*

**Abstract: **We focus on securely computing the ranks of sealed integers
distributed among $n$ parties. For example, we securely compute the
largest or smallest integer, the median, or in general the
$k^{th}$-ranked integer. Such computations are a useful building
block to securely implement a variety of sealed-bid auctions. Our
objective is efficiency, specifically 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 BOREALIS, a
special-purpose protocol for secure computation of ranks among
integers. BOREALIS 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
cryptographic primitives, such as ECC Elgamal encryption, encrypted
comparisons, ciphertext blinding, secret sharing, and shuffling,
BOREALIS sets up systems of multi-scalar equations which we efficiently
prove with Groth-Sahai ZK proofs. Therewith, BOREALIS implements a
multi-party computation of pairwise comparisons and rank
zero-knowledge proofs secure against malicious adversaries. BOREALIS
completes in at most $4$ rounds which is constant in both bit length
$\ell$ of integers and the number of parties $n$. This is not only
asymptotically optimal, but surpasses generic constant-round secure
multi-party computation protocols, even those based on shared-key
fully homomorphic encryption. Furthermore, our implementation shows
that BOREALIS is very practical. Its 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 8 Sep 2020

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

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

**Version: **20200908:082050 (All versions of this report)

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

[ Cryptology ePrint archive ]