I am interested in reducing a circuit over sets of naturals (see here for some basic notions about this type of circuits) to a boolean circuit computing the same output. A very basic circuit of this type is a circuit $C_s$ defined over a beginning subset of $\mathbb{N}$ (i.e., $\{0,...,n\}$) containing only $\{\cap,\cup\}$ gates. My question is how efficiently can a boolean circuit $C_b$ be constructed that computes the same output as $C_s$ and whether there exists a lower bound on the size of such a $C_b$. The simplest way I can think of, in order to achieve the above, would be to represent a set $S$ by a binary array $\mathbf{s} = s_1,...,s_n$ of size $n$ where a 1 in position $i$ would signify that element $i \in S$. With this representation in mind, a union operation between sets $S,P$ can be implemented by $n$ OR gates by performing a point-wise OR for arrays $\mathbf{s}$ and $\mathbf{p}$. Likewise, intersection would be captured by point-wise AND. This approach would imply that $|C_b| \in O(n)$ and likewise for the reduction time (with a multiplicative factor of $|C_s|$).Can someone point out whether this approach is optimal or whether there is a better way to achieve the above? More importantly, is there a known lower bound for transformation of circuits over sets of naturals to boolean circuits? My research is security-motivated and the problem is governed by a security parameter $\lambda$ such that $n \in O(2^{\lambda})$ hence my approach is infeasible as it yields exponential size $C_b$. (EDIT: Assume each set $S$ is of size only $O(poly(\lambda)$)   
How efficiently can circuits over sets of naturals be transformed to boolean circuits?
cc.complexity theory;circuit complexity;arithmetic circuits