Paper 2020/1018
Big Subset and Small Superset Obfuscation
Steven D. Galbraith and Trey Li
Abstract
Let S = {1,...,n} be a set of integers and X be a subset of S. We study the boolean function f_X(Y) which outputs 1 if and only if Y is a big enough subset (resp. small enough superset) of X. Our purpose is to protect X from being known, yet allow evaluations of f_X on any input Y \subseteq S. The corresponding research area is called function obfuscation. The two kinds of functions are called big subset functions (BSF) and small superset functions (SSF) respectively. In this paper, we obfuscate BSF and SSF in a very simple and efficient way. We prove both virtual black-box (VBB) security and input-hiding security in the standard model based on the subset product problem. We also give a proof of input-hiding based on the discrete logarithm problem (DLP) for the conjunction obfuscation by Bartusek et al. [5] (see Appendix A) and propose a new conjunction obfuscation based on BSF and SSF obfuscation (see Appendix B). The security of our conjunction obfuscation is from our new computational problem called the Twin Subset Product Problem.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- ObfuscationBig SubsetSmall SupersetConjunctionTwin Subset Product Problem
- Contact author(s)
- s galbraith @ auckland ac nz,trey li @ auckland ac nz
- History
- 2022-10-27: last of 6 revisions
- 2020-08-23: received
- See all versions
- Short URL
- https://ia.cr/2020/1018
- License
-
CC BY