An arithmetic circuit for the indicator function?

Question

The indicator function (or characteristic function) is defined as $f_{t^*}:\mathbb{Z}_q\to \mathbb{Z}_q$ satisying that $f_{t^*}(t)=1$ if $t^*=t$ and $f_{t^*}(t)=0$, otherwise. (Here $t^*\in \mathbb{Z}_q$ is given to define the function.) I am dealing with transforming the function into an arithmetic circuit with addition gates and multiplication gates. I know that if $t^*, t\in \{0,1\}$ then we can use a single NAND gate (in Boolean Algebra) for this function. However, using arithmetic circuits, the transformation seems not to be trivial.

Could you please help me about this? Thank you very much!

Updated:

The (one-variable) indicator function (or characteristic function) is defined as $f_{t^*}:\mathbb{Z}_q\to \mathbb{Z}_q$ satisying that $f_{t^*}(t)=1$ if $t=t^*$ and $f_{t^*}(t)=0$, otherwise. (Here $t^*\in \mathbb{Z}_q$ is given to define the function.) More generally, in the case of multi-variable, we define $f_{t^*}:\mathbb{Z}_q^d\to \mathbb{Z}_q$, $f_{t^*}(t_1, \cdots, t_d)=1$ if $\exists t_i$ such that $t_i=t^*$ and $f_{t^*}(t_1, \cdots, t_d)=0$, otherwise.

I am finding polynomials that can be used to represent these functions. So far, I have found some for the one-variable case:

• Using Lagrange Interpolation: As $t, t^* \in \mathbb{Z}_q=\{0,1, \cdots, q-1 \}$ then such a polynomial should go through the points $(0,0), (1,0), $ $\cdots, $ $(t^*-1,0), (t^*, 1), $ $(t^*+1, 0),$ $ \cdots,$ $ (q-1,0)$. We can construct $f_{t^*}(t)=\frac{t(t-1)\cdots (t-t^*+1)(t-t^*-1)\cdots (t-q+1)}{t^*(t^*-1)\cdots (t^*-t^*+1)(t^*-t^*-1)\cdots (t^*-q+1)} (\bmod q)$ via the Lagrange Interpolation method. However, the polynomial has degree of $q-1$ and looks complicated to analyze.
• Using Fermat's Little Theorem: The Fermat's Little Theorem states that if $q$ is a prime number, then for any integer $a$ not divisible by $q$, the number $a^{q-1}=1 ~(\bmod q)$. Then we can construct $f_{t^*}(t)=1-(t-t^*)^{q-1}~ (\bmod q)$, if $q$ is prime. This polynomial looks simpler but may still be not helpful in case $q$ is a very big integer.

The question is that is there any more polynomials that are simpler than those above. This question raised when I was trying to apply the idea at Section 4.2-4.3 of paper: https://www.iacr.org/archive/eurocrypt2014/84410298/84410298.pdf to the indicator function.

Answer 1

Any degree $d$ polynomial (over a field) has at most $d$ roots (unless it is identically zero). As the indicator function has $q-1$ roots, one gets that it must have degre $\geq q-1$. There are generalizations of this to multivariate polynomials (the best known is Schwartz-Zippel). You could potentially try to generalize to non-fields, but one quickly runs into odd behavior --- say over $\mathbb{Z}/6\mathbb{Z}$ the linear function $f(x) = 3x$ has $\geq 1$ root. This is because it is "identically zero in a CRT component" though, but I do not know of the proper generalization to avoid issues such as this.

Answer 2

The gates thought in the question can be used to build any polynomial with coefficients and variable in $\mathbb Z_q$. When $q$ is prime, a polynomial $P(x)$ in $\mathbb Z_q$ of degree $k>0$ has at most $k$ roots, that is points $x$ in $\mathbb Z_q$ with $P(x)=0$. The function $f_{t^*}$ has $q-1$ roots and does not match any constant polynomial, hence we need a polynomial of degree at least $q-1$ to implement it.

The one polynomial of degree $q-1$ matching $f_{t^*}$ can be constructed as $$P(x)=\begin{cases} (q-1)\displaystyle\prod_{i\in\mathbb Z_q,\,i\ne t}(x+(q-i))&\text{ if }t\text{ is even}\\ \quad\quad\quad\,\displaystyle\prod_{i\in\mathbb Z_q,\,i\ne t}(x+(q-i))&\text{ if }t\text{ is odd} \end{cases}$$ which can be evaluated with $q-1$ two‑inputs addition gates [one less if $t$ is non-zero, since one of the $(q-i)$ is zero], and $q-1$ two‑inputs multiplication gates [one less if $t$ is odd].

I fail to prove the conjecture that this construction is minimal in term of gates.

Answer 3

It's a bad idea to apply the mentioned scheme to the indicator function of an element in $\mathbb{Z}_p$, as the noise will blow up.

The scheme in [BGG+14] applies to circuits such that for each 2-ary multiplication gate, there is one input wire such that its value is guaranteed to be small upon evaluation (the choice of this wire cannot depend on the particular input). For the point function implemented as $f_a(x)=1-(x-a)^{p-1}$ in the most obvious way, this pre-requistie does not hold. It's not clear to me whether there is an arithmetic circuit for this function with the required property.

A simple method to avoid this problem is to use Boolean circuits. Note that when applied with a point function (decrypt only if the input is $t^\ast$), ABE is just IBE, and there are dedicated IBE schemes from LWE.