Cryptology ePrint Archive: Report 2017/448

Obfuscation of Bloom Filter Queries from Ring-LWE

Alex Davidson

Abstract: We devise a virtual black-box (VBB) obfuscator for querying whether set elements are stored within Bloom filters, with security based on the Ring Learning With Errors (RLWE) problem and strongly universal hash functions. Our construction uses an abstracted encoding scheme that we instantiate using the Gentry, Gorbunov and Halevi (GGH15) multilinear map, with an explicit security reduction to RLWE. This represents an improvement on the functionality and security guarantees compared with the conjunction obfuscator introduced by Brakerski et al. (ITCS 2016), where security follows from a non-standard RLWE variant. Immediate applications of our work arise from any common usage of Bloom filters, such as efficient set intersection testing. Our obfuscated program allows this functionality to be executed in a non-interactive manner, whilst preventing the natural leakage that occurs when providing offline access to a Bloom filter. Compared to more general obfuscators for evasive functions, we demonstrate a significant asymptotic reduction in size and required computation for obfuscating set intersection queries. The obfuscator of Wichs and Zirdelis (EPRINT 2017) requires \(O(4^{n \log n})\) encodings for obfuscating circuits computing the intersection of sets of size \(n\), requiring the usage of additional primitives such as FHE to allow sets of polynomial size. Our construction requires only \(O(kn)\) total encodings and operations for evaluation, where \(k << n\). Moreover, the size of our obfuscator is independent of the size of the elements that are contained in the set. Our results, alongside recent and concurrent work, can be seen as another step forward in obfuscating wider classes of evasive functions using standard assumptions and models.

Category / Keywords: foundations / obfuscation, virtual black-box, Bloom filters, set intersection

Date: received 23 May 2017, last revised 2 Jun 2017, withdrawn 28 Feb 2018

Contact author: alex davidson 2014 at rhul ac uk

Available format(s): (-- withdrawn --)

Note: The parameters required for the proof of Lemma 4 to be valid are impossible to achieve for the construction.

Version: 20180228:071606 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]