In this problem Here I am given 2 hash families and I need to prove the universality of the double hash, but I am stuck as to how to prove this. I know the properties of an epsilon-universal family is that the probability of collision is at most epsilon, but how could I relate this to prove the universality of the double hash?

  • $\begingroup$ Please credit the source of all copied material. Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX). $\endgroup$ – D.W. Aug 11 '20 at 19:10
  • $\begingroup$ We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. You might need to spend some more time trying to prove it. Often starting with the definitions is useful. The triangle inequality might also be helpful. $\endgroup$ – D.W. Aug 11 '20 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy