Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Proof-of-Work Certificates that Can Be Efficiently Computed in the Cloud (Invited Talk)

  • Conference paper
  • First Online:
Computer Algebra in Scientific Computing (CASC 2018)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 11077))

Included in the following conference series:

  • 610 Accesses

Abstract

In an emerging computing paradigm, computational capabilities, from processing power to storage capacities, are offered to users over communication networks as a cloud-based service. There, demanding computations are outsourced in order to limit infrastructure costs.

The idea of verifiable computing is to associate a data structure, a proof-of-work certificate, to the result of the outsourced computation. This allows a verification algorithm to prove the validity of the result, faster than by recomputing it. We talk about a Prover (the server performing the computations) and a Verifier.

Goldwasser, Kalai and Rothblum gave in 2008 a generic method to verify any parallelizable computation, in almost linear time in the size of the, potentially structured, inputs and the result. However, the extra cost of the computations for the Prover (and therefore the extra cost to the customer), although only almost a constant factor of the overall work, is nonetheless prohibitive in practice.

Differently, we will here present problem-specific procedures in computer algebra, e.g. for exact linear algebra computations, that are Prover-optimal, that is that have much less financial overhead.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /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
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 54.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 69.99
Price excludes VAT (USA)
  • 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

References

  1. Aaronson, S., Wigderson, A.: Algebrization: a new barrier in complexity theory. ACM Trans. Comput. Theory 1(1), 2:1–2:54 (2009). https://doi.org/10.1145/1490270.1490272

    Article  MATH  Google Scholar 

  2. Ábrahám, E., et al.: \({\sf SC}^{\sf 2}\): satisfiability checking meets symbolic computation. In: Kohlhase, M., Johansson, M., Miller, B., de de Moura, L., Tompa, F. (eds.) CICM 2016. LNCS (LNAI), vol. 9791, pp. 28–43. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-42547-4_3. https://members.loria.fr/PFontaine/Abraham1.pdf

    Chapter  Google Scholar 

  3. Arora, S., Safra, S.: Probabilistic checking of proofs; a new characterization of NP. In: 33rd Annual Symposium on Foundations of Computer Science, 24–27 October 1992, pp. 2–13. IEEE, Pittsburgh (1992)

    Google Scholar 

  4. Arreche, C. (ed.): ISSAC 2018, Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, New York, USA. ACM Press, New York, July 2018

    Google Scholar 

  5. Babai, L.: Trading group theory for randomness. In: Sedgewick [54], pp. 421–429. https://doi.org/10.1145/22145.22192

  6. Babai, L., Fortnow, L., Lund, C.: Nondeterministic exponential time has two-prover interactive protocols. In: Proceedings of the 31st Annual Symposium on Foundations of Computer Science, vol. 1, pp. 16–25, October 1990. https://doi.org/10.1109/FSCS.1990.89520

  7. Bangerter, E., Camenisch, J., Maurer, U.: Efficient proofs of knowledge of discrete logarithms and representations in groups with hidden order. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 154–171. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30580-4_11

    Chapter  Google Scholar 

  8. Beame, P.W., Cook, S.A., Hoover, H.J.: Log depth circuits for division and related problems. SIAM J. Comput. 15, 994–1003 (1986). https://doi.org/10.1137/0215070

    Article  MathSciNet  MATH  Google Scholar 

  9. Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Ashby, V. (ed.) Proceedings of the 1st ACM Conference on Computer and Communications Security, pp. 62–73. ACM Press, Fairfax, November 1993. http://www-cse.ucsd.edu/users/mihir/papers/ro.pdf

  10. Ben-Sasson, E., et al.: Computational integrity with a public random string from quasi-linear PCPs. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part III. LNCS, vol. 10212, pp. 551–579. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_19

    Chapter  Google Scholar 

  11. Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, Report 2018/046 (2018). https://eprint.iacr.org/2018/046

  12. Blum, M., Kannan, S.: Designing programs that check their work. J. ACM 42(1), 269–291 (1995). http://www.icsi.berkeley.edu/pubs/techreports/tr-88-009.pdf

    Article  Google Scholar 

  13. Bootle, J., Cerulli, A., Chaidos, P., Groth, J., Petit, C.: Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part II. LNCS, vol. 9666, pp. 327–357. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_12

    Chapter  MATH  Google Scholar 

  14. Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: 2018 IEEE Symposium on Security and Privacy (SP), pp. 319–338 (2018). https://doi.org/10.1109/SP.2018.00020

  15. Calude, C.S., Thompson, D.: Incompleteness, undecidability and automated proofs. In: Gerdt, V.P., Koepf, W., Seiler, W.M., Vorozhtsov, E.V. (eds.) CASC 2016. LNCS, vol. 9890, pp. 134–155. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45641-6_10

    Chapter  Google Scholar 

  16. Chyzak, F., Mahboubi, A., Sibut-Pinote, T., Tassi, E.: A computer-algebra-based formal proof of the irrationality of \(\zeta \)(3). In: ITP - 5th International Conference on Interactive Theorem Proving, Vienna, Austria (2014). https://hal.inria.fr/hal-00984057

  17. Cramer, R., Damgård, I., Nielsen, J.B.: Multiparty computation from threshold homomorphic encryption. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 280–300. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_18

    Chapter  Google Scholar 

  18. DeMillo, R.A., Lipton, R.J.: A probabilistic remark on algebraic program testing. Inf. Proces. Lett. 7(4), 193–195 (1978). https://doi.org/10.1016/0020-0190(78)90067-4

    Article  MATH  Google Scholar 

  19. Dumas, J.G., Giorgi, P., Elbaz-Vincent, P., Urbańska, A.: Parallel computation of the rank of large sparse matrices from algebraic k-theory. In: Moreno-Maza, M., Watt, S. (eds.) PASCO 2007, Proceedings of the 3rd ACM International Workshop on Parallel Symbolic Computation, pp. 43–52. Waterloo University, Ontario, July 2007. http://hal.archives-ouvertes.fr/hal-00142141

  20. Dumas, J.G., Kaltofen, E.: Essentially optimal interactive certificates in linear algebra. In: Nabeshima [46], pp. 146–153. https://doi.org/10.1145/2608628.2608644, http://hal.archives-ouvertes.fr/hal-00932846

  21. Dumas, J.G., Kaltofen, E., Thomé, E.: Interactive certificate for the verification of Wiedemann’s Krylov sequence: application to the certification of the determinant, the minimal and the characteristic polynomials of sparse matrices. Technical report, IMAG-hal-01171249 arXiv cs.SC/1507.01083, January 2016. http://hal.archives-ouvertes.fr/hal-01171249

  22. Dumas, J.G., Kaltofen, E., Thomé, E., Villard, G.: Linear time interactive certificates for the minimal polynomial and the determinant of a sparse matrix. In: Gao [34], pp. 199–206. https://doi.org/10.1145/2930889.2930908, http://hal.archives-ouvertes.fr/hal-01266041

  23. Dumas, J.G., Kaltofen, E., Villard, G., Zhi, L.: Polynomial time interactive proofs for linear algebra with exponential matrix dimensions and scalars given by polynomial time circuits. In: Safey El Din [52], pp. 125–132. https://doi.org/10.1145/3087604.3087640, http://ljk.imag.fr/membres/Jean-Guillaume.Dumas/Publications/DKVZ17.pdf

  24. Dumas, J.G., Lucas, D., Pernet, C.: Certificates for triangular equivalence and rank profiles. In: Safey El Din [52], pp. 133–140. https://doi.org/10.1145/3087604.3087609, http://hal.archives-ouvertes.fr/hal-01466093

  25. Dumas, J.-G., Zucca, V.: Prover efficient public verification of dense or sparse/structured matrix-vector multiplication. In: Pieprzyk, J., Suriadi, S. (eds.) ACISP 2017. LNCS, vol. 10343, pp. 115–134. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59870-3_7. http://hal.archives-ouvertes.fr/hal-01503870

    Chapter  Google Scholar 

  26. Eberly, W.: A new interactive certificate for matrix rank. Technical report 2015–1078-11, University of Calgary, June 2015. http://prism.ucalgary.ca/bitstream/1880/50543/1/2015-1078-11.pdf

  27. Eberly, W.: Selecting algorithms for black box matrices: checking for matrix properties that can simplify computations. In: Gao [34]

    Google Scholar 

  28. Elkhiyaoui, K., Önen, M., Azraoui, M., Molva, R.: Efficient techniques for publicly verifiable delegation of computation. In: Proceedings of the 11th ACM on Asia Conference on Computer and Communications Security, ASIA CCS 2016, pp. 119–128. ACM, New York (2016). https://doi.org/10.1145/2897845.2897910

  29. Fiat, A., Shamir, A.: How To Prove Yourself: Practical Solutions to Identification and Signature Problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12. http://www.cs.rit.edu/~jjk8346/FiatShamir.pdf

  30. Fiore, D., Fournet, C., Ghosh, E., Kohlweiss, M., Ohrimenko, O., Parno, B.: Hash first, argue later: adaptive verifiable computations on outsourced data. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, 24–28 October 2016, pp. 1304–1316. ACM (2016). http://doi.acm.org/10.1145/2976749.2978368

  31. 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, CCS 2012, pp. 501–512. ACM, New York (2012). https://doi.org/10.1145/2382196.2382250

  32. Freivalds, R.: Fast probabilistic algorithms. In: Bečvář, J. (ed.) MFCS 1979. LNCS, vol. 74, pp. 57–69. Springer, Heidelberg (1979). https://doi.org/10.1007/3-540-09526-8_5

    Chapter  Google Scholar 

  33. Furer, M., Goldreich, O., Mansour, Y., Sipser, M., Zachos, S.: On completeness and soundness in interactive proof systems. In: Micali, S. (ed.) Randomness and Computation. Advances in Computing Research, vol. 5, pp. 429–442. JAI Press, Greenwich (1989). http://www.wisdom.weizmann.ac.il/~oded/PS/fgmsz.ps

  34. Gao, X.S. (ed.): ISSAC 2016, Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation, Waterloo, Canada. ACM Press, New York, July 2016

    Google Scholar 

  35. Gąsieniec, L., Levcopoulos, C., Lingas, A., Pagh, R., Tokuyama, T.: Efficiently correcting matrix products. Algorithmica 79, 1–16 (2016). https://doi.org/10.1007/s00453-016-0202-3

    Article  MathSciNet  MATH  Google Scholar 

  36. Gentry, C., Groth, J., Ishai, Y., Peikert, C., Sahai, A., Smith, A.: Using fully homomorphic hybrid encryption to minimize non-interative zero-knowledge proofs. J. Cryptol. 28, 1–24 (2014). https://doi.org/10.1007/s00145-014-9184-y

    Article  MathSciNet  MATH  Google Scholar 

  37. Giorgi, P., Neiger, V.: Certification of minimal approximant bases. In: Arreche [4]

    Google Scholar 

  38. Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: Dwork, C. (ed.) STOC 2008, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, pp. 113–122. ACM Press, May 2008. https://doi.org/10.1145/1374376.1374396, http://research.microsoft.com/en-us/um/people/yael/publications/2008-delegatingcomputation.pdf

  39. Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems. In: Sedgewick [54], pp. 291–304. https://doi.org/10.1145/22145.22178

  40. Kaltofen, E., Trager, B.: Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators. J. Symb. Comput. 9(3), 301–320 (1990). http://www.math.ncsu.edu/~kaltofen/bibliography/90/KaTr90.pdf

  41. Kaltofen, E.: Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems. Math. Comput. 64(210), 777–806 (1995). https://doi.org/10.2307/2153451

    Article  MathSciNet  MATH  Google Scholar 

  42. Kaltofen, E., Pernet, C.: Sparse polynomial interpolation codes and their decoding beyond half the minimum distance. In: Nabeshima [46]. http://arxiv.org/abs/1403.3594

  43. Kaltofen, E.L., Nehring, M., Saunders, B.D.: Quadratic-time certificates in linear algebra. In: Leykin, A. (ed.) ISSAC 2011, Proceedings of the 2011 ACM International Symposium on Symbolic and Algebraic Computation, San Jose, California, USA, pp. 171–176. ACM Press, New York, June 2011. http://www.math.ncsu.edu/~kaltofen/bibliography/11/KNS11.pdf

  44. Kimbrel, T., Sinha, R.K.: A probabilistic algorithm for verifying matrix products using \(O(n^2)\) time and \(\log _2 n + O(1)\) random bits. Inf. Proces. Lett. 45(2), 107–110 (1993). ftp://trout.cs.washington.edu/tr/1991/08/UW-CSE-91-08-06.pdf

  45. Lund, C., Fortnow, L., Karloff, H., Nisan, N.: Algebraic methods for interactive proof systems. J. ACM 39(4), 859–868 (1992). https://doi.org/10.1145/146585.146605

    Article  MATH  Google Scholar 

  46. Nabeshima, K. (ed.): ISSAC 2014, Proceedings of the 2014 ACM International Symposium on Symbolic and Algebraic Computation, Kobe, Japan. ACM Press, New York, Jul 2014

    Google Scholar 

  47. Ng, E.W. (ed.): Symbolic and Algebraic Computation. LNCS, vol. 72. Springer, Heidelberg (1979). https://doi.org/10.1007/3-540-09519-5

    Book  MATH  Google Scholar 

  48. Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: Proceedings of the 2013 IEEE Symposium on Security and Privacy, SP 2013, pp. 238–252. IEEE Computer Society, Washington, DC (2013). https://doi.org/10.1109/SP.2013.47

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

  50. Reingold, O., Rothblum, G.N., Rothblum, R.D.: Constant-round interactive proofs for delegating computation. In: Wichs, D., Mansour, Y. (eds.) Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, 18–21 June 2016, pp. 49–62. ACM (2016). https://doi.org/10.1145/2897518.2897652, http://dl.acm.org/citation.cfm?id=2897518

  51. Roche, D.: Error correction in fast matrix multiplication and inverse. In: Arreche [4]

    Google Scholar 

  52. Safey El Din, M. (ed.): ISSAC 2017, Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation, Kaiserslautern, Deutschland. ACM Press, New York, July 2017

    Google Scholar 

  53. Schwartz, J.T.: Probabilistic algorithms for verification of polynomial identities. In: Ng [47], pp. 200–215. https://doi.org/10.1007/3-540-09519-5_72

  54. Sedgewick, R. (ed.): STOC 1985, ACM Symposium on Theory of Computing, Providence, Rhode Island, USA. ACM Press, New York, May 1985

    Google Scholar 

  55. Shamir, A.: IP = PSPACE. J. ACM 39(4), 869–877 (1992). https://doi.org/10.1145/146585.146609

    Article  MathSciNet  Google Scholar 

  56. Storjohann, A.: Integer matrix rank certification. In: May, J.P. (ed.) ISSAC 2009, Proceedings of the 2009 ACM International Symposium on Symbolic and Algebraic Computation, Seoul, Korea, pp. 333–340. ACM Press, New York, Jul 2009. https://cs.uwaterloo.ca/~astorjoh/issac09.pdf

  57. Thaler, J.: Time-optimal interactive proofs for circuit evaluation. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 71–89. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_5

    Chapter  Google Scholar 

  58. Walfish, M., Blumberg, A.J.: Verifying computations without reexecuting them. Commun. ACM 58(2), 74–84 (2015). https://doi.org/10.1145/2641562

    Article  Google Scholar 

  59. Wiedemann, D.H.: Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theory 32(1), 54–62 (1986). https://doi.org/10.1109/TIT.1986.1057137

    Article  MathSciNet  MATH  Google Scholar 

  60. Zhang, Y., Blanton, M.: Efficient secure and verifiable outsourcing of matrix multiplications. In: Chow, S.S.M., Camenisch, J., Hui, L.C.K., Yiu, S.M. (eds.) ISC 2014. LNCS, vol. 8783, pp. 158–178. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13257-0_10

    Chapter  Google Scholar 

  61. Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng [47], pp. 216–226. https://doi.org/10.1007/3-540-09519-5_73

Download references

Acknowledgment

I thank Brice Boyer, Pascal Lafourcade, Shafi Goldwasser, Erich Kaltofen, Julio López Fenner, David Lucas, Vincent Neiger, Jean-Baptiste Orfila, Clément Pernet, Maxime Puys, Jean-Louis Roch, Dan Roche, Guy Rothblum, Justin Thaler, Emmanuel Thomé, Gilles Villard, Lihong Zhi and an anonymous referee for their helpful comments.

Author information

Authors and Affiliations

  1. Université Grenoble Alpes, Laboratoire Jean Kuntzmann, CNRS, UMR 5224, 700 avenue centrale, IMAG - CS 40700, 38058, Grenoble, Cedex 9, France

    Jean-Guillaume Dumas

Authors
  1. Jean-Guillaume Dumas
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jean-Guillaume Dumas .

Editor information

Editors and Affiliations

  1. Laboratory of Information Technologies, Joint Institute of Nuclear Research, Dubna, Russia

    Vladimir P. Gerdt

  2. Institut für Mathematik, Universität Kassel, Kassel, Germany

    Wolfram Koepf

  3. Institut für Mathematik, Universität Kassel, Kassel, Germany

    Werner M. Seiler

  4. Institute of Theoretical and Applied Mechanics, Russian Academy of Sciences, Novosibirsk, Russia

    Evgenii V. Vorozhtsov

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

Dumas, JG. (2018). Proof-of-Work Certificates that Can Be Efficiently Computed in the Cloud (Invited Talk). In: Gerdt, V., Koepf, W., Seiler, W., Vorozhtsov, E. (eds) Computer Algebra in Scientific Computing. CASC 2018. Lecture Notes in Computer Science(), vol 11077. Springer, Cham. https://doi.org/10.1007/978-3-319-99639-4_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-99639-4_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-99638-7

  • Online ISBN: 978-3-319-99639-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation