Rafail Ostrovsky - Publications

High–Precision Secure Computation of Satellite Collision Probabilities

Brett Hemenway, Steve Lu, Rafail Ostrovsky, William Welser IV


The cost of designing building, launching and maintaining satellites make satellite operators extremely motivated to protect their on–orbit assets. Unfortunately , privacy concerns present a serious barrier to coordination between different operators. One obstacle to improving safty arises because operators view the trajectories of their satellites as private, and refuse to share this private information with other operators. without data–sharing, preventing collision between satellites becomes a challenging task. A 2104 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 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 integrates the integer–based Goldreich–Micali–Wigderson (GMW) protocol and 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 withut 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 triple 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 buary 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.

comment: SCN2106 PP: 169–187

Fetch PDF file of the paper

Back to Publications List