THIS IS A CONTINUATION OF N00014-14-1-0469 Making Proof-Based Verifiable Computation Practical
Abstract
Making Proof-Based Verifiable Computation Practical: Exec. Summary The objective of the proposed research is to address a fundamental problem in systems security: how can we build a system in which one computer can verify that another computer executed correctly? We will tackle this question using the emerging approach of proof-based verifiable computation. In this research area, the central activities are refining deep complexity-theoretic and cryptographic machinery, and then implementing and rigorously evaluating systems that are based on the refined theory. Success in the research program would be revolutionary and transformative: we would get inexpensive guarantees of execution correctness. This capability would apply in many contexts (cloud computing, distributed systems, defense applications, tightly coupled local systems, etc.). Consider an embedded robot deployed in hostile territory; we must regard this machine as a third party no longer under our control. Or consider cloud computing, which, despite enormous promise (sophisticated analysis on gargantuan data sets, inexpensive local devices with access to vast remote computing resources, etc.), brings risk. In these and other third-party computing scenarios, many things can go wrong without the failure being evident. Thus, the outsourcing computer (the base, the client of the cloud, etc.) needs assurance that the computation was carried out correctly. The PI has been at the forefront of research on a new approach to this problem that, in contrast to prior work, does not make potentially unrealistic assumptions about the system performing the computation (replication by uncorrelated machines, trusted hardware, etc.) and applies to broad classes of computations. Although it had been known for decades that the problem of general-purpose verifiable outsourced computation has theoretical solutions (interactive proofs and probabilistically checkable proofs (PCPs), coupled with cryptographic commitments in the context of arguments), the performance of these tools was “known” to be wildly impractical (trillions of CPU-years or more to verify simple computations). Over the past few years, the PI has challenged the second piece of this folklore, by incorporating deep results from complexity theory and cryptography into built systems—with experiments that terminated in minutes and hours. However, despite the exciting advances, these systems are still not practical in the normal sense; for instance, overhead for the performing computer is still too large for many usage scenarios, and high memory utilization precludes handling computations of realistic size. The ultimate goal is truly practical performance. To get there, we propose a “Grand Challenge” to both stimulate and advance this emerging area: over the next few years, make proof-based verifiable computation truly practical for certain real-world problems at realistic input sizes. The proposed research will respond to this challenge.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jun 03, 2016
- Source ID
- N000141612154
Entities
People
- Michael Walfish
Organizations
- New York University
- Office of Naval Research
- United States Navy