**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.

**Category / Keywords: **public-key cryptography / Obfuscation, Big Subset, Small Superset, Conjunction

**Date: **received 23 Aug 2020, last revised 23 Aug 2020

**Contact author: **s galbraith at auckland ac nz,trey li@auckland ac nz

**Available format(s): **PDF | BibTeX Citation

**Version: **20200823:132853 (All versions of this report)

**Short URL: **ia.cr/2020/1018

[ Cryptology ePrint archive ]