Cryptology ePrint Archive: Report 2017/756

Verifiable Private Polynomial Evaluation

Xavier Bultel and Manik Lal Das and Hardik Gajera and David Gérault and Matthieu Giraud and Pascal Lafourcade

Abstract: Delegating the computation of a polynomial to a server in a verifiable way is challenging. An even more challenging problem is ensuring that this polynomial remains hidden to clients who are able to query such a server. In this paper, we formally define the notion of \emph{Private Polynomial Evaluation} (PPE). Our main contribution is to design a rigorous security model along with relations between the different security properties. We define \emph{polynomial protection} (PP), \emph{proof unforgeability} (UNF), and \emph{indistinguishability against chosen function attack} (INDCFA), which formalizes the resistance of a PPE against attackers trying to guess which polynomial is used among two polynomials of their choice. As a second contribution, we give a cryptanalysis of two PPE schemes of the literature. Finally, we design a PPE scheme called PIPE and we prove that it is PP-, UNF- and INDCFA-secure under the decisional Diffie-Hellman assumption in the random oracle model.

Category / Keywords: cryptographic protocols / verifiable computation, private polynomial, security models, cloud

Original Publication (with major differences): ProvSec 2017

Date: received 4 Aug 2017

Contact author: matthieu giraud at uca fr

Available format(s): PDF | BibTeX Citation

Version: 20170807:163800 (All versions of this report)

Short URL: ia.cr/2017/756