SYSTEM AND METHOD FOR PAIRWISE DISTANCE COMPUTATION

[Technical Field]

[0001]

This invention relates generally to pairwise distance computation, and more particularly to computation of absolute distances between signals with or without privacy constraints.

[Background Art]

[0002]

Secure distance computation is performed when there are privacy constraints on one or both the signals. One way to solve this problem is to use encryption functions that allow computation in the ciphertext space. Such cryptosy stems are called homomorphic cryptosy stems. Many protocols based on homomorphic cryptosystems have been developed. Applications include secure computing, wherein a client processor can send encrypted data to a server. The server interacts with the client to solve a mathematical problem without revealing data to untrusted third parties. The protocols include, among other things, polynomial function computation primitives, which allow computation of Euclidean distance (L2 norm), L3 norm, correlation, etc. However, there are no efficient protocols for computing the absolute distance between pairs of signals under privacy constraints.

[0003]

Accordingly, there is a need for a method for determining an absolute distance between two signals such that this method is suitable for secure computation of such an absolute distance.

[Summary of Invention]

[0004]

The "distance" between two signals can serve as a measure of the similarity between the signals. One object of some embodiments of the invention is to provide a method for determining an absolute distance between two signals. Another object of some embodiments is to provide such a method that is suitable for secure computation of the absolute distances between signals.

[0005]

Some embodiments include converting the absolute distance computation into a k-norm distance computation, e.g., a polynomial distance computation. The embodiments allow reusing computation primitives originally constructed for determining polynomial distances (such as Euclidean distance) in the determination of the absolute distance.

[0006]

For example, some embodiments map the original signals to new signals such that a suitably selected polynomial distance function computed on pairs of the new mapped signals is approximately equal to the absolute distance between the underlying pairs of original input signals. This absolute distance preserving mapping expresses each scalar dimension of the input signal as a vector having length exactly equal to the cardinality of the scalar alphabet, and the values of the elements of the vector are selected according to the polynomial distance computation primitive that is available.

[0007]

For example, the absolute distance preserving mapping of an element of the signal includes determining a position N of the element in a vector of symbols of the finite alphabet arranged in an order, determining values for each of the first N elements or the last N elements of the vector as a fractional power of positive increments in the finite alphabet, wherein the fractional power is reciprocal of a positive; and determining values for subsequent elements of the vector as zero.

[0008]

Accordingly, one embodiment of the invention discloses a method for pairwise distance computation. The method includes transforming a first signal into a first mapped signal using an absolute distance preserving mapping; and transforming a second signal into a second mapped signal using the absolute distance preserving mapping, such that a k-norm distance between the first mapped signal and the second mapped signal represents an absolute distance between the first signal and the second signal. The elements of the first signal and the second signal are selected from a finite alphabet, wherein the absolute distance preserving mapping maps an element of a first or a second signal to a vector having a size equals to a cardinality of the finite alphabet. The steps of the method are performed by a processor.

[0009]

Another embodiment discloses a system including a sensor for determining a signal, wherein elements of the first signal are selected from a finite alphabet; a processor for transforming the signal into a mapped signal using an absolute distance preserving mapping, such that each element of the signal is mapped to a vector in the mapped signal, wherein a size of the vector equals to a cardinality of the finite alphabet; and a memory for storing the mapped signal.

[0010]

Yet another embodiment discloses a method for pairwise distance computation including steps for receiving a first signal representing an output of a sensor, wherein elements of the first signal are selected from a finite alphabet; transforming, using a processor, the first signal into a first mapped signal using an absolute distance preserving mapping, such that each element of the first signal is mapped to a vector in the first mapped signal, wherein a size of the vector equals to a cardinality of the finite alphabet; and storing the first mapped signal in a memory.

[001 1]

In various embodiments, the absolute distance preserving mapping includes determining a position N of the element in an ordered sequence of symbols of the finite alphabet; determining values for each of N elements of the vector as a fractional power 1/k of positive increments in the finite alphabet, wherein k is a positive number, and determining values for subsequent elements of the vector as zero.

[Brief Description of the Drawings]

[0012]

[Fig- 1]

Figure 1 is a schematic of an overview of processing signals using an absolute distance preserving mapping according to embodiments of the invention;

[Fig. 2]

Figure 2 is a block diagram of the absolute distance preserving mapping according to embodiments of the invention;

[Fig. 3A]

Figure 3A is a schematic of an example of absolute distance preserving mapping according to embodiments of the invention;

[Fig. 3B]

Figure 3B is a schematic of an example of absolute distance preserving mapping according to embodiments of the invention;

[Fig. 3C]

Figure 3C is a schematic of an example of absolute distance preserving mapping according to embodiments of the invention;

[Fig. 4]

Figure 4 is a block diagram of a method for determining the absolute distance preserving mapping according to embodiments of the invention; and [Fig. 5]

Figure 5 is a block diagram of a method for performing nearest neighbor search based on k-norm distance metric according to embodiments of the invention.

[Description of Embodiments]

[0013]

Figure 1 shows an overview of processing signals using an absolute distance preserving mapping of a signal 120. The signals can be an output of a sensor 110. Examples of the sensor 110 include a camera, e.g., an image or a depth camera, a biometric sensor, and an acoustic or light sensor. Examples of the signal 120 include intensities values or depth values of pixels in an image, or values of minutia in a fingerprint. In various embodiments, elements of the signal are selected from a finite alphabet. For example, the elements of the signal can be (8 bit) integers with values varying from 0 till 255. However, it should be understood that the method can be applied to other types of signals.

[0014]

Various embodiments of the invention map 140 the signal 120 into a mapped signal 150 that can be stored in a memory 160 or used for subsequent processing and/or distance computation. The mapping is an absolute distance preserving mapping than can be performed by a processor 130. The processor 130 can be operatively connected to the sensor 1 10 and/or the memory 160.

[0015]

The method can be performed in a processor connected to memory and input/output interfaces by buses as known in the art. The processor can be a client processor, a server processor, or a combination of client and server processors. For example, in a privacy preserving secure application, some of the steps are performed in the client and other steps are performed in a server in such a way that the signals or data and methodologies of either processor are revealed to the other processor. For example, the client is a low complexity, limited resource processor that generates the signals. The server can have unlimited resources and performs the mapping. Then, the results of the mapping can be stored in a memory or transferred back to the client to enable the client to assess a level of similarity (or dissimilarity) between the signals.

[0016]

Some embodiments of an invention are based on a realization that an absolute distance between a pair of signals is related to a value of an alternative distance function applied to a pair of mapped signals. For signals that are discrete and bounded, this relation is one of an exact equality. For signals that are bounded, but not necessarily discrete, this relation is one of an approximate equality, where the approximation results from discretization (quantization) of continuous values of the signal being processed.

[0017]

Figure 2 shows a block diagram of the absolute distance preserving mapping according to some embodiments. The elements 210 of the signal 120 have values selected from the finite alphabet 230. Each element, e.g., an element 220, of the signal 120 is mapped to a vector 225 in the mapped signal 150. A size of the vector 225 equals to a cardinality of the finite alphabet 230.

[0018]

Figure 3 A illustrates the mapping of the elements of the signal 120 to vectors of the mapped signal 150. For example, an element 310 is mapped to a vector 320. An element 315 is mapped to a vector 325. If the size of the signal n and the cardinality of the finite alphabet is m, then the size of the mapped signal is mn. In this example, m equals five, so the sizes of vectors

320 and 325 are five.

[0019]

In some embodiments of the invention, the absolute distance preserving mapping of an element 220 determines 240 a position N of the element in an ordered sequence of symbols of the finite alphabet 230. For example, the N elements of the vector can be the first N elements or the last N elements of the vector, and the ordered sequence of symbols of the finite alphabet can be arranged in an ascending or a descending order.

[0020]

Also, the absolute distance preserving mapping of an element 220 determines 250 values for each of the N elements of the vector as a fractional power 1/k of positive increments in the finite alphabet 230 wherein k 255 is a positive number, and determining 270 values for subsequent elements of the vector as zero.

[0021]

Figure 3B shows an example of the absolute distance preserving mapping / of an elements 330 s, having a value 3 selected from a finite alphabet with possible values 1 , 2, 3, 4, and 5. The value 3 has a third position in the finite alphabet, i.e., N = 3. The positive increments in the finite alphabet equal one, i.e., 2 - 1 = 1, 3 - 2 = 1 , 4 - 3 = 1 , and 5 - 4 = 1. Because the positive increments all are one, for any value of the power k , the first three element of the mapped vector 335 are one, and the other two values are zero.

[0022]

Figure 3C shows another example of the absolute distance preserving mapping/ of an elements 340 s,- having a value 1. In this case, N - 1 , so only the first element of the mapped vector 345 is one, the values of the other elements are zeroes.

[0023]

The concept underlying the mapping is that each scalar component of the signal is expressible in vector form, wherein the individual components of the vector depend on the relationship (≤, =,≥) between the scalar component of the signal and each possible value that the signal can take, where the possible value that the signal can take are ordered, e.g., from lowest to highest.

[0024]

For example, the finite alphabet set

X — {ai , 0,2 , <¾+l , . . . 5 am }

where

Cii < ( 2 < ... < CL% <
< . . . < Cim

[0025]

Assume without loss of generality that ^ If the original alphabet had some negative values, then some embodiments add an appropriate constant to all alphabet symbols such that all of the symbols of the alphabet are non-negative.

[0026]

Let the vector constructed from these ordered elements be denoted by

<¾ ( 1 ? . . . ^ (Ιγγ ^ §ome embodiments represent the absolute

distance between two vectors s ' t G Xn , in terms of a different

distance measure, e.g., the norm between two different vector valued

signals, S and " where the integer, k > 1 , and the norm is defined as:

ran

S t k — ^ \ Si t¾

i

[0027]

In the above expression, the vectors , S and t are related

(respectively) to the vectors s and t by the absolute distance preserving mapping.

[0028]

The absolute distance preserving mapping constructs a vector b of

length m using the m ordered elements of such that
ancj

¾— 1 ) for j = 1, 2, m . By construction, the values of the elements of b are all positive increments such that:

3

where 1 ≤ U < ΤΠ .

[0029]

Each possible value in the alphabet set is mapped with a

vector-valued function including m elements, where each individual element of this vector valued function is given by

b■' for j < i.

0 tor ι < j < m

[0030]

Thus, each element of is either a fractional power of positive

increments of elements in or has a zero value.

[0031]

Given the candidate vectors s and t above, some embodiments construct

the new vectors S and t whose elements are given by
and

^¾ ^ ) where the mapping function is as described above.

[0032]

Now, it is straightforward to verify that

mn n

II s ~ t ||fc
\si - t% \ = I) s - t || i

% i

[0033]

Thus, the absolute distance between s and t has been expressed as

/ -norm distance between S and t . If there exist computation primitives that

can accept as inputs S and "t , and work with the distance metric

S — t fc 7 , for k > 1 , is a finite real number, then these primitives can be used for distance-based computations on the vectors s and t . Furthermore, if

there exist mappings of S and t that preserve distance in the normed-metric space, then these mappings can be used to preserve the absolute distance between vectors s and t.

[0034]

Figure 4 shows a block diagram of a method for determining the absolute distance when a computation primitive is available for k-norm distances according to one embodiment of the invention. The method can be performed using a processor, such as the processor 130. Additionally or alternatively, at least part of the method can be performed by a processor of a pairwise distance computation unit 401 , which can be a different processor. The pairwise distance computation unit can be operatively connected to the memory 160.

[0035]

The method transforms 430 a first signal 410 into a first mapped signal 450 using the absolute distance preserving mapping and transforms 440 a second signal 420 into a second mapped signal 460 using the absolute distance preserving mapping. The elements of the first and the second signals are selected from the same finite alphabet.

[0036]

Next, the method determines 470 a k-norm distance between the first mapped signal and the second mapped signal to produce an absolute distance 480 between the first signal and the second signal. For example, the distances are Euclidean distances when k is two.

[0037]

The Euclidean distances between two signals can be determined using various methods, including methods that can be performed in a secure manner. Thus, some embodiments can determine the absolute distance between two signals, and also can determine such an absolute distance securely.

[0038]

Embodiments of the invention use different methods for determining securely the k-norm distance between the first mapped signal 450 and the second mapped signal 460. For example, one embodiment determines the squared Euclidian distance between the signals. This embodiment expresses the squared Euclidian distance function as a linear combination of homomorphic components to determine the squared distance based on homomorphic transformation, as described in the U.S. Publication No. 2010/0329448. The homomorphic component is an algebraic combination of the signal 450 and/or the signal 460, such that the encrypted result of the algebraic combination can be determined directly from encrypted versions of the signals using homomorphic properties.

[0039]

Figure 5 shows a block diagram of a method for performing nearest neighbor search based on the absolute distance metric, when a nearest neighbor primitive is available for a k-norm distance metric, according to one embodiment of the invention. The method can be performed using a processor, such as the processor 130. Additionally or alternatively, at least part of the method can be performed by a processor of a nearest neighbor computation unit 501 , which can be a different processor. The nearest neighbor computation unit can be operatively connected to the memory 160.

[0040]

A nearest neighbor search occurs between a query signal 510 and a database of signals 520 according to a distance metric. In a nearest neighbor search, the distance or an approximate distance between the signals in the database and the query signal is explicitly or implicitly computed. The output of this search can be the signal in the database with the smallest distance or approximate distance, a pointer to that signal in the database, or information pertaining to that signal, also stored in the database.

[0041]

This embodiment operates similarly to the embodiment in Figure 4, in transforming 530 a query signal 510 into a mapped query signal 550 using the absolute distance preserving mapping and transforming 540 a database of signals 520 into a database of mapped signals 560 by transforming each signal in the database of signals using the absolute distance preserving mapping. The elements of the query signal and of the signals in the database of signals are selected from the same finite alphabet.

[0042]

Next, the method uses a k-norm nearest neighbor primitive 570 to perform a k-norm nearest neighbor search of the mapped query signal and the database of mapped signals, which produces a nearest neighbor for the k-norm distance metric 580 between the mapped query signal and the database of mapped signals. The nearest neighbor for the k-norm distance metric of the mapped query signal in the database of mapped signals corresponds to the nearest neighbor for the absolute distance metric 590 of the query signal in the database of signals.

[0043]

In alternative embodiments, the k-norm nearest neighbor primitive may be replaced by an approximate k-norm near neighbor primitive, which selects one or more signals from the database of mapped signals which have small

distance with the mapped query signal, according to the k-norm distance metric, but not necessarily the nearest neighbor. Other similar search or comparison primitives using a k-norm distance metric can also be used in alternative embodiments.

[Claim 1]

A method for pairwise distance computation, comprising:

transforming a first signal into a first mapped signal using an absolute distance preserving mapping; and

transforming a second signal into a second mapped signal using the absolute distance preserving mapping, such that a k-norm distance between the first mapped signal and the second mapped signal represents an absolute distance between the first signal and the second signal, wherein elements of the first signal and the second signal are selected from a finite alphabet, wherein the absolute distance preserving mapping maps an element of a first or a second signal to a vector having a size equals to a cardinality of the finite alphabet, wherein steps of the method are performed by a processor, and wherein the absolute distance preserving mapping comprises:

determining a position N of the element in an ordered sequence of symbols of the finite alphabet;

determining values for each of N elements of the vector as a fractional power 1/k of positive increments in the finite alphabet, wherein k is a positive number, and

determining values for subsequent elements of the vector as zero.

[Claim 2]

The method of claim 1 , further comprising:

determining the k-norm distance between the first mapped signal and the second mapped signal to produce the absolute distance between the first signal and the second signal.

[Claim 3]

The method of claim 1 , wherein the k-norm distance is determined securely in an encrypted domain.

[Claim 4]

The method of claim 3, wherein the k-norm distance is a squared Euclidian distance determined as a linear combination of homomorphic components of the first mapped signal and the second mapped signal.

[Claim 5]

The method of claim 1 , wherein the N elements of the vector are the first N elements or the last N elements of the vector.

[Claim 6]

The method of claim 1 , wherein the first signal and the second signal are received from a sensor.

[Claim 7]

The method of claim 6, wherein the sensor is a camera and the first and the second signals include values of pixels in images acquired by the camera. [Claim 8]

The method of claim 1 , wherein the second signal is stored in a database of signals, further comprising:

transforming the signals in the database using the absolute distance preserving mapping to produce a database of mapped signals; and

querying the database of mapped signals using a k-norm distance with the first mapped signals to determine at least one nearest neighbor signal for a k-norm distance metric.

[Claim 9]

The method of claim 8, wherein the k-norm distance includes a k-norm distance nearest neighbor search.

[Claim 10]

The method of claim 8, wherein the k-norm distance includes a k-norm distance approximate near neighbor search.

[Claim 1 1]

The method of claim 8, wherein the database of signals includes information corresponding to each signal, further comprising

retrieving, from the database, the information corresponding to the nearest neighbor signal.

[Claim 12]

A system for pairwise distance computation, comprising:

a sensor for determining a signal, wherein elements of the first signal are selected from a finite alphabet;

a processor for transforming the signal into a mapped signal using an absolute distance preserving mapping, such that each element of the signal is mapped to a vector in the mapped signal, wherein a size of the vector equals to a cardinality of the finite alphabet, and wherein the absolute distance preserving mapping of an element comprises:

determining a position N of the element in an ordered sequence of symbols of the finite alphabet;

determining values for each of N elements of the vector as a fractional power 1/k of positive increments in the finite alphabet, wherein k is a positive number; and

determining values for subsequent elements of the vector as zero; and

a memory for storing the mapped signal.

[Claim 13]

The system of claim 12, wherein the memory stores a first mapped signal transformed from a first signal using the absolute distance preserving mapping and stores a second mapped signal transformed from a second signal using the absolute distance preserving mapping, further comprising:

a pairwise distance computation unit operatively connected to the memory for determining a k-norm distance between the first mapped signal and the second mapped signal to produce an absolute distance between the first signal and the second signal.

[Claim 14]

A method for pairwise distance computation, comprising:

receiving a first signal representing an output of a sensor, wherein elements of the first signal are selected from a finite alphabet;

transforming, using a processor, the first signal into a first mapped signal using an absolute distance preserving mapping, such that each element of the first signal is mapped to a vector in the first mapped signal, wherein a size of the vector equals to a cardinality of the finite alphabet, and wherein the absolute distance preserving mapping of an element comprises:

determining a position N of the element in an ordered sequence of symbols of the finite alphabet;

determining values for each of N elements of the vector as a fractional power 1/k of positive increments in the finite alphabet, wherein k is a positive number, and

determining values for subsequent elements of the vector as zero;

and

storing the first mapped signal in a memory.

[Claim 15]

The method of claim 14, further comprising:

transforming a second signal into a second mapped signal using the absolute distance preserving mapping; and

determining a k-norm distance between the first mapped signal and the second mapped signal to produce an absolute distance between the first signal and the second signal.

[Claim 16]

The method of claim 14, wherein the k-norm distance is determined securely in an encrypted domain.