Paper 2019/620

Obfuscated Fuzzy Hamming Distance and Conjunctions from Subset Product Problems

Steven D. Galbraith and Lukas Zobernig


We consider the problem of obfuscating programs for fuzzy matching (in other words, testing whether the Hamming distance between an $n$-bit input and a fixed $n$-bit target vector is smaller than some predetermined threshold). This problem arises in biometric matching and other contexts. We present a virtual-black-box (VBB) secure and input-hiding obfuscator for fuzzy matching for Hamming distance, based on certain natural number-theoretic computational assumptions. In contrast to schemes based on coding theory, our obfuscator is based on computational hardness rather than information-theoretic hardness, and can be implemented for a much wider range of parameters. The Hamming distance obfuscator can also be applied to obfuscation of matching under the $\ell_1$ norm on $\mathbb{Z}^n$. We also consider obfuscating conjunctions. Conjunctions are equivalent to pattern matching with wildcards, which can be reduced in some cases to fuzzy matching. Our approach does not cover as general a range of parameters as other solutions, but it is much more compact. We study the relation between our obfuscation schemes and other obfuscators and give some advantages of our solution.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. TCC 2019
Program ObfuscationHamming DistanceConjunctionsVBBInput Hiding
Contact author(s)
lukas zobernig @ auckland ac nz
s galbraith @ auckland ac nz
2019-09-20: last of 2 revisions
2019-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Steven D.  Galbraith and Lukas Zobernig},
      title = {Obfuscated Fuzzy Hamming Distance and Conjunctions from Subset Product Problems},
      howpublished = {Cryptology ePrint Archive, Paper 2019/620},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.