*01:17*[Pub][ePrint] Detection of Cheaters in Non-interactive Polynomial Evaluation, by Maki Yoshida and Satoshi Obana

In this paper, we consider both theoretical and practical aspects of

robust NI-PE (non-interactive polynomial evaluation with detection of

cheaters). First, we give a necessary condition of adversary structures for which perfectly robust NI-PE with small communication complexity exists. More precisely, we show that for any positive integers $n$, $m$ and $d>1$, an $n$-player access structure $U$, and an $n$-player adversary structure $T$, there exists a $U$-participating NI-PE scheme for $m$-variate polynomials over a finite field $F$ with $T$-private inputs such that (1) perfectly robust (i.e., successful cheating probability $\\epsilon=0$), (2) any polynomial of degree $d$ can be evaluated, and (3) the total size of shares of the output for some participating set is $o(m)\\times \\log |F|$, {\\em only if} $T$ is of type $Q_{d+1}$ for $U$, meaning that no $d+1$ sets in $T$ cover any set in $U$. Second, we give constructions of perfectly robust NI-PE schemes against threshold adversary and general adversary, respectively. All the proposed schemes ensure perfect robustness against $Q_{d+1}$ adversary, and computability of arbitrary polynomial of degree $d$. Third, we show that efficient robust NI-PE schemes against general adversary can be constructed by allowing cheaters very small chance of successful cheating. Namely, we construct two robust NI-PE schemes with $\\epsilon=1/|F|$ and the total size for shares of the output is only three times larger compared to the perfectly robust NI-PE scheme against threshold adversary.