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 \(\mathsf {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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Note that such a value h can be generated by a distributed coin flipping protocol that outputs a random value \(r \in \mathbb {Z}_p^*\), followed by computing \(h = r^{(p-1)/q}\) satisfying that \(h \ne 1\).
- 2.
If there exists an adversary who can break the DL assumption with non-negligible probability, then an algorithm can be designed that uses this adversary as a subroutine and breaks both DDH and t-SDH assumptions with non-negligible probability.
References
Bellare, M., Garay, J.A., Rabin, T.: Batch verification with applications to cryptography and checking. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998. LNCS, vol. 1380, pp. 170–191. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054320
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, pp. 62–73. ACM (1993)
Benaloh, J.C.: Secret sharing homomorphisms: keeping shares of a secret secret (extended abstract). In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 251–260. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_19
Boneh, D., Boyen, X.: Short signatures without random oracles and the SDH assumption in bilinear groups. J. Cryptol. 21(2), 149–177 (2008)
Boneh, D., Franklin, M.: Identity-based encryption from the Weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_13
Bultel, X., Das, M.L., Gajera, H., Gérault, D., Giraud, M., Lafourcade, P.: Verifiable private polynomial evaluation. In: Okamoto, T., Yu, Y., Au, M.H., Li, Y. (eds.) ProvSec 2017. LNCS, vol. 10592, pp. 487–506. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68637-0_29
Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM (JACM) 51(4), 557–594 (2004)
Canetti, R., Riva, B., Rothblum, G.N.: Two protocols for delegation of computation. In: Smith, A. (ed.) ICITS 2012. LNCS, vol. 7412, pp. 37–61. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32284-6_3
Choi, S.G., Katz, J., Kumaresan, R., Cid, C.: Multi-client non-interactive verifiable computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 499–518. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_28
Feldman, P.: A practical scheme for non-interactive verifiable secret sharing. In: 1987 28th Annual Symposium on Foundations of Computer Science, pp. 427–438. IEEE (1987)
Fiore, D., Gennaro, R.: Publicly verifiable delegation of large polynomials and matrix computations, with applications. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security, pp. 501–512. ACM (2012)
Gajera, H., Naik, S., Das, M.L.: On the security of “verifiable privacy-preserving monitoring for cloud-assisted mHealth systems”. In: Ray, I., Gaur, M.S., Conti, M., Sanghi, D., Kamakoti, V. (eds.) ICISS 2016. LNCS, vol. 10063, pp. 324–335. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-49806-5_17
Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: outsourcing computation to untrusted workers. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 465–482. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_25
Guo, L., Fang, Y., Li, M., Li, P.: Verifiable privacy-preserving monitoring for cloud-assisted mHealth systems. In: 2015 IEEE Conference on Computer Communications, INFOCOM, pp. 1026–1034. IEEE (2015)
Kate, A., Zaverucha, G.M., Goldberg, I.: Constant-size commitments to polynomials and their applications. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 177–194. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_11
Naor, M., Pinkas, B.: Oblivious transfer and polynomial evaluation. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 245–254. ACM (1999)
Papamanthou, C., Shi, E., Tamassia, R.: Signatures of correct computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 222–242. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_13
Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: 2013 IEEE Symposium on Security and Privacy, SP, pp. 238–252. IEEE (2013)
Parno, B., Raykova, M., Vaikuntanathan, V.: How to delegate and verify in public: verifiable computation from attribute-based encryption. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 422–439. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28914-9_24
Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_9
Acknowledgement
This work was partially supported by the National Natural Science Foundation of China (Grant No. 61572303, 61772326, 61672010, 61672398), and Natural Science Foundation of Hubei Province (Grant No. 2017CFB303, 2017CFA012). We are also grateful to the anonymous reviewers for their valuable comments on the paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendices
Appendix A – \(\mathsf {PolyCommit_{Ped}}\)
The \(\mathsf {PolyCommit_{Ped}}\) scheme [15] contains four algorithms (Setup, Init, Compute, Verif), and it works as follows:
-
Setup: This algorithm is operated by a trusted party. Given the security parameter \(\lambda \), it generates two cyclic groups G and \(G_T\) with prime order p such that there exists a symmetric bilinear pairing \(\hat{e}: G \times G \rightarrow G_T\). It also chooses two generators g and h of G such that \(\log _gh\) is unknown. Moreover, it selects \(\alpha {\mathop {\leftarrow }\limits ^{R}} \mathbb {Z}_p^*\) and sets \(\mathsf {params} = (G, G_T, p, \hat{e}, g, h, (g^{\alpha }, \ldots , g^{\alpha ^k}), (h^{\alpha }, \ldots , h^{\alpha ^k}))\).
-
Init: For the secret polynomial \(f(z) = a_0 + a_1z + \ldots + a_kz^k\), the service provider chooses a random polynomial \(f'(z) = b_0 + b_1z + \ldots + b_kz^k\) over \(\mathbb {Z}_p^*\) with degree k. It computes the commitment \(C = \prod _{i=0}^k (g^{\alpha ^i})^{a_i}(h^{\alpha ^i})^{b_i} = g^{f(\alpha )}h^{f'(\alpha )}\) and sets \(\mathsf {vk} = C\).
-
Compute: Once receiving the client’s input x. The third party computes \(y = f(x)\) and \(y' = f'(x)\). Moreover, it computes \(\phi (z) = \frac{f(z) - f(x)}{z - x} = \sum _{i=0}^k \delta _i z^i\) and \(\phi '(z) = \frac{f'(z) - f'(x)}{z - x} = \sum _{i=0}^k \sigma _i z^i\). It further computes \(w = \prod _{j=0}^k (g^{\alpha ^j})^{\delta _j}(h^{\alpha ^j})^{\sigma _j} = g^{\phi (\alpha )}h^{\phi '(\alpha )}\). It sets the proof as \(\pi = (x, y', w)\) and returns \((y, \pi )\) to the client.
-
Verif: The client verifies whether \(\hat{e}(C, g) = \hat{e}(w, g^{\alpha - x}) \hat{e}(g^{f(x)}h^{g'(x)}, g)\). If this equation holds, the client outputs 1, and outputs 0 otherwise.
Appendix B – Bultel’s PPE Scheme
The Bultel’s PPE scheme [6] also contains four algorithms (Setup, Init, Compute, Verif) as follows:
-
Setup: Given the security parameter \(\lambda \), the service provider generates a group G with prime order p and a generator g for the group. It chooses a hash function \(\mathsf {H}: \{0, 1\}^* \rightarrow \mathbb {Z}_p^*\), and it sets \(\mathsf {params} = (G, p, g, \mathsf {H})\). Note that the hash function is only used to generate non-interactive zero-knowledge proofs.
-
Init: For the secret polynomial \(f(z) = a_0 + a_1z + \ldots + a_kz^k\), the service provider picks \(\mathsf {sk} {\mathop {\leftarrow }\limits ^{R}} \mathbb {Z}_p^*\) and computes \(\mathsf {pk} = g^{\mathsf {sk}}\). For \(i = 0, 1, \ldots , k\), it picks \(r_i {\mathop {\leftarrow }\limits ^{R}} \mathbb {Z}_p^*\) and computes \(c_i = g^{r_i}\) and \(d_i = \mathsf {pk}^{r_i} g^{a_i}\). Note that \((c_i, d_i)\) is an ElGamal ciphertext encrypting the commitment \(g^{a_i}\). Finally, it sets \(\mathsf {vk} = (\{c_i, d_i\}_{0 \le i \le k}, \mathsf {pk})\).
-
Compute: Once receiving the client’s input x, the third party computes \(y = f(x)\). It also computes \(c = \prod _{i=0}^k (c_i)^{x^i} = \prod _{i=0}^k g^{r_i \cdot x^i} = g^{r(x)}\) and \(d = \prod _{i=0}^k (d_i)^{x^i} = (\prod _{i=0}^k h^{r_i \cdot x^i}) \cdot (\prod _{i=0}^k g^{a_i \cdot x^i}) = h^{r(x)}g^{f(x)}\) for some polynomial \(r(x) = \sum _{i=0}^k r_i \cdot x^i\). Moreover, it generates a non-interactive zero-knowledge proof \(\pi \) that (c, d) is an ElGamal ciphertext encrypting \(g^{f(x)}\). Finally, it return \((y, \pi )\) to the client.
-
Verif: Using params and vk, the client can also compute (c, d). Then, she can verify whether \(\pi \) is a valid non-interactive zero-knowledge proof such that (c, d) encrypts \(g^y\). If the verification satisfies, the client outputs 1, and outputs 0 otherwise.
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Xia, Z., Yang, B., Zhang, M., Mu, Y. (2018). An Efficient and Provably Secure Private Polynomial Evaluation Scheme. In: Su, C., Kikuchi, H. (eds) Information Security Practice and Experience. ISPEC 2018. Lecture Notes in Computer Science(), vol 11125. Springer, Cham. https://doi.org/10.1007/978-3-319-99807-7_38
Download citation
DOI: https://doi.org/10.1007/978-3-319-99807-7_38
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-99806-0
Online ISBN: 978-3-319-99807-7
eBook Packages: Computer ScienceComputer Science (R0)