[cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it?
Alice discloses a 160-bit value h and claims that she (or parties/devices she has access to) knows a message m with h=SHA-1(m). 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? At a Crypto'98 rump session, Hal Finney made a 7-minutes presentation A zero-knowledge proof of possession of a pre-image of a SHA-1 hash claiming a feasible protocol for this. http://video.google.com/videoplay?docid=-5745972992365920864 This talk mentions using the protocol in the Crypto'98 paper of Ronald Cramer and Ivan B. Damgård: Zero-Knowledge Proofs for Finite Field Arithmetic or: Can Zero-Knowledge be for Free? http://www.springerlink.com/content/0l4734h77615u161/ ftp://ftp.inf.ethz.ch/pub/crypto/publications/CraDam98.pdf http://www.brics.dk/RS/97/27/BRICS-RS-97-27.pdf 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. Any info on the Hal Finney protocol, or a protocol giving a similar result, or the (in)feasibility of such a protocol? TIA, Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it?
You can obviously prove it in the case where Alice claims she knows SHA-1(SHA-1(m)), which seems to be the same claim. William -Original Message- From: cryptography-boun...@randombit.net [mailto:cryptography- boun...@randombit.net] On Behalf Of Francois Grieu Sent: Wednesday, February 01, 2012 4:49 AM To: cryptography@randombit.net Subject: [cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it? Alice discloses a 160-bit value h and claims that she (or parties/devices she has access to) knows a message m with h=SHA-1(m). 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? At a Crypto'98 rump session, Hal Finney made a 7-minutes presentation A zero-knowledge proof of possession of a pre-image of a SHA-1 hash claiming a feasible protocol for this. http://video.google.com/videoplay?docid=-5745972992365920864 This talk mentions using the protocol in the Crypto'98 paper of Ronald Cramer and Ivan B. Damgård: Zero-Knowledge Proofs for Finite Field Arithmetic or: Can Zero-Knowledge be for Free? http://www.springerlink.com/content/0l4734h77615u161/ ftp://ftp.inf.ethz.ch/pub/crypto/publications/CraDam98.pdf http://www.brics.dk/RS/97/27/BRICS-RS-97-27.pdf 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. Any info on the Hal Finney protocol, or a protocol giving a similar result, or the (in)feasibility of such a protocol? TIA, Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it?
On 01/02/2012 13:32, William Whyte wrote : You can obviously prove it in the case where Alice claims she knows SHA-1(SHA-1(m)), which seems to be the same claim. Alice discloses h and claims knowledge of m with h=SHA1(m). That's not equivalent to claiming knowledge of SHA-1(SHA-1(m)), which anyone can compute as SHA-1(h). Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it?
[William Whyte wwh...@securityinnovation.com (2012-02-01 12:32:05 UTC)] Alice discloses a 160-bit value h and claims that she (or parties/devices she has access to) knows a message m with h=SHA-1(m). 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? [...] You can obviously prove it in the case where Alice claims she knows SHA-1(SHA-1(m)), which seems to be the same claim. I feel an anti-top-posting rant coming on, but I'll endeavour to clamp down on it. Instead, let me ask if you have a different definition of «obvious» than I do? Or if not, a sentence or two of explanation should clear it up real quick. - Harald ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it?
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 -- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Proving knowledge of a message with a given
Natanael wrote: We do have zero-knowledge proofs, but AFAIK they do not use SHA1. I'm not after a proof that uses SHA-1; I'm after a proof of a message with given SHA-1 result, which is something very different. http://en.wikipedia.org/wiki/Zero-knowledge_password_proof http://en.wikipedia.org/wiki/Zero-knowledge_proof http://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof -- Most likely what you want Some of the techniques discussed here are close. In particular, some zero-knowledge proof of the solution of a SAT problem may fit the task, as it is easy to rewrite the problem h=SHA-1(m) for known h and unknown m as a SAT problem with some thousands clauses. However I'm afraid that the proof size (or the amount of work/data involved in the protocol) could grow beyond practicality. The talk does hint that it was necessary to use optimizations, but I could not extract enough information to understand which. Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it?
On 01/02/2012 18:50, Nico Williams wrote: On Wed, Feb 1, 2012 at 3:49 AM, Francois Grieufgr...@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 :^) Issues seem to be: can we chain commitments of commitments, to so many levels (hundreds, I guess), and still get something manageable? Did some detail slept in the talk's method? In particular, the XOR and ADD that make the bulk of SHA-1 are not field operations. A detailed analysis could tell, but we do not have enough detail on the talk's method, or on a similar claim. Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it?
On Feb 1, 2012, at 1:49 AM, Francois Grieu 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. Any info on the Hal Finney protocol, or a protocol giving a similar result, or the (in)feasibility of such a protocol? As I remember Hal's protocol, it requires about eight megabytes of data to be transferred back and forth to prove that you know the SHA1 hash. It's not so much to be obviously absurd, but not efficient enough to be something you'd want to do often. Jon ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it?
On 01/02/2012 21:09, Jon Callas wrote: As I remember Hal's protocol, it requires about eight megabytes of data to be transferred back and forth to prove that you know the SHA1 hash. It's not so much to be obviously absurd, but not efficient enough to be something you'd want to do often. Close. If I get it correctly, it is a zero-knowledge proof, with one pass (leaving I guess =50% odds of forgery) requiring 100 seconds and 22 kbytes of data (exchanged?), after some initial pre-computation requiring 40 minutes and 6MBytes of data (storage?), on a PC as it was circa 14 years ago. That, and more, is at 6'52 in the talk at http://video.google.com/videoplay?docid=-5745972992365920864 Hal Finney explains he got his result after careful optimizations, rewriting some SHA-1 internal operations as arithmetic operations in some appropriate field, rather than as boolean operations. Everything he says is convincing, but in 7 minutes there is not much detail, and so far I could not locate any later work (by him or others) claiming a comparable result. So it is hard to rule out that some error crept in his work. Francois Grieu ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it?
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
