You are looking at a specific version 20160418:152045 of this paper. See the latest version.

Paper 2016/289

Obfuscation Combiners

Marc Fischlin and Amir Herzberg and Hod Bin Noon and Haya Shulman

Abstract

Obfuscation is challenging; we currently have practical candidates with rather vague security guarantees on the one side, and theoretical constructions which have recently experienced jeopardizing attacks against the underlying cryptographic assumptions on the other side. This motivates us to study and present robust combiners for obfuscators, which integrate several candidate obfuscators into a single obfuscator which is secure as long as a quorum of the candidates is indeed secure. 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.

Note: Updated paragraph about concurrent work after discussions with the authors of related work.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Combinerobfuscationimplementation
Contact author(s)
marc fischlin @ cryptoplexity de
History
2016-04-18: revised
2016-03-17: received
See all versions
Short URL
https://ia.cr/2016/289
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.