Florian
Kerschbaum
David
R.
Cheriton
School
of
Computer
Science
In this talk, I will focus on securely computing the kth-ranked integer in a sequence of integers distributed among n parties, e.g., the largest or smallest integer or the median. The 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 a special-purpose protocol for secure computation of the kth-ranked integer.
Our protocol 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 an encryption scheme (ECC Elgamal), encrypted comparisons, ciphertext blinding, secret sharing, and shuffling, our protocol sets up a system of multi-scalar equations which we efficiently prove with Groth-Sahai ZK proofs. As a result, our protocol is secure in the malicious model and practical, requiring only 3 rounds (blockchain blocks). This number of rounds is constant in both bit length l of integers and the number of parties n which is optimal. Our implementation indicates that the main bottleneck, ZK proof computations, is small in practice: even for a large number of n = 200 parties and high-precision integers (l = 32), computation time of all proofs is less than a single Bitcoin block interval.
Bio: Florian is an associate professor in the David R. Cheriton School of Computer Science at the University of Waterloo (since 2017) and executive director of the Waterloo Cybersecurity and Privacy Institute (since 2018). Before he worked as chief research expert at SAP in Karlsruhe (2005–2016) and as a software architect at Arxan Technologies in San Francisco (2002–2004).
He holds a Ph.D. in computer science from the Karlsruhe Institute of Technology (2010) and a master's degree from Purdue University (2001). He is interested in data security and privacy in data management, machine learning, and blockchains. He extends real-world systems with cryptographic security mechanisms to achieve (some) provable security guarantees. His work has been applied to products for databases, supply chain management and RFID tracking.