Commitment scheme: Difference between revisions

Revision as of 21:45, 15 June 2023

Revision as of 04:09, 5 July 2023

Line 108:

===Bit-commitment from any one-way permutation===

One can create a bit-commitment scheme from any [[one-way function]] that is [[Injective function|injective]]. The scheme relies on the fact that every one-way function can be modified (via the [[Goldreich-Levin theorem]]) to possess a computationally [[hard-core predicate]] (while retaining the injective property).

Let ''f'' be an injective one-way function, with ''h'' a hard-core predicate. Then to commit to a bit ''b'' Alice picks a random input ''x'' and sends the triple

Line 138:

This scheme isn't perfectly concealing as someone could find the commitment if he manages to solve the [[discrete logarithm problem]]. In fact, this scheme isn't hiding at all with respect to the standard hiding game, where an adversary should be unable to guess which of two messages he chose were committed to - similar to the [[IND-CPA]] game. One consequence of this is that if the space of possible values of ''x'' is small, then an attacker could simply try them all and the commitment would not be hiding.

A better example of a perfectly binding commitment scheme is one where the commitment is the encryption of ''x'' under a [[semantically secure]], public-key encryption scheme with perfect completeness, and the decommitment is the string of random bits used to encrypt ''x''. An example of an information-theoretically hiding commitment scheme is the Pedersen commitment scheme,<ref name="Pedersen pp. 129–140">{{cite book | last=Pedersen | first=Torben Pryds | title=Advances in Cryptology —– CRYPTO ’91 | chapter=Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing | publisher=Springer Berlin Heidelberg | publication-place=Berlin, Heidelberg | isbn=978-3-540-55188-1 | doi=10.1007/3-540-46766-1_9 | pages=129–140}}</ref> which is computationally binding under the discrete logarithm assumption.

<ref name="metere2017automated" >{{cite conference

| title = Automated cryptographic analysis of the pedersen commitment scheme

Line 271:

* [[Web of trust]]

* [[Zerocoin]]

*[[Anagram#Establishment_of_priorityEstablishment of priority|Anagrams]] Used by Natural Philosophers to establish priority of a discovery without revealing it to others

==References==