[Resource Topic] 2016/1070: Preventing CLT Attacks on Obfuscation with Linear Overhead

Welcome to the resource topic for 2016/1070

Preventing CLT Attacks on Obfuscation with Linear Overhead

Authors: Rex Fernando, Peter M. R. Rasmussen, Amit Sahai


We describe a defense against zeroizing attacks on indistinguishability obfuscation (iO) over the CLT13 multilinear map construction that only causes an additive blowup in the size of the branching program. This defense even applies to the most recent extension of the attack by Coron et al. (ePrint 2016), under which a much larger class of branching programs is vulnerable. To accomplish this, we describe an attack model for the current attacks on iO over CLT13 by distilling an essential common component of all previous attacks. This leads to the notion of a function being input partionable, meaning that the bits of the function’s input can be partitioned into somewhat independent subsets. We find a way to thwart these attacks by requiring a “stamp” to be added to the input of every function. The stamp is a function of the original input and eliminates the possibility of finding the independent subsets of the input necessary for a zeroizing attack. We give three different constructions of such “stamping functions” and prove formally that they each prevent any input partition. We also give details on how to instantiate one of the three functions efficiently in order to secure any branching program against this type of attack. The technique presented alters any branching program obfuscated over CLT13 to be secure against zeroizing attacks with only an additive blowup of the size of the branching program that is linear in the input size and security parameter. We can also apply our defense to a recent extension of annihilation attacks by Chen et al. (EUROCRYPT 2017) on obfuscation over the GGH13 multilinear map construction.

ePrint: https://eprint.iacr.org/2016/1070

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .