The first instantiation of \(U_A\)  and \(U_{A^\perp }\)  was proposed in the same paper [1]}, which was based on multivariate polynomials. The idea is to “obfuscate” the subspace \(A\)  using a set of polynomials \(p_1, \dots , p_m \in \mathbb {F}_2[x_1, \dots , x_n]\) . More precisely, let \(I_{d, A}\)  be the set of polynomials of degree \(d\)  in \(\mathbb {F}_2[x_1, \dots , x_n]\)  that vanish on \(A\) . Then the polynomials \(p_i\)  are selected uniformly at random from \(I_{d, A}\) . For a large enough \(m\) , the polynomials \(p_1, \dots , p_m\)  uniquely determine \(A\)  with overwhelming probability. This means for all \(v \in A\)  we will have \(p_1(v) = \cdots = p_m(v) = 0\) , and for any \(v \notin A\)  we will have \(p_k(v) \ne 0\)  for at least one \(1 \le k \le m\)  with overwhelming probability. This is proved in the following lemma.
