Content deleted Content added
Thebirdlover (talk | contribs) m Reverted 1 edit by 2405:201:5002:3916:5690:F0B7:5EC5:A27F (talk) to last revision by Cewbot |
|||
Line 96:
===Bit-commitment in the random oracle model===
Bit-commitment schemes are trivial to construct in the [[random oracle]] model. Given a [[cryptographic hash function|hash function]] H with a 3''k'' bit output, to commit the ''k''-bit message ''m'', Alice generates a random ''k'' bit string ''R'' and sends Bob H(''R'' || ''m''). The probability that any ''R′'', ''m′'' exist where ''m′'' ≠ ''m'' such that H(''R′'' || ''m′'') = H(''R'' || ''m'') is ≈ 2<sup>−''k''</sup>, but to test any guess at the message ''m'' Bob will need to make 2<sup>''k''</sup> (for an incorrect guess) or 2<sup>''k''-1</sup> (on average, for a correct guess) queries to the random oracle.<ref>{{Citation
| last = Wagner
| first = David
| |||