Conditionally accepted sampling: AB15 IO scheme with smaller deviation ratio

Indistinguishable Obfuscation (IO) is a very critical cryptography primitive. It can be used to construct almost any other cryptography schemes. AB15 indistinguishability obfuscation scheme is the first practical scheme. In order to avoid the ideal generator can be searched, authors of AB15 IO scheme set it to a relatively large size (In fact, such ideal generator should be a “small prime”). It causes the ratio of the standard deviation of Gaussian sampling and the size of ideal generator smaller. We call the ratio as “deviation ratio”. In this paper, we point that direct sampling and smaller deviation ratio makes the scheme insecure. A searching attack can reveal hidden coefficients of original boolean circuit from its obfuscator. Firstly, the attacker searches those level-0 encodings of 0, hoping that the code value is 0. Such event happens with probability [Formula: see text] or [Formula: see text], where [Formula: see text] as the deviation ratio. By a series of searching, a weak obfuscator with prime module can be obtained. Then, the attacker can obtain all hidden coefficients of original boolean circuit. Take n as the dimension of independent variable, m as the dimension of coefficient of original boolean circuit. For Simple Obfuscator, searching time is [Formula: see text], and the probability that one successfully reveals hidden coefficients of original boolean circuit is about [Formula: see text]. For Robust Obfuscator, searching time and success probability are respectively [Formula: see text] and [Formula: see text]. At last, we present a revised scheme with “conditionally accepted sampling” and smaller deviation ratio. The new scheme avoids above mentioned attack and greatly reduce the size complexity.