Can you think of any way to evaluate the similarity between two time series without revealing any information on the time series ?

More precisely, considering two time series $x$ and $y$ of length 130 each, is there a way to get the minimum distance (using DTW for example) without reveling x or y ?

Recent work has been done on this topic using Homomorphic encryption but it performs very poorly (around 10 seconds to build and compute the minimum path on a $10*10$ DTW matrix)

  • $\begingroup$ The meaning of "privacy preserving" isn't in your title, although your post's body makes me pretty sure that you mean the multi-party computation sense rather than the differential privacy sense. ​ ​ $\endgroup$ – user991 Nov 3 '16 at 2:23
  • $\begingroup$ Actually my case if a bit different from two-party computation. I have a non-trusted server that holds the two time series x and y in a hidden format (either encrypted or randomized or whatever). This server has to compute the minimum distance between x and y without knowing the clear values of x and y and returns only the clear or encrypted minimum distance. Does this make sense ? $\endgroup$ – thib.v Nov 3 '16 at 2:37
  • $\begingroup$ So then, it's definitely not the case that "Everything is in the title.". ​ How related can the encoding procedures be? ​ (For example, can the encoders have a shared secret?) ​ Is selection of a similarity metric part of the problem? ​ Does the evaluation of that need to be exact? ​ ​ ​ ​ $\endgroup$ – user991 Nov 3 '16 at 2:56
  • $\begingroup$ Yes sorry, it's true that privacy preserving is not very accurate. In fact, the time series x and y will be obtained from a trusted client. Then yes, the client can have an encoder to encode both time series. The similarity metric would be Squared Euclidean distance. $\endgroup$ – thib.v Nov 3 '16 at 3:06
  • 1
    $\begingroup$ Yes something like that. Except that, while they are dealing with vectors of 2400 bits representing Irises, I have to deal with time series vectors of length n. They just compare the template with the user's input and compare the result to a threshold. In my case, I have to align the two time series in order to have the minimum distance and then compare this distance to a threshold. This involves building a matrix of distances n². That is why homomorphic encryption is not an option for me. $\endgroup$ – thib.v Nov 3 '16 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.