A Secure Multidimensional Point Inclusion Protocol

Signal processing in the encrypted domain combines typical signal processing operations and cryptographic primitives to ensure security in applications involving mutually distrusting participants. Several such applications reduce to a multi-dimensional point, inclusion problem where two participants decide whether a point known to the first lies inside a region specified by the second. In a secure solution, neither party gains knowledge about the other's input. For instance; in biometric authentication the client can prove his identity without disclosing his biometric. In this paper; we present a new primitive for securely solving the multidimensional point inclusion problem. Using this primitive, we first propose an efficient and provably secure protocol that solves the problem for art N-dimensional convex region bounded with hyperplanes. We subsequently extend the protocol to inclusion in multiple hyperellipsoidal regions. Considering possible reduction strategies such as input packing; we analyze the complexity of both protocols.