I am self-studying the book Intro to Algorithms 3ed by CLRS. One of the problems seems to give a piece of information that is not necessary, Problem 11-4 in the book states

Let H be class of hash functions in which each hash function h ∈ H maps the universe U of keys to {0, 1...m-1}. We say H is k-universal if, for every fixed sequence of k distinct keys {x1, x2...xk} and for any h chosen at random from H, the sequence is equally likely to be any of the m^k sequences of length k with elements drawn from {0, 1...m-1}

part d (previous parts are unrelated): suppose that Alice and Bob secretly agree on a hash function h from a 2-universal family H of hash functions. Each h ∈ H maps from a universe of keys U to Zp = {0, 1, 2...p-1}, where p is prime. Later, Alice sends a message m to Bob over the Internet, where m ∈ H. She authenticates this message to Bob by also sending an authentication tag t = h(m), and Bob checks that the pair (m,t) he receives indeed satisfies t = h(m). Suppose that an adversary intercepts (m,t) en route and tries to fool Bob by replacing the pair (m,t) with a different pair (m',t'). Argue that the probability that the adversary succeeds in fooling Bob into accepting (m', t') is at most 1/p, no matter how much computing power the adversary has, and even if the adversary knows the family of H of hash functions used.

So the best thing the adversary can do is find all h' such that h'(m) = t, then find some m', t' pair that matches as many of those h' as possible. However, since the universe H is 2-universal, that means even if the adversary has narrowed it down to the smaller set of h', for each m', the value of t' is still equally likely to be any of the p possible values. Hence, the probability of the adversary's pair m', t' matching Alice and Bob's function h is exactly 1/p, assuming that the adversary has narrowed it down at first.

However, the problem stated that p is prime. In the argument I gave, at no part did I use that fact, so either my argument is wrong, or the problem has made a somewhat unnecessary condition?

  • $\begingroup$ It's more appropriate to Cryptography SO. I think you are right (it may be useless leftover from Chinese Remainder Theorem), but I'm not cryptographer nor scientist. $\endgroup$ – Bulat Jun 27 '18 at 18:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.