Why randomness space must be significantly larger than the commitment space |R|>|C|? the picture is from https://youtu.be/IkNZWJFcfcU?t=236
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
For the hiding property we require that the commitment value provides no information about the message. In particular we hope that for any given message $m$ it is possible for $H(m,r)$ to take all possible values in $C$ (otherwise one could exclude some messages as corresponding to some commitments). If $H$ behaves like a random function, then it unlikely to have this surjective property unless $|R|>|C|\log|C|$.
More powerfully we probably want the values of $H(m,r)$ for any fixed $m$ to be distributed uniformly across the values of $C$.
Note that these are information theoretic "zero knowledge" requirements rather than complexity/computation bounded requirements.
-
1$\begingroup$ For any secret value the random blinding of a Pedersen commitment covers the whole image space uniformly. It can do this because the random blinding is a random permutation rather than a random function. $\endgroup$– Daniel SFeb 26, 2022 at 14:05
-
$\begingroup$ "In particular we hope that for any given message $m$ it is possible for $H(m,r)$ to take all possible values in $C$"; while this would be sufficient, this is not actually necessary. What is necessary is that any plausible adversary be unable to obtain any information about $m$ from the commitment; however, because computationally unbounded adversaries are not plausible, we can consider lesser goals (such as deducing information about $m$ computationally infeasible..) $\endgroup$– ponchoFeb 26, 2022 at 17:26
-
$\begingroup$ @poncho: There are three levels of hiding in commitment schemes perfect, statistical, and computational. The lecturer is tacitly requiring statistical hiding (hence my reference to information theory) and the requirement $|R|\gg |C|$ is necessary to meet this. $\endgroup$– Daniel SFeb 26, 2022 at 17:47