2
$\begingroup$

I found there are two perplexing and related concept "Collision Resistance" and "Computation Binding in Commitment" in cryptography. I found the wikipedia's explanation is confusing. And no resources clarify their difference

Especially, I found I can't differentiate the two concepts' common ideas which is given certain inputs, there is no more than one output for a particular Hash function.

$\endgroup$
4
  • 5
    $\begingroup$ Your answer should be a part of your question so that you can ask for clarification of your understanding instead of a task-based question that triggers many that this is HW. $\endgroup$
    – kelalaka
    Commented Feb 8, 2022 at 16:12
  • 3
    $\begingroup$ This is obviously homework or test question. @Sheldon, you can edit your question (while there is still time prior to closure my a moderator) to convert it: 1) to a question instead of an assignment statement; and 2) to overtly call out what you see as the synonymous portions and the semantically/meaning nonoverlapping portions of the 2 terms, especially focusing on those aspects that you find perplexing, asking us to sort out the overlap that you already itemized and sort out the nonoverlap that you already itemized. We ponder your ?-words' finer points, not do 100% of the work for you. $\endgroup$ Commented Feb 8, 2022 at 19:06
  • 1
    $\begingroup$ Thank you @AndreasZUERCHER, I will do it $\endgroup$
    – Sheldon
    Commented Feb 9, 2022 at 3:06
  • $\begingroup$ Thank you @kelalaka, I will do it $\endgroup$
    – Sheldon
    Commented Feb 9, 2022 at 3:06

2 Answers 2

1
$\begingroup$

They are related but according to the adversary and the scheme;

Hash commits

  • If you are malicious and make a hash commitment. then $commit = H(c)$ then you may seek a collision of two commits $c_1$ and $c_2$ such that $commit = H(c_1) = H(c_2)$. This can be easy with MD5 and SHA-1 but hard with SHA-2, SHA-3, BLAKE2, etc.

    You may be a secretary and give $c_1$ to your boss to commit and later claim that the commit $c_2$ where your advantage on $c_2$ is higher than $c_1$.

  • If you are malicious and someone gave you a hash commitment. $commit = H(c)$ and you want to have an advantage, then you have to see another $c'$ such that $commit = H(c) = H(c')$. This is the second pre-image attack on the hash functions.

Keyed Hash Commits

If one uses a key $k$ to commit like $commit = HMAC(k,c)$ then the collision resistance of the hash function is no more problem since HMAC doesn't rely on the collision resistance of the underlying hash function, only PRF is enough.

  • If you are malicious and make a keyed hash commitment. Then again collision; you need to find two messages that have the same HMAC value under the same key.

  • If you are malicious and someone gave you a hash commitment. This time your attack is brute-forcing the key then finding the second-pre-image under the same key.

$\endgroup$
0
$\begingroup$

According to Wikipedia:

Collision Resistance:

a property of cryptographic hash functions: a hash function H is collision-resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b where a≠b but H(a) =H(b).

Commitment Binding
Let open be chosen from a set of size $2^k$ i.e., it can be represented as a k bit string, and let $\text { Commit }_{k}$ 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 non-uniform probabilistic polynomial time algorithms that output and of increasing length k, the probability that and $x \neq x^{\prime}$ and $\operatorname{Commit}_{k}(x$, open $)=\operatorname{Commit}_{k}\left(x^{\prime}\right.$, open $\left.^{\prime}\right)$ is a negligible function in k.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.