Talk:Commitment scheme

Tip: Anchors are case-sensitive in most browsers.

This article links to one or more target anchors that no longer exist.

[[Elliptic-curve cryptography#Rationale|elliptic curve discrete logarithm problem]] The anchor (#Rationale) is no longer available because it was deleted by a user before.

Please help fix the broken anchors. You can remove this template after fixing the problems. | Reporting errors

For information about committed identity on Wikipedia, see Template:Committed identity

Mathematics Mid‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Mid	This article has been rated as Mid-priority on the project's priority scale.

Cryptography: Computer science High‑importance

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
High	This article has been rated as High-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as High-importance).

Untitled[edit]

I think the explanation of a bit-commitment protocol from a hash function is incorrect:

A simple commitment scheme is the following: if b is the commitment, Alice generates a large random number r and gives to Bob a hash of b concatenated with r. To open her commitment, Alice reveals b and r thus letting Bob recalculate the hash and compare it with the hash given him earlier to make sure Alice didn't cheat.

If the output length of the hash function is specified (as it is in most cryptographic hash functions) concatenating h(b) and r allows Bob to completely recover h(b) and r.

There is a reasonable sounding bit-commitment protocol from a hash function explained at everything2, and unless someone can explain why the protocol explained here works, I'm going to change the one here.

--Beamishboy 00:00, 3 August 2006 (UTC)[reply]

The point is, that Alice hashes the random number r concatenated with b. Since Bob does not know r, and cannot invert the hash function, he has no information whatsoever about b (assuming the output of the hash function is statistically independent of b). So basically what Alice tells Bob in the commitment phase is "I know a number which hashes to the value y=h(b), and the last bit of that number is the one I want to commit to.". It is binding because in order to cheat, Alice needs to find a number with last bit -b and the hash value y that she announced before. If the hash function is really one-way, this is (virtually) impossible.

--Tagmrfen 11:21, 24 August 2006 (UTC)[reply]

Thanks for the clarification. I misunderstood the order of operations. If || denotes concatenation, I thought the scheme was h(b) || r instead of h(b||r). As you say though, the security of this bit commitment scheme still rests on the fact that the hash function is statistically independent of b. This fact is not captured by most definitions of hash function security. For example, for this application it is not enough to assume h is collision-resistant or preimage resistant. For that reason, I still would like to change it.

--Beamishboy 22:31, 25 August 2006 (UTC)[reply]

You are right, but a hash function that allows to guess one bit of its input with probability != 1/2 would certainly be a very bad hash function. The easy example I like most is the following: Take TWO one-way permutations (!) h_0 and h_1, known to Alice and Bob. Alice chooses a random input X and sends Y=h_b(X) to Bob (note that this is effectively the same as having a hash function which takes one bit more and whose output is statistically independent of b).

Alice effectively promises "I know a number which permuted by h_b is Y". Thus the protocol is perfectly (!) concealing. To reveal the bit, she gives b and X to Bob, who checks that h_b(X)=Y. To cheat, Alice must be able to invert the one-way permutations, which she cannot in reasonable time. So the protocol is binding in a computational sense.

I do not like the protocol at everything2 for two reasons:

The XOR of two hash function is unneccessary, since it can be merged into one hash function that calculates h_Alice(X) XOR h_Bob(X). There is no point in constructing it from two different functions, since a honest participant must assume that his/her hash function is a "good" hash function anyway, so one could as well use just that one and fix it by the protocol specification.
On second look, it is just a derivation of the simple protocol described in the article: appending the bit to r is effectively the same as choosing the first N bits of a N+1-bit string at random (->r) and then adjusting the last bit so the parity is even (b=0) or odd (b=1). So one still must assume that the output of the composite hash function is statistically uncorrelated with the parity of the input.

--Tagmrfen 00:03, 27 August 2006 (UTC)[reply]

Link to external site[edit]

Is there any good reason why this page doesn't give a link, in the external links section, to a site such as [1] which will actually calculate the commitment? (I got that link from Wikipedia:Wikipedia Signpost/2007-05-14/Committed identity.) --Coppertwig (talk) 19:59, 26 January 2008 (UTC)[reply]

This article is useless, since it lacks … a real-world example … for humans.[edit]

How would such an exchange actually look?
In human words.
— 81.173.138.89 (talk) 19:28, 21 December 2014 (UTC)[reply]

There is a rock/paper/scissors example in the intro, but it isn't really comprehensible currently. I'll try to rewrite it. — J D (talk) 14:17, 29 June 2015 (UTC)[reply]

I deleted the rock/paper/scissors example from the intro and replaced it with a simple analogy, and I rewrote the first section of the article (coin flipping) so that it is intelligible to a general audience. Success? — J D (talk) 14:43, 29 June 2015 (UTC)[reply]

Non-constructive (misleading?) sentence?[edit]

This sentence seems out-of-place:

This scheme isn't perfectly concealing as someone could find the commitment if he manages to solve the discrete logarithm problem.

If someone did solve that problem, the entire internet would break - and there's no suggestion that someone could find that solution anytime soon as far as I know? — Preceding unsigned comment added by 2001:8000:1A99:9A00:CC32:4655:2CD0:1A1B (talk) 13:06, 16 February 2018 (UTC)[reply]

It's not out-of-place: the problem with solving the discrete logarithm is that all known algorithms are slow, not that there are no known algorithms. Perfectly concealing means concealing against adversaries even with unbounded computational resources. (This is discussed at several places in the article.) --JBL (talk) 18:27, 16 February 2018 (UTC)[reply]

Will it ever be fixed?[edit]

≈≈ ₯₯°₯₯ We never know... ₯₯°₯₯ ≈≈ ∞

Finnh54 (talk) 11:41, 6 June 2016 (UTC) Finnh54 (talk) 11:41, 6 June 2016 (UTC)[reply]