An Efficient and Provably Secure Private Polynomial Evaluation Scheme | SpringerLink
Skip to main content

An Efficient and Provably Secure Private Polynomial Evaluation Scheme

  • Conference paper
  • First Online:
Information Security Practice and Experience (ISPEC 2018)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 11125))

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 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. 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

  1. 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

    Chapter  Google Scholar 

  2. 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)

    Google Scholar 

  3. 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

    Chapter  Google Scholar 

  4. Boneh, D., Boyen, X.: Short signatures without random oracles and the SDH assumption in bilinear groups. J. Cryptol. 21(2), 149–177 (2008)

    Article  MathSciNet  Google Scholar 

  5. 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

    Chapter  Google Scholar 

  6. 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

    Chapter  Google Scholar 

  7. Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM (JACM) 51(4), 557–594 (2004)

    Article  MathSciNet  Google Scholar 

  8. 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

    Chapter  Google Scholar 

  9. 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

    Chapter  Google Scholar 

  10. 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)

    Google Scholar 

  11. 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)

    Google Scholar 

  12. 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

    Chapter  Google Scholar 

  13. 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

    Chapter  Google Scholar 

  14. 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)

    Google Scholar 

  15. 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

    Chapter  Google Scholar 

  16. 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)

    Google Scholar 

  17. 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

    Chapter  MATH  Google Scholar 

  18. 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)

    Google Scholar 

  19. 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

    Chapter  Google Scholar 

  20. 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

    Chapter  Google Scholar 

Download references

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

Authors

Corresponding author

Correspondence to Bo Yang .

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 (cd) 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 (cd). Then, she can verify whether \(\pi \) is a valid non-interactive zero-knowledge proof such that (cd) encrypts \(g^y\). If the verification satisfies, the client outputs 1, and outputs 0 otherwise.

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

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)

Publish with us

Policies and ethics