Content deleted Content added
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 :<math>(h,f(x),b \oplus h(x))</math>
to Bob, where <math>\oplus</math> denotes XOR, ''i.e.'', bitwise addition modulo 2. To decommit, Alice simply sends ''x'' to Bob. Bob verifies by computing ''f''(''x'') and comparing to the committed value. This scheme is concealing because for Bob to recover ''b'' he must recover ''h''(''x''). Since ''h'' is a computationally hard-core predicate, recovering ''h''(''x'') from ''f''(''x'') with probability greater than one-half is as hard as inverting ''f''. Perfect binding follows from the fact that ''f'' is injective and thus ''f''(''x'') has exactly one preimage.
| |||