Paper 2013/032

Detection of Cheaters in Non-interactive Polynomial Evaluation

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.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Secret sharingnon-interactive polynomial evaluationcheating detection
Contact author(s)
maki-yos @ ist osaka-u ac jp
2013-01-29: received
Short URL
Creative Commons Attribution


      author = {Maki Yoshida and Satoshi Obana},
      title = {Detection of Cheaters in Non-interactive Polynomial Evaluation},
      howpublished = {Cryptology ePrint Archive, Paper 2013/032},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.