Paper 2020/1018

Big Subset and Small Superset Obfuscation

Steven D. Galbraith and Trey Li

Abstract

We obfuscate the big subset and small superset functionalities in a very simple way. We prove both VBB and input-hiding in the standard model based on the subset product problems. Our security proofs are simple. Let n in N be the bit length, t in N be the threshold indicating big/small, x in {0,1}^n be the characteristic vector of a set, with its hamming weight |x| denoting the size of the set. Our obfuscation for x requires that ||x|-t| < n/2. Note that a random x has hamming weight approximately n/2, hence this condition is for free most of the time. Our obfuscation requires hamming distance evasiveness, which is stronger than big subset and small superset evasiveness. Though, this requirement already implies a fairly large family of functions to obfuscate. We also give a proof of input-hiding for the conjunction obfuscation by Bartusek et al. [5] (see Appendix A) and propose a new conjunction obfuscation based on the big subset and small superset obfuscation (see Appendix B). The security of our conjunction obfuscation is from our new assumption called the twin subset product problem.