**Detection of Cheaters in Non-interactive Polynomial Evaluation**

*Maki Yoshida and Satoshi Obana*

**Abstract: **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.

**Category / Keywords: **foundations / Secret sharing, non-interactive polynomial evaluation, cheating detection

**Date: **received 24 Jan 2013, last revised 25 Jan 2013

**Contact author: **maki-yos at ist osaka-u ac jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20130129:223255 (All versions of this report)

**Short URL: **ia.cr/2013/032

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]