Errata

page 153.  Definition.  We should never refer a function f satisfying Omega(X^a) = f(X) = O(X^b) as exponential.  Rather we should always take care to say that it is exponential in the bit size of X. Similar considerations hold for functions that are polynomial in the bit size of X.  

page 199.  In the second paragraph right after the first displayed equation, the sentence should read, “The quantity A, together with the public parameters p and g, form Samantha’s public verification key.”

page 238.  The notation Pr (X=x) is not explained.  It is an abuse of notation for the probability of the event {omega | X(omega) = x}.

page 264.  Warning: The definition of perfect secrecy is not consistent with some other books.  For example, Katz and Lindell require the given identity to hold for all distributions over the message space.

page 266. Prop. 5.55. A more intuitive notation for C^+ might be M^+, because C is generally used to denote the space of cipher texts.

page 270.  The Property H3 is incorrect.  First of all, the elements x_{ij} should all be distinct.  Second, the formula should read Pr(X=x_{ij}) = Pr(Y = Z_i) Pr(Z_i=x_{ij}).  (Using the incorrect property as stated in the text, we can construct counterexamples when the random variables Y and Z_i are not independent.  For example let Y, Z0, Z1 be (dependent) binary choices given by a single toss of an unbiased coin.  Then H(X) = 1, but the right hand side of the entropy formula evaluates to 2.  We cannot get two bits of entropy out of a single toss.)

page 296. Exercise. 5.45 (b). Warning: Perfect secrecy depends on what happens for all c.