Title: Verifiable Computation: From Polynomials and Graphs to Databases and RAM Programs
Speaker: Charalampos (Babis) Papamanthou (University of Maryland)
Date: Wed. Feb. 21, 2018, 9am
Room: CSE 4258
In the age of cloud computing and distributed blockchains outsourcing of storage and computation has become quite prevalent: Databases and email are now mostly hosted by large providers like Amazon or Google driving down the costs of on-premises infrastructure and allowing anyone to run SQL queries fast or read email 24/7; Cryptocurrency blockchains (e.g., Bitcoin) are maintained by powerful miners enabling even lightweight nodes running on smartphones to access, for example, information about previous transactions and blocks. While this new outsourcing paradigm has created economies of scale it is clear that most of the computation and storage is nowadays consumed from parties that we do not necessarily trust.
In this talk I will present research that we have been doing over the last few years on techniques and protocols for verifiable computation. In particular, verifiable computation enables a lightweight node to outsource his storage and computation to an untrusted powerful server in a way that a query result can be cryptographically verified by using far less resources than those required to perform the computation. I will describe progress in two fronts: First, I will present protocols for verifying custom functionalities, such as simple database queries or graph algorithms, leading to fairly practical protocols. Then I will show how designing such application-specific mechanisms has provided insights towards new and scalable general-purpose methods, leading to systems such as vSQL and vRAM that can verify arbitrary SQL and RAM programs. While the produced protocols are still not practical per se (e.g., when compared with native execution), they have improved the state of the art in terms of practical performance (and sometimes in terms of asymptotics) by several orders of magnitude. I will conclude with some open problems in the area, lessons learnt, and interesting applications on more scalable blockchains that we are currently working on.
Charalampos (Babis) Papamanthou is an assistant professor of Electrical and Computer Engineering at the University of Maryland, College Park, where he joined in 2013 after a postdoc at UC Berkeley. At Maryland, he is also affiliated with the Institute for Advanced Computer Studies (UMIACS), where he is a member of the Maryland Cybersecurity Center (MC2). He works on applied cryptography and computer security – and especially on technologies, systems and theory for secure and private cloud computing. While at College Park, he received the NSF CAREER award, Google Faculty Research Award, the Yahoo! Faculty Research Engagement Award, the NetApp Faculty Fellowship, the 2013 UMD Invention of the Year Award, the 2014 Jimmy Lin Award for Invention and the George Corcoran Award for Excellence in Teaching. His research has been funded by federal agencies (NSF, NIST and NSA) and by the industry (Google, Yahoo!, NetApp and Amazon). His PhD is in Computer Science from Brown University (2011) and he also holds an MSc in Computer Science from the University of Crete (2005), where he was a member of ICS-FORTH. His work has received over 3,000 citations and he has published in venues and journals spanning theoretical and applied cryptography, systems and database security, graph algorithms and visualization and operations research.