Welcome to the resource topic for 2021/400
Title:
Size of IK00 Branching Program
Authors: Yupu Hu, Xingting Dong, Baocang Wang
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.
ePrint: https://eprint.iacr.org/2021/400
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 .