Content deleted Content added
m →Quantum bit commitment: Copy edit ▸ Presentation. Tags: Mobile edit Mobile app edit Android app edit App section source |
Link suggestions feature: 3 links added. Tags: Visual edit Mobile edit Mobile web edit Newcomer task Suggested: add links |
||
Line 21:
===Coin flipping===
Suppose [[Alice and Bob]] want to resolve some dispute via '''[[coin flipping]]'''. If they are physically in the same place, a typical procedure might be:
# Alice "calls" the coin flip,
Line 88:
environment that, instead of corrupting ''C'', corrupts ''R'' instead. Additionally it runs a copy of ''S''. Messages received from ''C'' are fed into ''S'', and replies from ''S'' are forwarded to ''C''.
The environment initially tells ''C'' to commit to a message ''m''. At some point in the interaction, ''S'' will commit to a value ''m′''. This message is handed to ''R'', who outputs ''m′''. Note that by assumption we have ''m' = m'' [[with high probability]]. Now in the ideal process the simulator has to come up with ''m''. But this is impossible, because at this point the commitment has not been opened yet, so the only message ''R'' can have received in the ideal process is a "receipt" message. We thus have a contradiction.
==Construction==
Line 118:
Note that since we do not know how to construct a one-way permutation from any one-way function, this section reduces the strength of the cryptographic assumption necessary to construct a bit-commitment protocol.
In 1991 [[Moni Naor]] showed how to create a bit-commitment scheme from a [[cryptographically secure pseudorandom number generator]].<ref>{{cite web|url=http://citeseer.ist.psu.edu/context/22544/0 |title=Citations: Bit Commitment using Pseudorandom Generators - Naor (ResearchIndex) |publisher=Citeseer.ist.psu.edu |access-date=2014-06-07 |url-access=registration}}</ref> The construction is as follows. If ''G'' is a pseudo-random generator such that ''G'' takes ''n'' bits to 3''n'' bits, then if Alice wants to commit to a bit ''b'':
*Bob selects a random 3''n''-bit vector ''R'' and sends ''R'' to Alice.
| |||