CryptoDB
Obfuscated Fuzzy Hamming Distance and Conjunctions from Subset Product Problems
NOTE: imports for ToSC and TCHES are no longer functioning.
Authors: | |
---|---|
Download: | |
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. |
BibTeX
@article{tcc-2019-29968, title={Obfuscated Fuzzy Hamming Distance and Conjunctions from Subset Product Problems}, booktitle={Theory of Cryptography}, series={Lecture Notes in Computer Science}, publisher={Springer}, volume={11891}, pages={81-110}, doi={10.1007/978-3-030-36030-6_4}, author={Steven D. Galbraith and Lukas Zobernig}, year=2019 }