On Wed, 1 Feb 2012, Nico Williams wrote:
On Wed, Feb 1, 2012 at 3:49 AM, Francois Grieu <fgr...@gmail.com> wrote:
The talk does not give much details, and I failed to locate any article
with a similar claim.
I would find that result truly remarkable, and it is against my intuition.
The video you posted does help me with the intuition problem. The
idea seems to be to replace the normal arithmetic in SHA-1 with
operations from a zero-knowledge scheme such that in the end you get a
zero-knowledge proof of the operations that were applied to the input.
That makes complete sense to me, even without seeing the details.
But maybe I'm just gullible :^)
Nico
In some sense this is all not very surprising. The Cramer-Damgard paper he
cites in his talk describes a zero-knowledge proof for the NP-complete
problem of boolean circuit satisfiability. So the only question is to
express SHA-1 (plus a check for string equality) as a boolean circuit and
then apply their technique. And implement it, of course. =)
(Anyone have an estimate as to how many gates such a circuit would have,
assuming you are evaluating SHA-1 on a two-block input?)
As he says in his talk, the point of the exercise is not to claim any
novelty for the resulting protocol, but to explore how efficient these
generic techniques can be when applied to circuits of practical interest.
Since he appears not to have written up the work, it is unclear what
additional optimizations could have been made.
_______________________________________________
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
