Designing privacy-preserving interval operations based on homomorphic encryption and secret sharing techniques

This paper introduces two-party protocols for various operations on two integer intervals that are privacy-preserving in the semi-honest model. Specifically, this work proposes new protocols for determining whether two intervals overlap; computing the boundaries and size of the overlap; and selecting a random sub-interval within the overlap. The protocols are presented both for homomorphic encryption and for secret sharing as basic secure multi-party computation techniques. Moreover, this paper presents a comprehensive performance evaluation of the newly-developed protocols.