Cryptography Lecture 12: Probability Problems and Birthday Paradox
Explore probability problems related to fixed n-bit values, union bounds, and the birthday paradox in cryptography lecture 12. Understand the likelihood of collisions and security implications. Finish with a discussion on authenticated encryption and secure sessions.
Uploaded on | 1 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Cryptography Lecture 12
Problems 1 Let t be a fixed n-bit value. If we randomly select an n-bit value x. What is the probability of x = t? 2-n
Problems 1 Union bound: Pr[E1 V E2] Pr[E1] + Pr[E2] E1 V E2: disjunction (E1 or E2 occurs) What is the probability that a random n-bit value y is equal to any of q n-bit different values? = Pr[y = first value] + Pr[ y = second value] + Pr[y = q-th value] = q/2n
Problems 1 Union bound: Pr[E1 V E2] Pr[E1] + Pr[E2] E1 V E2: disjunction (E1 or E2 occurs) What is the probability that a random n-bit value y is equal to any of q n-bit different values? What if these q values are randomly selected? Simple q/2n Remember when this is used? (Our first CPA secure scheme using PRF! Page 83)
Problem 2 (Birthday problem) If q people are in a classroom, what is the probability that two of them have the same birthday? (Assume birthdays are uniformly and independently distributed among the 365 days.) Equivalently, if we choose q elements y1, y2, , yq uniformly form a set of N, what is the probability there exist distinct i, j with yi=yi? This event is called a collision. Let s write coll(q, N) to denote the probability of this event.
Problem 2 It can be proven (book pp. 543 and 544) q(q-1)/4N coll(q, N) q2/2N Conclusion is important Proofs are standard (although not required by the exam, you are encouraged to go over them. It is a good exercise, indeed.) Very tight bound, mathematically beautiful Can be understood in two ways When N is small, coll is high! (so that you can attack!) When N is large, coll is negligible! (so that you cannot attack)
The remaining lecture Finish authenticated encryption and secure sessions
