Paper 2013/032

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 ϵ=0), (2) any polynomial of degree can be evaluated, and (3) the total size of shares of the output for some participating set is , {\em only if} is of type for , meaning that no sets in cover any set in . 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 adversary, and computability of arbitrary polynomial of degree . 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 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Secret sharingnon-interactive polynomial evaluationcheating detection
Contact author(s)
maki-yos @ ist osaka-u ac jp
History
2013-01-29: received
Short URL
https://ia.cr/2013/032
License
Creative Commons Attribution
CC BY

BibTeX

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