3
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ I guess the question's addition and multiplication gates have two inputs in $\mathbb{Z}_q$, one output in $\mathbb{Z}_q$, and compute modulo $q$. [update: it's now clarified that the gates are slightly more general]. $\endgroup$
    – fgrieu
    Mar 2 '21 at 5:59
  • $\begingroup$ This question raised when I was trying to apply the idea at Section 4.2-4.3 of paper: iacr.org/archive/eurocrypt2014/84410298/84410298.pdf to the indicator function. Following the paper, addition gates have the form $g(x_1, \cdots, x_n)=a_1 x_1+\cdots+ a_n x_n$ and multiplication gates have the form $g(x_1, \cdots, x_n)=ax_1\cdots x_n$. In our case, $n$ can be $2$. $\endgroup$
    – Huy Le
    Mar 2 '21 at 6:12
  • 3
    $\begingroup$ Not sure what you are looking for, as you already found it. There is a unique polynomial of degree <q calculating the indicator function, so you cannot hope for better polynomials of degree <q. As you can represent all functions as linear combination of indicator functions (that's basically a function table), they necessarily have the highest (algebraic) degree = highest complexity. $\endgroup$
    – j.p.
    Mar 2 '21 at 7:22
  • $\begingroup$ This appears to be similar to the equality function. This definitely is non-trivial to compute with an arithmetic circuit. You might want to look into to the literature on secure comparison/equality testing if this is for an MPC-like setting. In fact there is a very recent paper on the topic eprint.iacr.org/2021/119 $\endgroup$
    – Guut Boy
    Mar 2 '21 at 9:01
  • $\begingroup$ Thanks alot @GuutBoy. I will take time to read the paper that you suggested! $\endgroup$
    – Huy Le
    Mar 3 '21 at 1:39
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much, Mark! $\endgroup$
    – Huy Le
    Mar 3 '21 at 1:41
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ It looks so interesting! I will check it out! Thank you @fgrieu! $\endgroup$
    – Huy Le
    Mar 3 '21 at 1:38
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.