Paper 2022/1301

On the Invalidity of Lin16/Lin17 Obfuscation Schemes

Abstract

Indistinguishability obfuscation (IO) is at the frontier of cryptography research. Lin16/Lin17 obfuscation schemes are famous progresses towards simplifying obfuscation mechanism. Their basic structure can be described in the following way: to obfuscate a polynomial-time-computable Boolean function $$, first divide it into a group of component functions with low-degree and low-locality by using randomized encoding, and then hide the shapes of these component functions by using constant-degree multilinear maps (rather than polynomial degree ones). In this short paper we point out that Lin16/Lin17 schemes are invalid. More detailedly, they cannot achieve reusability, therefore they are not true IO schemes, but rather garbling schemes which are one-time schemes. Besides, this short paper presents more observations, to show that component functions cannot be overly simple.