Strongly average-case secure obfuscation: achieving input privacy and circuit obscurity

摘要

A program obfuscator is a compiling algorithm that takes a program/circuit as input and generates a new garbled circuit to implement the same functionality as before while obtaining hard-to-understand in some sense, that is, infeasible to learn information from the garbled circuit. In order to obtain a practical application, an obfuscation should satisfy equivalent in functionality, polynomial slowdown in efficiency, and virtual black-box in security. In this paper, we model a stronger cryptographic obfuscation that does not only achieves the obfuscated circuit obscurity but also supports input re-key privacy. In order to implement the re-encryption obfuscation, we at first propose a key-privacy two-level encryption mechanism that implicitly supports the transformation from level-2 ciphertext into level-1 one, which provides an efficient method to re-encrypt the ciphertext without explicitly decryption procedure. Under the mechanism of two-level encryption and function of re-encryption, we construct an obfuscation of re-encryption that takes as input a probabilistic (keys) circuit and outputs a transformed circuit. We also give the proof that the obfuscator achieves the average-case security for the circuit family under the extended DBDH assumption and Decisional Linear assumption in the standard model. Copyright (c) 2016 John Wiley & Sons, Ltd.