Re: Proving knowledge of a message with a given SHA-1 without disclosing it?



On 01/02/2012 22:40, Paul Rubin wrote:

Francois Grieu<fgrieu@xxxxxxxxx> writes:
Can she convince Bob of her claim using some protocol, without letting
Bob find m, and without a third party or device that Bob trusts?

I don't know about zero-knowledge, but I'd expect from the PCP theorem
that there is a protocol that might leak some info about m. The amount
of leak would be bounded by k bits where Bob is supposed to be convinced
with confidence 1-2**O(k) that Alice has a preimage. Maybe the format
of m can be designed so that this bounded amount of leakage doesn't matter.

Or maybe a leak is not exploitable by Bob, because he is computationally
bounded.
For example, if Alice discloses SHA-1(~m), she discloses 160 bits
about m, mostly additional to SHA-1(m). Yet it does not help a computationally
bounded Bob, to the best of the known techniques.

Francois Grieu
.



Relevant Pages

  • Re: Fact v Fishy
    ... what did he do that brought about such a sudden and tremendous change ... mysterious when you look at the amount of material he would then ... Brother Bob completely went the other way. ... it was during the whole year from session 1 to ...
    (rec.music.dylan)
  • Re: Fact v Fishy
    ... mysterious when you look at the amount of material he would then ... Brother Bob completely went the other way. ... it was during the whole year from session 1 to ...
    (rec.music.dylan)
  • Re: Fact v Fishy
    ... mysterious when you look at the amount of material he would then ... Brother Bob completely went the other way. ... it was during the whole year from session 1 to ...
    (rec.music.dylan)
  • Novak Takes A Leak
    ... Novak Takes a Leak ... "Bob," I said as I stood beside him, our positions before the ... "Listen, Mark," he said, his voice gruff. ...
    (alt.politics.bush)
  • Re: Gen.McChrystal - Woodward - Cohen - Leak : first fabricated scandal from within = th
    ... No sign that the leak was a leak, ... Bob Woodward?s Monday-morning exclusive on a 66-page report from Gen. ... Post reporter has penetrated yet another administration. ... suggested they?d begin a witch hunt for the leaker. ...
    (sci.military.naval)