Perfect Indistinguishability Obfuscation for Boolean Polynomial Vector Spaces via Learning

Perfect Indistinguishability Obfuscation for Boolean Polynomial Vector Spaces via Learning

연구 분야: Analysis

학회: International Computing and Combinatorics Conference

Indistinguishability obfuscation (IO) is an extremely important primitive in cryptography and in this paper we are interested in perfect IO (while known constructions are mainly computational IO). At present only those functions with known deterministic unique representations or exactly learning methods have perfect IO, and besides this, there is no perfect IO for other functions. Thus we investigate whether we can construct perfect IO for functions that are not, or are unlikely to be, in the two kinds of functions above. Our target is vector spaces spanned by Boolean polynomials. Let be a set of arbitrary Boolean polynomials (not necessarily independent or distinct), the vector space spanned by . Currently there is no efficient way to exactly learn or compute deterministic unique representations for it even if F is given. Our result is that despite this, we can still construct a perfect indistinguishability obfuscator for which has the description of F as input. The mere cryptographic primitive used in our obfuscation is the somewhat homomorphic encryption scheme over the integers due to van Dijk et al. which only assumes the hardness of the Approximate GCD problem that is regarded solid so far. The most notable novelty in our techniques is a new positive application of the PAC Learning theory to IO, in which we show that the learning result of approximate correctness (for the Evaluation function homomorphically computing ) can be employed to achieve exact obfuscation for (note that given F, is approximately learnable but not exactly learnable). We remark that our result is for restricted function classes, unlike general computational IO sufficient for cryptographic applications. So we treat this result as a first step towards exploring the possibility of perfect IO beyond uniquely representable or exactly learnable.