Patent ID: 8631053

Claim:
A method for determining securely a Manhattan distance between a first signal and a second signal, comprising a first processor and a second processor for performing steps of the method such that the first signal is kept secret from the second processor, and the second signal is kept secret from the first processor, comprising the steps: mapping the first signal to a first binary signal; mapping the second signal to a second binary signal, such that a squared distance between the first binary signal and the second binary signals equals the Manhattan distance between the first signal and the second signal; reducing the first binary signal to a first low dimensional signal; reducing the second binary signal to a second low dimensional signal, wherein a squared distance between the first low dimensional signal and the second low dimensional signals approximates the squared distance between the first binary signal and the second binary signals; encrypting the first low dimensional signal and the second low dimensional signal with a key to produce a first encrypted low dimensional signal and a second encrypted low dimensional signal; and determining securely the squared distance between the first encrypted low dimensional signal and the second encrypted low dimensional signal to securely determine the Manhattan distance between the first signal and the second signal.