[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/2382196.2382250acmconferencesArticle/Chapter ViewAbstractPublication PagesccsConference Proceedingsconference-collections
research-article

Publicly verifiable delegation of large polynomials and matrix computations, with applications

Published: 16 October 2012 Publication History

Abstract

Outsourced computations (where a client requests a server to perform some computation on its behalf) are becoming increasingly important due to the rise of Cloud Computing and the proliferation of mobile devices. Since cloud providers may not be trusted, a crucial problem is the verification of the integrity and correctness of such computation, possibly in a public way, i.e., the result of a computation can be verified by any third party, and requires no secret key -- akin to a digital signature on a message. We present new protocols for publicly verifiable secure outsourcing of Evaluation of High Degree Polynomials and Matrix Multiplication. Compared to previously proposed solutions, ours improve in efficiency and offer security in a stronger model. The paper also discusses several practical applications of our protocols.

References

[1]
B. Applebaum, Y. Ishai, and E. Kushilevitz. From secrecy to soundness: Efficient verification via secure computation. In S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, and P. G. Spirakis, editors, ICALP 2010 International Colloquium on Automata, Languages and Programming, Part I, volume 6198 of Lecture Notes in Computer Science, pages 152--163, Bordeaux, France, July 6--10, 2010. Springer, Berlin, Germany.
[2]
L. Babai. Trading group theory for randomness. In 17th Annual ACM Symposium on Theory of Computing, pages 421--429, Providence, Rhode Island, USA, May 6--8, 1985. ACM Press.
[3]
M. Belenkiy, M. Chase, C. C. Erway, J. Jannotti, A. Küpçü, and A. Lysyanskaya. Incentivizing outsourced computation. In Workshop on Economics of Networked Systems -- NetEcon, pages 85--90, 2008.
[4]
S. Benabbas, R. Gennaro, and Y. Vahlis. Verifiable delegation of computation over large datasets. In P. Rogaway, editor, Advances in Cryptology -- CRYPTO 2011, volume 6841 of Lecture Notes in Computer Science, pages 111--131, Santa Barbara, CA, USA, Aug. 14--18, 2011. Springer, Berlin, Germany.
[5]
D. Boneh and M. K. Franklin. Identity-based encryption from the Weil pairing. In J. Kilian, editor, Advances in Cryptology -- CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, pages 213--229, Santa Barbara, CA, USA, Aug. 19--23, 2001. Springer, Berlin, Germany.
[6]
D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weil pairing. In C. Boyd, editor, Advances in Cryptology -- ASIACRYPT 2001, volume 2248 of Lecture Notes in Computer Science, pages 514--532, Gold Coast, Australia, Dec. 9--13, 2001. Springer, Berlin, Germany.
[7]
K.-M. Chung, Y. Kalai, and S. P. Vadhan. Improved delegation of computation using fully homomorphic encryption. In T. Rabin, editor, Advances in Cryptology -- CRYPTO 2010, volume 6223 of Lecture Notes in Computer Science, pages 483--501, Santa Barbara, CA, USA, Aug. 15--19, 2010. Springer, Berlin, Germany.
[8]
R. Gennaro, C. Gentry, and B. Parno. Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In T. Rabin, editor, Advances in Cryptology -- CRYPTO 2010, volume 6223 of Lecture Notes in Computer Science, pages 465--482, Santa Barbara, CA, USA, Aug. 15--19, 2010. Springer, Berlin, Germany.
[9]
C. Gentry. Fully homomorphic encryption using ideal lattices. In M. Mitzenmacher, editor, 41st ACM STOC Annual ACM Symposium on Theory of Computing, pages 169--178, Bethesda, Maryland, USA, May 31 -- June 2, 2009. ACM Press.
[10]
S. Goldwasser, Y. T. Kalai, and G. N. Rothblum. Delegating computation: interactive proofs for muggles. In R. E. Ladner and C. Dwork, editors, 40th ACM STOC Annual ACM Symposium on Theory of Computing, pages 113--122, Victoria, British Columbia, Canada, May 17--20, 2008. ACM Press.
[11]
S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186--208, 1989.
[12]
V. Goyal, O. Pandey, A. Sahai, and B. Waters. Attribute-based encryption for fine-grained access control of encrypted data. In A. Juels, R. N. Wright, and S. Vimercati, editors, ACM CCS Conference on Computer and Communications Security, pages 89--98, Alexandria, Virginia, USA, Oct. 30 -- Nov. 3, 2006. ACM Press. Available as Cryptology ePrint Archive Report 2006/309.
[13]
J. Kilian. A note on efficient zero-knowledge proofs and arguments. In 24th Annual ACM Symposium on Theory of Computing, pages 723--732, Victoria, British Columbia, Canada, May 4--6, 1992. ACM Press.
[14]
J. Kilian. Improved efficient arguments. In International Cryptology Conference on Advances in Cryptology, pages 311--314, London (UK), 1995. Springer-Verlag.
[15]
A. Lewko and B. Waters. New proof methods for attribute-based encryption: Achieving full security through selective techniques. Crypto 2012, to appear.
[16]
A. B. Lewko and B. Waters. Efficient pseudorandom functions from the decisional linear assumption and weaker variants. In E. Al-Shaer, S. Jha, and A. D. Keromytis, editors, ACM CCS 09 Conference on Computer and Communications Security, pages 112--120, Chicago, Illinois, USA, Nov. 9--13, 2009. ACM Press.
[17]
S. Micali. Cs proofs. In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, Nov. 20--22, 1994.
[18]
P. Mohassel. Efficient and secure delegation of linear algebra. Cryptology ePrint Archive, Report 2011/605.
[19]
F. Monrose, P. Wyckoff, and A. D. Rubin. Distributed execution with remote audit. In ISOC Network and Distributed System Security Symposium -- NDSS'99, San Diego, California, USA, Feb. 3--5, 1999. The Internet Society.
[20]
C. Papamanthou, E. Shi, and R. Tamassia. Signatures of correct computation. Cryptology ePrint Archive, Report 2011/587, 2011.
[21]
B. Parno, M. Raykova, and V. Vaikuntanathan. How to delegate and verify in public: Verifiable computation from attribute-based encryption. TCC 2012.
[22]
S. W. Smith and S. Weingart. Building a high-performance, programmable secure coprocessor. Computer Networks, 31:831--860, 1999.
[23]
B. Yee. Using Secure Coprocessors. PhD thesis, Carnegie Mellon University, 1994.

Cited By

View all
  • (2025)Privacy-preserving fair outsourcing polynomial computation without FHE and FPRComputer Standards & Interfaces10.1016/j.csi.2024.10389991(103899)Online publication date: Jan-2025
  • (2024)Research progress of verifiable technologies for outsourcing servicesSCIENTIA SINICA Informationis10.1360/SSI-2022-036054:3(514)Online publication date: 6-Mar-2024
  • (2024)VERITAS: Plaintext Encoders for Practical Verifiable Homomorphic EncryptionProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670282(2520-2534)Online publication date: 2-Dec-2024
  • Show More Cited By

Index Terms

  1. Publicly verifiable delegation of large polynomials and matrix computations, with applications

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      CCS '12: Proceedings of the 2012 ACM conference on Computer and communications security
      October 2012
      1088 pages
      ISBN:9781450316514
      DOI:10.1145/2382196
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 16 October 2012

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. pseudorandom functions
      2. verifiable computation

      Qualifiers

      • Research-article

      Conference

      CCS'12
      Sponsor:
      CCS'12: the ACM Conference on Computer and Communications Security
      October 16 - 18, 2012
      North Carolina, Raleigh, USA

      Acceptance Rates

      Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

      Upcoming Conference

      CCS '25

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)43
      • Downloads (Last 6 weeks)5
      Reflects downloads up to 13 Dec 2024

      Other Metrics

      Citations

      Cited By

      View all
      • (2025)Privacy-preserving fair outsourcing polynomial computation without FHE and FPRComputer Standards & Interfaces10.1016/j.csi.2024.10389991(103899)Online publication date: Jan-2025
      • (2024)Research progress of verifiable technologies for outsourcing servicesSCIENTIA SINICA Informationis10.1360/SSI-2022-036054:3(514)Online publication date: 6-Mar-2024
      • (2024)VERITAS: Plaintext Encoders for Practical Verifiable Homomorphic EncryptionProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670282(2520-2534)Online publication date: 2-Dec-2024
      • (2024)How to Securely and Efficiently Solve the Large-Scale Modular System of Linear Equations on the CloudIEEE Transactions on Cloud Computing10.1109/TCC.2024.340824012:3(913-927)Online publication date: Jul-2024
      • (2024)A Publicly Verifiable Outsourcing Matrix Computation Scheme Based on Smart ContractsIEEE Transactions on Cloud Computing10.1109/TCC.2023.333784812:1(70-83)Online publication date: Jan-2024
      • (2024)An efficient polynomial-based verifiable computation scheme on multi-source outsourced dataScientific Reports10.1038/s41598-024-53267-x14:1Online publication date: 12-Apr-2024
      • (2024)Privacy-Preserving Fair Outsourcing Polynomial Computation Without FHE and FPRMobile Internet Security10.1007/978-981-97-4465-7_6(78-93)Online publication date: 12-Jul-2024
      • (2024)Multi-key Fully-Homomorphic Aggregate MAC for Arithmetic CircuitsProgress in Cryptology – INDOCRYPT 202410.1007/978-3-031-80308-6_10(213-233)Online publication date: 13-Dec-2024
      • (2023)Protecting Function Privacy and Input Privacy in the Publicly Verifiable Outsourcing Computation of Polynomial FunctionsFuture Internet10.3390/fi1504015215:4(152)Online publication date: 21-Apr-2023
      • (2023)Privacy-Preserving Large Language Models (PPLLMs)SSRN Electronic Journal10.2139/ssrn.4512071Online publication date: 2023
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media