CS 70 Discrete Mathematics and Probability TheoryFall 2011 Rao Rough Outline Lecture 1The reader shold be aware that thes notes have been subject to minimal if any editing and should notbe distributed.This course is about formal analysis in the context of discrete math and probability and its applications incomputer science.Today, we highlight some of the applications and hint at the mathematical ideas that we will use to derivethese applications.Secret sharing, coding theory.Consider the problem of shaing (parts of) a secret number with three people, where any two can figure outthe number, and any one person knows nothing about the number.Let me describe a secret sharing scheme using a sequence of examples.• Secret: 2. Shares: 2, 4,6.• Secret: 3. Shares: 1000, 1003, 1006.• Secret: 5. Shares: 41, 46,51.This is an old “guess the pattern” problem, where the patterns consist of an arithmetic sequence: add thesecret number every time.Now, guess the secret given the following shares.• Shares: 2, *,6. What is the secret?• Shares: *, 8, 12. What is the secret?• Shares: *,8,*. What is the secret?From even the first example above, where the secret is 2, it becomes clear that the order of the shares matter.That is, the shares correspond to share 1, share 2, and share 3. With this, it is easy to see that the secondexample’s secret is 4.In the last example, with this scheme, one cannot determine the secret at all.How can we generalize this scheme to share the secret among more people, have the minimum sized set ofknowing people be larger?Viewing the shares as a set of ordered pairs, E.g;, (1, 2);(2, 4);(3, 6), and associate a graph or functionbetween share number and share value, one sees that the secret is encoded as the slope of a line. We havethe very familiar notion that points determine a line. Moreover, one point tells is nothing about the slopeof a line.CS 70, Fall 2011, Rough Outline Lecture 1 1So, to generalize to having more shares, one can simply choose more points on the line. Any two suffice toreconstruct the line.How about needing a larger group to collaborate to reconstruct the secret? Here, we will use the simply usefunctions which are higher degree polynomials. For example, three points uniquely determine a parabola,or any k points determine a degree k− 1 polynomial. We can encode the secret as one of the coefficients ofthe the polynomial.Later in this course, we will see how to do this computation using integers and small numbers.This scheme is actually broadly used in communication. For example, if we have a k packet message thatwe want to send over a lossy communication channel, can we send n packets where any k of them allowus to reconstruct the original message. Here, each “sent” packet will correspond to a share of the originalmessage.A more challenging problem is a “noisy” channel, a channel that changes the contents of a packet. Here youwish to send a k packet message using n packets, and reconstruct the message of any g packets remain good.Here, we will need g to be larger than k, but can still do very well. Again, the constructions are based onproperties of polynomials! Indeed, properties that were developed in the California 10th grade curriculumfor real numbers. Here, we will use analagous properties over finite fields, as that is what computers do.Cyrptography: Public Key encryption.Since time immemorial: share codebook... secret key. Both ends need to share a codebook. A messageis sent by encoding the message using the “codebook” and then decoding the message using the same“codebook”.Diffie and Hellman devised a public key system consisting of a public key, secret key pair, a method toencode a message using the public key, and a method to decode the message using the corresponding secretkey. Rivest, Shamir, and Adleman later devised a public key scheme based on modular arithmetic. This isthe basis of modern cryptography in practice.In particular, a greatly simplified depiction of what happens when Bob wishes to send his credit card numberto Amazon.Amazon: I am Amazon; my public key is K = (N, e)!This public key is known to the world (in particular to Bob’s browser and everyone else’s browser.)Bob: y = E(x = ”5422132217861111.”, N, e) = xemod NHere, we use modular arithmetic. When we say x mod N we mean something akin to the remainder of xmod N, i.e., 13 mod 7. (In fact, we mean that the whole world only consists of 0, ..., N − 1. And N + 1mod N is simply another representation of 1 mod N. So, the mod N simply means we are in this world.The mod N will be at the end of an equation as above. )Now, an evil eavesdropper (Eve) is snooping on the router.Eve(il): See’s y.. hopefully can’t figure out x even though she knows N and e.A tiny bit of intuition of how this might work. Let’s consider an example where the encryption anddecryption are done with one prime, 7. Here, we have.Eve: for what x, is x5= 5 mod 7?CS 70, Fall 2011, Rough Outline Lecture 1 2In modular arithmetic, it is not clear how to take roots. For real numbers (or rationals) one can do somekind of binary search, but other than trying all of them it is not clear how to take the 5th root of somethingmod p.But I know (x5)5mod 7 = 1 by,Fermat’s (Little) Theorem: ap−1= 1 mod p for prime p and for a non-multiple of p.Now, with this theorem, we have that(x5)5= x25= x24x = (x6)4x mod 7Now, by Fermats theorem, we have that x6= 1 mod 7, and we have that (x5)5= 1 mod 7.(This takes a bit of belief that basic rules of arithmetic; e.g., (xa)b= xabmod p, apply to modulararithmetic.)Thus, this mathematical fact called Fermat’s Little Theorem gives us a somewhat counterintuitivedecryption method. Unfortunately, Eve can as easily figure out the decryption method as Bob when N is aprime. But, the analagous decryption method when N is the product of two unknown primes along with theanalagous theorem (Euler’s Theorem) remains the state of the deployed technology.Probability...We will cover a fair bit of probability in this class. While primarily we will cover discrete probability wewill touch on continuous probability and the connections should give you a better grasp of both.Let’s take a brief look at some examples which you will be able to formally reason about after this course.You are offered a million dollars for winning 2 consecutive games of 3 1-on-1 games of Jeapardy againstWatson (IBM’s supercomputer which happens to be very good) and me (I am
View Full Document
Unlocking...