Content deleted Content added
Line 63:
Let ''open'' be chosen from a set of size <math>2^k</math>, i.e., it can be represented as a ''k'' bit string, and let <math>\text{Commit}_k</math> be the corresponding commitment scheme. As the size of ''k'' determines the security of the commitment scheme it is called the [[security parameter]].
Then for all [[Uniformity (complexity)|non-uniform]] [[PP (complexity)|probabilistic polynomial time algorithms]] that output <math>x,x'</math> and <math>open, open'</math> of increasing length ''k'', the probability that <math>x \neq x'</math> and <math>\text{Commit}_k(x,open)=\text{Commit}_k(x',open')</math> is a [[negligible function]] in ''k''.
This is a form of [[asymptotic analysis]]. It is also possible to state the same requirement using [[concrete security]]: A commitment scheme ''Commit'' is <math>(t,\epsilon)</math> secure, if for all algorithms that run in time ''t'' and output <math>x,x',open,open'</math> the probability that <math>x \neq x'</math> and <math>\text{Commit}(x,open)=\text{Commit}(x',open')</math> is at most <math>\epsilon</math>.
| |||