Difference between computationally and perfectly hiding (binding) properties

Question

I am new to Cryptography and has a trouble of understanding the difference between perfect and computationally hiding (binding) properties of a commitment scheme. I also would like to ask what does it mean to be a computationally bounded (unbounded) adversary? I tried to look at these through Google search but none provides a clear difference between these terminologies.

Answer 1

Generally, in cryptography and in your question we say it has perfect hiding it means that if any adversary with any computation capability tries even forever cannot understand what you have hid. It means that even if he test all the possible comited values and all key, he cannot even decide which one is more probable and all of them are equally possible for him.

On the other hand, computationally hiding means that you must assume that your adversary cannot try forever. He has limitations on his computational resources and he has limited time to decide what you have hid. But you must proof with this limitation he cannot understand or guess what you hid (except with negligible probability).

Computationally bounded adversary means that your adversary cannot try forever. He has limitations on his computational resources. He may parallelize computers or ... But we usually consider this limitation as being polynomial-time. Because for example he can at most parallelize some certain number of processors. All the helps he can make to himself is considered as a coefficient or fixed power. So, if you can decide any of your adversaries can break your system (or find out what you have comited) in a limited polynomial form time, your scheme is not considered secure. But if any adversary needs more time it means that your scheme is computationally (=against computational adversaries) secure.

** This polynomial to compute computational complexity is usually in terms of number of bits of the keys (or anything the adversary must determine). Longer keys need more computations and are harder for adversary to guess.

Answer 2

The words perfect and unbounded refer to basically the same concept*. If something has perfect security with respect to property X, then an adversary that is computationally unbounded can not violate property X. Computationally unbounded means that the adversary is allowed to run for an unspecified amount of time, in particular, $O(2^\kappa)$ for security parameter $\kappa$.

For example, we can ask if AES is a secure block cipher (permutation). What we could do is pick a random key $k\in\{0,1\}^\kappa$, encrypt the messages 1,2,3,4,... and give the results to the adversary.

If we bound the running time of the adversary to be $poly(\kappa)=O(\kappa^c)$ for some constant $c$, the answer is yes, we think AES is indistinguishable from a truly random permutation from $\{0,1\}^\kappa $ to $\{0,1\}^\kappa$.

However, if we allow the adversary to be computationally unbounded then there is a simple attack that can break AES. Say the adversary see $c_i=Enc(k,i)$ for $i=1,2,...,100$. Then with overwhelming probability, there is only one AES key $k$ that results in these $c_i$ values. As such, an unbounded adversary can simply try all $k'\in\{0,1\}^\kappa$ and check which results in the same ciphertexts $c_i$. Since there is likely only one such key the adversary will find it. This is a "brute force" type of adversary.

Note that if we instead used a one-time pad, then an unbounded adversary would not be able to break the encryption.

Now let us answer your question. Perfectly hiding means that an unbounded adversary can not learn any information about the value being committed to. One-time pad is perfectly hiding (but isn't a commitment scheme...). Hiding is a security property you care about when the adversary is the person who receives the committed values.

You can also have a computationally hiding commitment which means no adversary which has running time $poly(\kappa)$ can learn any information about the value by seeing the commitment (except with negligible probability).

Perfectly binding means that an unbounded adversary can not break a commitment and decommit it to more than one value. In other words, there must truly be only one value that the commitment can ever decommit to.

For computationally binding, then any adversary with running time $poly(\kappa)$ must have negligible probability of decommitting to more than one value.

Say our commitment scheme the classic "random oracle" approach where you commit to $x$ as $c=H(x || r)$ where $r\gets\{0,1\}^\kappa$ is a random value. Then this scheme is not perfectly binding. An unbounded adversary could pick some $x'$ and simply try $O(2^\kappa)$ other values of $r'$ until they get $c=H(x'||r')$. They could then "decommit" using either $(x||r)$ or $(x'||r')$. However, this scheme is computationally binding since finding such an $r'$ value requires $O(2^\kappa)$. Note, I'm ignoring some issues with the birthday bound.

There exist commitment schemes that have perfect bind or hiding but not both.

Edit*: as Maeher pointed out, there is a way for a commitment to be secure against an unbounded adversary while still not being perfectly secure. For this we introduce the statistical security parameter $\lambda$. A property X is said to have $\lambda$ bits of statistically security if when you run the (commitment) algorithm there is at most a $1/2^\lambda$ probability that property X does not hold (unconditionally).

For example, let us have some commitment scheme $C(x;r)$ which takes a value $x$ and a random tape $r$ as input. It just so happens that if $r=42$ the scheme completely falls apart. However, if we sample $r\gets \{0,1\}^\lambda$, then the probability that $r=42$ is $1/2^\lambda$ and this scheme can still be considered statistically secure. Importantly, the probability that the scheme fails to have the desired property is a function of the random tape $r$ and not of the running time of the adversary.