International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Omer Paneth

Affiliation: MIT

Publications

Year
Venue
Title
2019
CRYPTO
On Round Optimal Statistical Zero Knowledge Arguments 📺
Nir Bitansky Omer Paneth
We construct the first three message statistical zero knowledge arguments for all of NP, matching the known lower bound. We do so based on keyless multi-collision resistant hash functions and the Learning with Errors assumption—the same assumptions used to obtain round optimal computational zero knowledge.The main component in our construction is a statistically witness indistinguishable argument of knowledge based on a new notion of statistically hiding commitments with subset opening.
2019
TCC
Incrementally Verifiable Computation via Incremental PCPs
If I commission a long computation, how can I check that the result is correct without re-doing the computation myself? This is the question that efficient verifiable computation deals with. In this work, we address the issue of verifying the computation as it unfolds. That is, at any intermediate point in the computation, I would like to see a proof that the current state is correct. Ideally, these proofs should be short, non-interactive, and easy to verify. In addition, the proof at each step should be generated efficiently by updating the previous proof, without recomputing the entire proof from scratch. This notion, known as incrementally verifiable computation, was introduced by Valiant [TCC 08] about a decade ago. Existing solutions follow the approach of recursive proof composition and can be based on strong and non-falsifiable cryptographic assumptions (so-called “knowledge assumptions”).In this work, we present a new framework for constructing incrementally verifiable computation schemes in both the publicly verifiable and designated-verifier settings. Our designated-verifier scheme is based on somewhat homomorphic encryption (which can be based on Learning with Errors) and our publicly verifiable scheme is based on the notion of zero-testable homomorphic encryption, which can be constructed from ideal multi-linear maps [Paneth and Rothblum, TCC 17].Our framework is anchored around the new notion of a probabilistically checkable proof (PCP) with incremental local updates. An incrementally updatable PCP proves the correctness of an ongoing computation, where after each computation step, the value of every symbol can be updated locally without reading any other symbol. This update results in a new PCP for the correctness of the next step in the computation. Our primary technical contribution is constructing such an incrementally updatable PCP. We show how to combine updatable PCPs with recently suggested (ordinary) verifiable computation to obtain our results.
2017
EUROCRYPT
2017
TCC
2016
EUROCRYPT
2016
TCC
2016
TCC
2016
TCC
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
TCC
2015
TCC
2014
CRYPTO
2014
CRYPTO
2014
CRYPTO
2014
EUROCRYPT
2014
PKC
2014
TCC
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2013
TCC
2013
TCC
2013
CRYPTO
2012
TCC

Program Committees

Crypto 2019
TCC 2019
Eurocrypt 2017
TCC 2017