What does universal look like? What is the complexity(size/depth) of universal circuit I was reading a paper about attribute based encryption. The authors showed that ciphertext-policy ABE can be constructed from key-policy ABE using universal circuit. But the universal circuit should be in the circuit space supported by CP-ABE. So what is the complexity of universal circuits?
The state of the art in optimizing the efficiency of universal circuits is, to my knowledge, this paper. At a high level, a universal circuit to evaluate any size-$s$ circuit has size $O(s\cdot \log s)$ I guess the depth should be roughly similar ($O(s\cdot \log s)$), since a size-$s$ circuit can have depth-$s$ in the worst case, and we do not know of generic techniques to reduce the depth of a circuit while increasing its size by only a logarithmic factor.