International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Obfuscated Fuzzy Hamming Distance and Conjunctions from Subset Product Problems

Steven D. Galbraith
Lukas Zobernig
DOI: 10.1007/978-3-030-36030-6_4
Search ePrint
Search Google
Abstract: 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.
  title={Obfuscated Fuzzy Hamming Distance and Conjunctions from Subset Product Problems},
  booktitle={Theory of Cryptography},
  series={Lecture Notes in Computer Science},
  author={Steven D. Galbraith and Lukas Zobernig},