Compact Proofs of Retrievability

In a proof-of-retrievability system, a data storage center must prove to a verifier that he is actually storing all of a client’s data. The central challenge is to build systems that are both efficient and provably secure – that is, it should be possible to extract the client’s data from any prover that passes a verification check.

We present the first proof-of-retrievability schemes with full proofs of security against arbitrary adversaries in the strongest model, that of Juels and Kaliski. Our first scheme, built from BLS signatures and secure in the random oracle model, has the shortest query and response of any proof-of-retrievability with public verifiability. Our second scheme, which builds elegantly on pseudorandom functions (PRFs) and is secure in the standard model, has the shortest response of any proof-of-retrievability scheme with private verifiability (but a longer query). Both schemes rely on homomorphic properties to aggregate a proof into one small authenticator value.

Joint work with Brent Waters (UT Austin).

Speaker Details

Hovav Shacham is an Assistant Professor in the department of Computer Science & Engineering at the University of California, San Diego.Dr. Shacham received his Ph.D. in computer science in 2005 from Stanford University, where he had also earned, in 2000, an A.B. in English. In 2006 and 2007, he was a Koshland Scholars Program postdoctoral fellow at the Weizmann Institute of Science.Dr. Shacham’s research interests are in applied cryptography, systems security, and tech policy.He is one of the pioneers in using pairings – computable bilinear maps over certain elliptic curves – to construct cryptographic systems. His thesis, “New Paradigms in Signature Schemes,” was runner up for the Stanford Department of Computer Science’s Arthur L. Samuel Thesis Award, and was nominated for the ACM Doctoral Dissertation Competition. At the Weizmann, Shacham taught a survey on pairings in cryptography, one of the first such courses to be offered.Dr. Shacham is the inventor of “return-oriented programming,” an attack against the class of protective measures that attempt to prevent malicious computation by distinguishing between “good code” present in the system and “bad code” introduced by the attacker. With return-oriented programming, the attacker combines short snippets of preexisting good code into gadgets from which he can synthesize arbitrary functionality without introducing any new code. One defensive measure threatened is Data Execution Prevention (DEP), implemented in Windows Vista and supported by changes to Intel processors. DEP makes it impossible for an attacker to execute code injected into a compromised process; but in the face of return-oriented programming it provides no security benefits.In 2007, Dr. Shacham participated in California Secretary of State Debra Bowen’s “Top-to-Bottom” of the voting machines certified for use in California. He was a member of the team reviewing Hart InterCivic source code; the report he co-authored was cited by the Secretary in her decision to withdraw approval from Hart voting machines.

Date:
Speakers:
Hovav Shacham
Affiliation:
UC San Diego