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 , and , an -player access structure , and an -player adversary structure , there exists a -participating NI-PE scheme for -variate polynomials over a finite field with -private inputs such that (1) perfectly robust (i.e., successful cheating probability ), (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.