WIXLIB

61. Constructing a formal security model and defining what it means for a given cryptographicdesign to be secure; and2. Demonstrating that the existence of an adversary capable of efficiently breaking the design’ssecurity is either impossible in the model or it can be transformed into an algorithm solving a“computationally hard” problem, i.e., a problem that we assume infeasible to be solved.The second item points to an area of interest for us called computational complexity . Thisdiscipline aims to answer questions such as “How many steps are necessary to solve a problem?” or“How much space is required to find a solution to a problem?” One of the objectives of computationalcomplexity is to calculate the time required to find a solution to a problem. For example, one ofthe fundamental open problems in computer science and mathematics relates to the classes P andN P . P is the set of problems that can be solved in polynomial-time and N P is the set of problemsfor which a candidate solution can be verified in polynomial-time. Although significant effort hasbeen devoted to understanding the relationship between these two classes, it is still unknown ifP 6 N P . It is known however, that many proofs of security would imply P 6 N P . In orderto understand this, observe the N P -nature of cryptography; namely that secret keys play the roleof the candidate solutions in a suitable N P problem. Unfortunately, the fact that P 6 N P isnot helpful in cryptographic security proofs. Such applications ask for average hardness; that is, arandom instance of a problem should be computationally hard, while N P problems may be hardonly in the worst-case.An important tool that assists in the classification of computational problems is the concept ofreduction. Suppose there are two problems A and B and an algorithm α that solves A with oracleaccess to B, written αB . We can appropriately define a pre-order 1 over all problems so A B ifand only if there is an algorithm α where αB solves A. This is a reduction.Intuitively, A B implies that A cannot be substantially harder than B. Say, A is a well-knownhard problem, such as the factoring problem or the discrete logarithm problem (that we will definein the sequel), and B corresponds to breaking the security of our cryptographic construction. IfA is acceptably hard and we can produce a reduction as is specified above, we can assume ourconstruction is provably secure.Despite the fact that reductions provide little “real” proof of security, they are acceptable givenour general inability to construct a lower bound on the difficulty of computational problems.2Mathematical ReviewHere we give a quick review of algebra, number theory, and probability. Further reviews will beprovided as necessary in subsequent sections. 22.1Algebra and Number TheoryGroupsDefinition 2.1.1. A group (G, ) is a set G together with a binary operation satisfying thefollowing conditions: G is closed under : for all g, h G, g h G; The operation is associative: for all g, h, G, g (h ) (g h) G; G contains an identity element e such that g e e g g for all g G;1Apre-order is a reflexive, transitive relation.more mathematical review, see [1].2 For[Draft of November 23, 2016]

2.1Algebra and Number Theory7 G is closed under inversion: for all g G, there exists g 1 G such that g g 1 g 1 g e.Formally, a group is denoted by an ordered pair (G, ). We will write G when is understood.Definition 2.1.2. A group G is called Abelian if for all g, h G, g h h g.Theorem 2.1.1. If G is an Abelian group under , then G contains exactly one identity elementand every element of G has a unique inverse.Definition 2.1.3. In a finite group G, the order of G is the size or number of elements in thegroup, denoted #G or G .Definition 2.1.4. For a group G and g G, define the order of g to be the smallest positiveinteger i such that g i e, or equivalently, g g · · · g e. We denote the order of g by ord(g).{z} i timesTheorem 2.1.2 (Lagrange). In a finite group, the order of any element divides the size of thegroup.Definition 2.1.5. If there is some element g G such that ord(g) #G, then g generates G andwe call G a cyclic group. We write G hgi.Example. Consider Z 5 Z5 {0}. This is a cyclic group under multiplication modulo 5. Our goalis to find g Z 5 such that ord(g) #Z 5 4 and therefore hgi Z 5 . Clearly h1i 6 Z 5 , so let us try2:20 1 mod 5, 21 2 mod 5, 22 4 mod 5, 23 3 mod 5, and 24 1 mod 5.Since h2i {1, 2, 3, 4} and 2 has order 4, 2 generators Z 5 .It is possible for multiple elements to generate the group, so let us now try 3. By Lagrange,ord(3) 4. From our previous calculations, 23 3 mod 5, so ord(23 ) ord(3). Then 3ord(3) 23ord(3) 1 mod 5 and 3ord(3) ord(2) mod 4. Since 3 and 4 are relatively prime, ord(3) 4. Thus3 is another generator of Z 5 .By the same argument, we can show 4 is not a generator. From the above, 22 4 mod 5, soord(22 ) ord(4). We know that 2 (the exponent in 22 ) divides 4, therefore gcd(2, 4) divides 4.Moreover, ord(4) 4/ gcd(2, 4) 2. This implies #h4i 2, so 4 is not a generator: h4i {1, 4}.Rings and FieldsDefinition 2.1.6. A (commutative) ring R is a set together with two binary operations and such that (R, ) is an Abelian group; The operation is associative: (r s) t r (s t) for all r, s, t R; The distributive law holds in R: r (s t) r s r t and (r s) t r t s t for allr, s, t R; The operation commutes: r s s r for all r, s R; and R contains an identity if there is an element 1 R such that 1 r r 1 r for all r R.Simply put, a commutative ring is an Abelian group without inverses. Not all rings contain 1, sothe last condition is not absolute.Example. Z is a ring under the usual addition and multiplication.Example. Zn is a ring under addition and multiplication modulo n.[Draft of November 23, 2016]

2.1Algebra and Number Theory8Definition 2.1.7. A field F is a set together with two binary operations and such that (F, ) is an Abelian group with identity 0; (F {0}, ) is an Abelian group with identity 1 and the distributive law holds.Example. Q, R, and C are all fields under the usual addition and multiplication.Example. For any prime p, Zp is a field under addition and multiplication modulo p.Definition 2.1.8. Let p be a prime. Then Zp is a finite field , denoted Fp .Chinese Remainder TheoremDefinition 2.1.9. We denote congruence relationships over the integers by a b mod n if andonly if n (a b).Theorem 2.1.3 (Chinese Remainder Theorem). Let m1 , . . . , mk be pairwise relatively primepositive integers and let c1 , . . . , ck be arbitrary integers. Then there exists an integer x such thatx ci mod mi0for all i 1, . . . , k. Moreover,Q any integer x is also a solution to these congruences if and only if0x x mod M where M mi for i 1, . . . , k.QProof. Let M mi for i 1, . . . , k. Define m0i M/mi . All the mi s are pairwise relatively0prime, so gcd(mi , mi ) 1 for all i. Let ui (m0i ) 1 mod mi and wi m0i ui . By construction then,wi 1 mod mi and wi 0 mod mj when i 6 j. This gives us wi δij mod mj where(1, if i jδij 0, if i 6 j.Letting x Pwi ci for i 1, . . . , k, we seex kXδij ci cj mod mjj 1as desired.Remark. The Chinese Remainder Theorem implies the group isomorphismZ n Z pe1 . . . Z pemm ,1given by a mod n 7 (a modprimes pi .pe11 , . . . , amodpemm ),where n pe11 · · · pemm for integers ei and distinctExample. Historically, the Chinese used this theorem to count soldiers. After a battle, the soldierswould line up in rows of (for example) three, then in rows of five, and then in rows of seven. Bycounting the remaining soldiers after each formation, the commanders could quickly determine thetotal number of men and therefore determine their losses.Say there are fewer than 100 soldiers. After lining up 3 soldiers in each row, 1 soldier remains.After standing 5 in a row, 2 soldiers remain, and after standing 7 in a row, 6 remain. We want tocalculate the exact number of soldiers.[Draft of November 23, 2016]

2.2Discrete Probability9Let x represent the total. Thenx 1 mod 3x 2 mod 5x 6 mod 7.We compute M 3 · 5 · 7 105, and m01 35, m02 21, m03 15. Computing inverses now, we haveu1 35 1 2 mod 3u2 21 1 1 mod 5u3 15 1 1 mod 7Then w1 70, w2 21, w3 15, making x w1 c1 w2 c2 w3 c3 70(1) 21(2) 15(6) 97 mod 105. Thus there are 97 soldiers.2.2Discrete ProbabilityDefinition 2.2.1. A discrete probability distribution D over a set [D] is specified as ProbD [u] [0, 1] for all u [D]P u D ProbD [u] 1.The set [D] is called the support of D.Example (Succeeding by Repetition). Consider an experiment where the probability of successis p. Suppose the experiment is repeated n times; we want to bound the probability that all n trialsfail. Since each trial is independent of the next, the probability of n failures is (1 p)n . Recall that1 x e x for all x. By letting x p and raising both sides to the nth power, we obtain the upperbound (1 p)n e pn . ThenProb[At least 1 success] 1 Prob[All fail] 1 e pn .If p is fixed, the probability that all trials fail drops exponentially according to the number ofrepetitions n.Example (Balls and Boxes). Consider an experiment with n boxes and k balls, each of a differentcolor. Each ball is thrown into a box at random. We define a collision to be the event that 2 differentcolored balls land in the same box. We want to calculate the probability of a collision. In a situationlike this, it is often easier to calculate the probability of the complementary event:ProbD [No collision] k 1Y n j n(n 1) · · · (n k 1) .nknj 0Using again the fact that 1 x e x for all x, we havek 1Y j 0n jn k 1Y j 1j1 n k 1Ye j/n e k(k 1)/2n .j 1Since Prob[Collision] 1 Prob[No collision],ProbD [Collision] 1 e k(k 1)/2n .[Draft of November 23, 2016]

2.3Conditional Probability10Example (The Birthday Paradox). The Birthday Paradox is a classic problem utilizing theprevious scheme. We want to know how many people must be in a room for there to be at least a 50%chance that two people have the same birthday (a collision). Let n 365 and assume that people’sbirthdays are uniformly distributed over the days of the year. If we want ProbD [Collision] 1/2,then11 e k(k 1)/2n 21 k(k 1)/2ne 2k(k 1)/2ne 2k(k 1) ln 22nk2 ln 22n k 2n ln 2So if there are more than 23 people in a room, there is over a 50% chance that two people share thesame birthday. This seems a bit counterintuitive; hence the name “paradox”.Example (Binomial Distribution). A binomial trial is an experiment with only two possibleoutcomes: success and failure. Let [D] {0, 1, . . . , n} and the probability of one success be p, thenthe binomial distribution is the probability of u successes in a sequence of n independent trials: n uProbD [u] p (1 p)n u .uDefinition 2.2.2. A subset A [D] denotes an event. The probability of A isXProbD [A] ProbD [u].u AIt is also possible to prove various statements about set theoretical operations defined betweenevents, such as unions and intersections. For example, if A, B [D], we haveProbD [A B] ProbD [A] ProbD [B] ProbD [A B].This is called the inclusion-exclusion principal .2.3Conditional ProbabilityDefinition 2.3.1. Let A and B be two events. The probability of A occurring, given that B hasalready occurred is called a conditional probability . This is given byProbD [A B] ProbD [A B].ProbD [B]The following theorem is useful for computing conditional probabilities.Theorem 2.3.1 (Bayes). For two events A and B,ProbD [B A] ProbD [A B] · ProbD [B].ProbD [A]Moreover, if D1 , . . . , Dn is a partition of disjoint events of [D] such that [D] then for any events A and B,ProbD [A B] · ProbD [B].i 1 ProbD [A Di ] · ProbD [Di ]ProbD [B A] Pn[Draft of November 23, 2016]SDi for 1 i n,

2.4Random Variables11Let B denote the complement of an event: B [D] \ B. Bayes’ theorem suggestsProbD [B A] ProbD [A B] · ProbD [B].ProbD [A B] · ProbD [B] ProbD [A B] · ProbD [B]Example. Here we see an application of Bayes’ Theorem. Let D be a probability distribution overa given population and let the event S correspond to the subset of the population sick with a certaindisease. Suppose there is a medical test that checks for the disease and define T to be the eventthat an individual selected from the population tests positive.The prevalence of the disease is ProbD [S] 1%, the chances of a successful test areProbD [T S] 99%, and the probability of an inaccurate test is ProbD [T S] 5%. We want tofind the probability that a certain individual is sick, given that the test result is positive. A commonmistake is to claim that the probability is 99%- the success rate of the test. This is false because itfails to take into account that we already know the person tested positive. Using Bayes’ theorem,we can account for this information and computeProbD [T S] · ProbD [S]ProbD [T S] · ProbD [S] ProbD [T S] · ProbD [S](0.99)(0.01) (0.99)(0.01) (0.05)(1 0.01)1 .6ProbD [S T] This might seem unreasonable, but because the disease is so uncommon, a positive test is more likelyto occur from an inaccurate test than from the actual sickness.2.4Random VariablesDefinition 2.4.1. For a probability distribution D, we define a random variable X to be afunctionX : [D] R. For any x R, we use the notationXProb[X x] ProbD [u].X(u) xWe say that a random variable X is distributed according to D if X : [D] [D] is the identityfunction. We denote this byXProb [X x] ProbD [u].X DX(u) xDefinition 2.4.2. For any probability distribution D with random variable X, its expectation isXE[X] xProb[X x].x RDefinition 2.4.3. The variance of a discrete random variable X measures the spread, or variabilityof a distribution. It is defined byVar[X] E[X 2 ] E[X]2 .[Draft of November 23, 2016]

2.5Tails of Probability Distributions2.512Tails of Probability DistributionsWhen analyzing random procedures, we often want to estimate the bounds on the tails of a probability distribution. The term “tails” refers to the extremities of the graphical representation of aprobability distribution, where the distribution deviates from the mean. The following theorems willbe helpful.Theorem 2.5.1 (Markov’s Inequality). Let X be a random variable that takes only nonnegativereal values. Then for any t 0,E[X].Prob[X t] tTheorem 2.5.2 (Chebyshev’s Inequality). Let X be a random variable. For any t 0 we haveProb[ X E(X) t] Var[X].t2Theorem 2.5.3 (Chernoff ’s Bound). Let X1 , . . . , Xn be independent random variables taking values in {0, 1} with Prob[Xi 1] pi . Then" n#" n# µXXeδ µδ 2 /2ProbXi (1 δ)µ eandProbXi (1 δ)µ (1 δ)1 δi 1i 1where µ Ppi and δ (0, 1].Here µ is the expectation and (1 δ)µ and (1 δ)µ are the tails.Example (Guessing with a Majority). Suppose there is an oracle that answers questions withYes or No, and answers questions correctly with probability 1/2 α. Say we ask the oracle nquestions and let Xi be a random variable according to(1, oracle answers the i th query correctlyXi 0, otherwise.If we define a failure as receiving fewer correct answers than incorrect answers, the probability offailing is#" nhXninProb[Failure] Prob # of correct answers . ProbXi 22i 1Here we apply Chernoff’s bound by setting n/2 (1 δ)µ. Then" n#X2ProbXi (1 δ)µ e µδ /2 .i 1Noting that µ (1/2 α)n, we can solve for δ.n (1 δ)µ2 n1 (1 δ) α n22αδ 1/2 αTo estimate the probability of a failure, we substitute this value of δ into (1).2Prob[Failure] e αn/(1 2α)[Draft of November 23, 2016].(1)

2.6Statistical Distance13This implies that if the oracle has bias α, we can typically expose the bias after a sufficient numberof repetitions n. Because of this, the probability of failing drops exponentially depending on thedegree of the bias and the number of trials. If we want the probability of failing to fall below someε, we can find a suitable lower bound on n.e α2n/(1 2α) ε2 α n ln(ε)(1 2α)n α 2 1(1 2α) lnεSo by taking n large enough, we can guarantee that the probability of failing is sufficiently low.2.6Statistical DistanceDefinition 2.6.1. Let X and Y be random variables distributed according to D1 and D2 respectively and let V X([D1 ]) Y ([D2 ]). We define the statistical distance by [X, Y ] 1 XProb [X u] Prob [Y u] .X D1Y D22u VFigure 1 illustrates the statistical distance between two random variables X and Y . The dottedcurve represents the distribution of X over D1 and the black curve corresponds to Y over D2 . Bydefinition, the sum of the probabilities over the support set is 1, so the area below each curve is 1.Half the sum of the shaded areas represents the statistical distance between X and Y . Because thestriped area equals the

1.2 Overview of Cryptography The previous example illustrates the research process of modern cryptography which can be epito-mized as follows. 1. Identify important problems in need of cryptographic solutions. These are typically problems of trust between two or more parties. As a rule of thumb, if the problem can be solved by