News for hackers. Stuff that matters.
Re:Oded Wins the Knuth Prize by modalduality on Thursday June 22, 2017 @06:57PM (#14615944)
Some context: doubly efficient interactive proofs are one of the fundamental ideas that make Zcash possible on modern hardware.
Re:Oded Wins the Knuth Prize by Ar-Curunir on Thursday June 22, 2017 @08:01PM (#14616209)
No, doubly efficient IPs do not have much to do with ZCash. deIPs are currently too weak to prove the general NP statements that ZCash requires.

ZCash relies on a different kind of "proof" system: SNARKs.

There's many differences between the two:

a) deIPs assume a computationally unbounded adversary, whereas SNARKs assume a polytime adversary.

b) deIP constructions currently suffice only for a limited class of languages, whereas SNARKs can prove any NP statement.

c) SNARKs have zero knowledge variants, whereas it is not clear how to extend many deIP constructions to be zero knowledge without changing the model (ala https://eprint.iacr.org/2017/305).

d) Most deIPs are interactive proof systems, whereas SNARKs are non-interactive.

Re:Oded Wins the Knuth Prize by mdxn on Thursday June 22, 2017 @09:51PM (#14616643)
I think what you are claiming here is misleading.

Some pre-processing SNARK constructions (particularly ones used by some ZCash scientists) are based on multi-round interactive proof systems which reduce to one round (depending on how you count) when you relax some requirements. Such relaxations include weakening the adversary from being computationally unbounded to polynomial time bounded, forcing the prover and verifier to use a specific set of functions, or restricting what kinds of statements can be proven. Oded's work on efficient interactive proofs contributed to this effort. It is partially this efficiency that helps SNARKs actually be "succinct" and quick to verify.

You should check out some of the citations to Oded's work in https://eprint.iacr.org/2012/718.pdf (which is co-authored by Alessandro Chiesa of ZCash) and see for yourself.

Re:Oded Wins the Knuth Prize by Ar-Curunir on Thursday June 22, 2017 @10:08PM (#14616703)
One can construct SNARKs from succinct MIPs, but these are again very different from deIPs. Sure, both SNARKs and deIPs involve highly efficient verifiers, and there is some overlap between the techniques used for succinct MIPs and deIPs, but that's pretty much where the similarities end. Furthermore, MIP based SNARKs are way too inefficient, and definitely not the ones used in Zerocash.

There are no constructions of SNARKs from deIPs, nor vice versa. In particular, one cannot construct laconic IPs at all for NP like languages.

P.S.: I'm Alessandro's student ;-)

Re:Oded Wins the Knuth Prize by modalduality on Thursday June 22, 2017 @09:12PM (#14616513)
Huh, you're correct. My professor said doubly-efficient IPs were used in Zcash, maybe he just meant as inspiration?