Chapter 10
Reinforcement
Problem R-10.4
What is the policy that Alice is using to determine which keys she fully trusts, partially
trusts, and doesn’t trust in her web of trust, illustrated in Figure 10.5?
Problem R-10.5
What is the solution to the CAPTCHA in Figure 10.8?
Problem R-10.10
A spammer named Richard has bribed an ISP official $1,000 to let him send out as many
spam emails as he wants and he has no other costs. The conversion rate for his spam is
the usual 0.001% and he gets $10 for each converted response. What is Richard’s expected
profit or loss if he sends out 1,000 emails, 100,000 emails, 1,000,000 emails, or 100,000,000
emails?
Problem R-10.11
In the previous exercise, how many emails does Richard need to send in order to be at an
expected break-even point, that is, the point where his expected profit is zero?
Problem R-10.20
In the ThreeBallot voting system, if there are 23 candidates running for the same office, how
many bubbles does someone have to fill in to correctly vote for their preferred candidate?
Creativity
Problem C-10.3
Alice has a table of famous 19th-century people and their exact ages at death, for which she
wants to anonymize using generalization, dividing ages into ranges, such as “46.35–48.08,”
so that each age range has at least 40, but no more than 80, people in it. Describe an
efficient algorithm for Alice to perform this generalization, assuming there are no more
than 40 people in Alice’s table with the same exact age at death.
Problem C-10.5
Explain why a DNS cache poisoning attack can compromise DKIM but not S/MIME.
Describe how DKIM could be modified to defend against DNS based attacks.
Problem C-10.6
A spammer named Richard pays people in Elbonia $0.01 for each CAPTCHA they solve,
which he can then use to create an email account that can send out 10,000 spam emails
before it is shut down. The conversion rate for his spam is the standard 0.001% and he
has no other expenses other than the money he pays his employees in Elbonia. What is
the formula for Richard to determine his expected profit in terms of N, the number of
recipients, and R, the dollar return on each converted responder?
Solution Since Richard’s operational costs are a function of N, his formula is
Problem C-10.10
Describe a rule change that would allow sellers and buyers in an online auction to still
provide feedback on their experience but would prevent them from holding their feedback
for ransom in response to first getting a positive feedback from the other party.
40
Problem C-10.11
Some social networking web sites provide mechanisms for users to determine the GPS coor-
dinates of where their friends are located at any given moment. Describe a generalization
scheme that would anonymize this information using disjoint rectangles so that any reported
rectangular region as a “location” always has at least kpeople in it, for some security pa-
rameter k.
41