Paper 2021/400 Original: eprint.iacr.org/2021/400 ↗

Size of IK00 Branching Program

Abstract

Branching program is an important component of indistinguishability obfuscation (IO) schemes, its size greatly influences the efficiencies of corresponding IO schemes. There are two major candidates of branching programs, Bar86 branching program and IK00 branching program. Bar86 branching program was shown to efficiently recognize NC$^1$ circuits. In specific, a Boolean circuit of depth $d$ can be recognized by a Bar86 branching program of length not larger than $4^d$ (Therefore of size not larger than $5^2 \times 4^d$). In this short paper we present similar result about IK00 branching program. We show that IK00 branching program efficiently recognizes NC$^1$ circuits, that is, a Boolean circuit of depth $d$ can be recognized by an IK00 branching program of size not larger than $(n+1) \times 4^d$, where $n$ is input length. Our result may be a negative evidence for IK00 branching program to efficiently recognize polynomial-time computable functions.