An efficient and provably secure private polynomial evaluation scheme

Authors

Zhe Xia, Wuhan University of TechnologyFollow
Bo Yang, Shaanxi Normal University
Mingwu Zhang, Hubei University of TechnologyFollow
Yi Mu, Fujian Normal UniversityFollow

RIS ID

130891

Publication Details

Xia, Z., Yang, B., Zhang, M. & Mu, Y. (2018). An efficient and provably secure private polynomial evaluation scheme. Lecture Notes in Computer Science, 11125 595-609. Tokyo, Japan Information Security Practice and Experience: 14th International Conference, ISPEC 2018

Abstract

Private Polynomial Evaluation (PPE) allows the service provider to outsource the computation of a polynomial to some third party (e.g. the Cloud) in a verifiable way. And meanwhile, the polynomial remains hidden to the clients who are able to query the service. In ProvSec 2017, Bultel et al. have presented the formal security definitions for PPE, including polynomial protection (PP), proof unforgeability (UNF) and indistinguishability against chosen function attack (IND-CFA). They have introduced a PPE scheme that satisfies all these properties, and they have also shown that a polynomial commitment scheme in Asiacrypt 2010, called PolyCommit_Ped, enjoys these properties as well. In this paper, we introduce another provably secure PPE scheme, which not only has computational advantages over these two existing ones, but also relies on a much weaker security assumption. Moreover, we further explore how our PPE scheme can be implemented in the distributed fashion, so that a number of third parties jointly respond to the query but none of them could learn the polynomial unless they all collude.