How can I work out Hamming distance between two binary vectors securely? I would like to know how I can apply homomorphic techniques here.

  • 2
    $\begingroup$ I'm sure there are papers out there on this. What have you found and why isn't it sufficient? $\endgroup$ – mikeazo Mar 22 '16 at 14:02
  • $\begingroup$ Please define "secure". Do you want to outsource this task to an untrusted server and don't want him to learn the vectors or the weight? Do you want to protect against side-channel attacks? $\endgroup$ – SEJPM Mar 22 '16 at 15:09
  • $\begingroup$ Yes I want it to be outsourced to an untrusted server and want the vector to remain oblivious. $\endgroup$ – Y.V Mar 22 '16 at 16:05
  • 1
    $\begingroup$ If you keep your question vague, the answers will remain vague. Yes, there are protocols that enable a functionality that uses similar terms to the ones that you are using. Now, to obtain useful results, you need to explain what you know, what are your constraints and what you have tried. $\endgroup$ – Sergio Andrés Figueroa Santos Mar 22 '16 at 17:28
  • 3
    $\begingroup$ Have a look at this article "Homomorphic Computation of Edit Distance" by Cheon et.al eprint.iacr.org/2015/132.pdf, where authors show how to compute edit distance on encrypted data. Hamming weight is a particular case of edit distance and maybe you can improve their work for this situation. $\endgroup$ – guglielmo london Mar 24 '16 at 18:37

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.