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

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 ]