Cryptology ePrint Archive: Report 2016/1070

Preventing CLT Attacks on Obfuscation with Linear Overhead

Rex Fernando and Peter M. R. Rasmussen and Amit Sahai

Abstract: 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.

Category / Keywords: foundations / Multilinear Maps, CLT13, Indistinguishability Obfuscation, Zeroizing Attacks

Date: received 15 Nov 2016, last revised 17 Mar 2017

Contact author: rasmussen at cs ucla edu

Available format(s): PDF | BibTeX Citation

Note: This is a significant revision with a a new construction that dramatically improves the efficiency of our defense along with a lower bound result. Additionally, most of the introduction and the main sections have been rewritten.

Version: 20170318:010511 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]