Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Program Obfuscation, Hamming Distance, Conjunctions, VBB, Input Hiding

Original Publication (with minor differences): TCC 2019

Date: received 31 May 2019, last revised 20 Sep 2019

Contact author: lukas zobernig at auckland ac nz, s galbraith at auckland ac nz

Available format(s): PDF | BibTeX Citation

Version: 20190920:063111 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]