We give several results about building obfuscation combiners, with matching upper and lower bounds for the precise quorum of secure candidates. Namely, we show that one can build 3-out-of-4 obfuscation combiners where at least three of the four combiners are secure, whereas 2-out-of-3 structural combiners (which combine the obfuscator candidates in a black-box sense) with only two secure candidates, are impossible. Our results generalize to (2c+1)-out-of-(3c+1) combiners for the positive result, and to 2c-out-of-3c results for the negative result, for any integer c.
To reduce overhead, we define detecting combiners, where the combined obfuscator may sometimes produce an error-indication instead of the desired output, indicating that some of the component obfuscators is faulty. We present a (c+1)-out-of-(2c+1) detecting combiner for any integer c, bypassing the previous lower bound. We further show that c-out-of-2c structural detecting combiners are again impossible.
Since our approach can be used for practical obfuscators, as well as for obfuscators proven secure (based on assumptions), we also briefly report on implementation results for some applied obfuscator programs.Category / Keywords: cryptographic protocols / Combiner, obfuscation, implementation Date: received 15 Mar 2016, last revised 18 Apr 2016 Contact author: marc fischlin at cryptoplexity de Available format(s): PDF | BibTeX Citation Note: Updated paragraph about concurrent work after discussions with the authors of related work. Version: 20160418:152045 (All versions of this report) Short URL: ia.cr/2016/289 Discussion forum: Show discussion | Start new discussion