Top

Published in:

2018 | OriginalPaper | Chapter

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

Author : Jean-Guillaume Dumas

Published in: Computer Algebra in Scientific Computing

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

next chapter On Unimodular Matrices of Difference Operators

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.1490272CrossRefMATH

Á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.pdfCrossRef

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)

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

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

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

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_11CrossRef

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/0215070MathSciNetCrossRefMATH

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_19CrossRef

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

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_12CrossRefMATH

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_10CrossRef

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_18CrossRef

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-4CrossRefMATH

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-01503870CrossRef

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]

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_5CrossRef

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

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

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-yMathSciNetCrossRefMATH

37.

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

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/2153451MathSciNetCrossRefMATH

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.146605CrossRefMATH

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

47.

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

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_24CrossRef

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]

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

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

55.

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

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_5CrossRef

58.

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

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.1057137MathSciNetCrossRefMATH

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_10CrossRef

61.

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

Title: Proof-of-Work Certificates that Can Be Efficiently Computed in the Cloud (Invited Talk)
Author: Jean-Guillaume Dumas
Publisher: Springer International Publishing
Book: Computer Algebra in Scientific Computing
Print ISBN: 978-3-319-99638-7

Electronic ISBN: 978-3-319-99639-4

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-99639-4_1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner