A New Construction of Publicly-Verifiable Non-Interactive Succinct Arguments

Alessandro Chiesa (MIT)

Abstract:

The problem of verifiably delegating computation has a powerful solution in the random-oracle model: any NP statement can be proven non-interactively and verified quickly by anyone, while guaranteeing soundness against computationally-bounded provers. Such proof systems are called publicly-verifiable Succinct Non-interactive ARGuments (SNARGs).

In recent years, researchers have sought to provide solutions to the problem of delegating computation, without relying on random oracles, that are as close as possible to publicly-verifiable SNARGs. While this line of research has produced beautiful constructions using a variety of cryptographic tools (including fully-homomorphic encryption, Yao's garbled circuits, and functional encryption), these constructions fell short of the ultimate goal.

In this talk I will present a new construction of publicly-verifiable SNARGs whose security can be based on a knowledge-of-exponent assumption in the plain model. While considered non-standard, such kinds of assumptions have been widely used over the past 20 years, in a variety of settings, without being broken. The construction does not rely on the Fiat-Shamir paradigm and, furthermore, achieves efficiency features that are not known to be achievable even in the random-oracle model.

Based on joint work with Nir Bitansky, Ran Canetti, Yuval Ishai, Rafail Ostrovsky, Omer Paneth, and Eran Tromer.

Time and Place

Tuesday, January 15, 2013, 4:30pm
Gates 463A