Paper 2020/1018
Small Superset and Big Subset Obfuscation
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 small enough superset (resp., big enough subset) of X. Our purpose is to protect X from being known when the function is evasive, 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 small superset functions (SSF) and big subset functions (BSF), respectively. In this paper, we obfuscate SSF and BSF in a very simple and efficient way. We prove both input-hiding security and virtual black-box (VBB) security 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. [4] (see Appendix A) and propose a new conjunction obfuscation based on SSF and BSF obfuscation (see Appendix B). The security of our conjunction obfuscation is from our new computational problem called the twin subset product problem.
Note: This is the full version of a paper published at ACISP 2021.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. ACISP
- DOI
- 10.1007/978-3-030-90567-5_4
- Keywords
- Obfuscation Small Superset Big Subset Conjunction Twin 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
BibTeX
@misc{cryptoeprint:2020/1018,
author = {Steven D. Galbraith and Trey Li},
title = {Small Superset and Big Subset Obfuscation},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/1018},
year = {2020},
doi = {10.1007/978-3-030-90567-5_4},
url = {https://eprint.iacr.org/2020/1018}
}
