[cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it?
jkatz at cs.umd.edu
Wed Feb 1 17:32:29 EST 2012
On Wed, 1 Feb 2012, Nico Williams wrote:
> On Wed, Feb 1, 2012 at 3:49 AM, Francois Grieu <fgrieu at 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 :^)
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.
More information about the cryptography