A 2014 report from the RAND Corporation proposed using cryptographic tools from the domain of secure Multiparty Computation (MPC) to allow satellite operators to calculate collision probabilities (conjunction analyses) without sharing private information about the trajectories of their satellites.
In this work, we report on the design and implementation of a powerful new MPC framework for high-precision arithmetic on real-valued variables in a two-party setting where, unlike previous works, there is no honest majority, and where the players are not assumed to be semi-honest. We show how to apply this new solution in the domain of securely computing conjunction analyses. Our solution extends existing protocols, in particular the integer-based Goldreich-Micali-Wigderson (GMW) protocol, whereby we use combine and optimize GMW with Garbled Circuits (GC). We prove security of our protocol in the two party, semi-honest setting, assuming only the existence of one-way functions and Oblivious Transfer (the OT-hybrid model). The protocol allows a pair of satellite operators to compute the probability that their satellites will collide without sharing their underlying private orbital information. Techniques developed in this paper would potentially have a wide impact on general secure numerical analysis computations. We also show how to strengthen our construction with standard arithmetic message-authentication-codes (MACs) to enforce honest behavior beyond the semi-honest setting.
Computing a conjunction analysis requires numerically estimating a complex double integral to a high degree of precision. The complexity of the calculation, and the possibility of numeric instability presents many challenges for MPC protocols which typically model calculations as simple (integer) arithmetic or binary circuits.
Our secure numerical integration routines are extremely stable and efficient, and our secure conjunction analysis protocol takes only a few minutes to run on a commodity laptop.Category / Keywords: implementation / Secure Computation, Numerical Analysis Date: received 20 Mar 2016 Contact author: stevelu8 at gmail com Available format(s): PDF | BibTeX Citation Version: 20160322:202413 (All versions of this report) Short URL: ia.cr/2016/319 Discussion forum: Show discussion | Start new discussion