Paper 2019/276

BOREALIS: Building Block for Sealed Bid Auctions on Blockchains

Erik-Oliver Blass and Florian Kerschbaum


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.

Available format(s)
Cryptographic protocols
Publication info
applicationssecret sharingzero knowledge
Contact author(s)
erik-oliver blass @ airbus com
2020-09-08: last of 5 revisions
2019-03-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Erik-Oliver Blass and Florian Kerschbaum},
      title = {BOREALIS: Building Block for Sealed Bid Auctions on Blockchains},
      howpublished = {Cryptology ePrint Archive, Paper 2019/276},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.