Paper 2019/620
Obfuscated Fuzzy Hamming Distance and Conjunctions from Subset Product Problems
Steven D. Galbraith and Lukas Zobernig
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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Minor revision. TCC 2019
- Keywords
- Program ObfuscationHamming DistanceConjunctionsVBBInput Hiding
- Contact author(s)
-
lukas zobernig @ auckland ac nz
s galbraith @ auckland ac nz - History
- 2019-09-20: last of 2 revisions
- 2019-06-03: received
- See all versions
- Short URL
- https://ia.cr/2019/620
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/620,
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{https://eprint.iacr.org/2019/620}},
url = {https://eprint.iacr.org/2019/620}
}
