Assignment 6: Lottery security design

Due Friday, April 10th, at 11:55 PM

Logistics

For this assignment, you will work in a group. This group need not be the same group you worked with for assignments 4 and 5 -- your choice. All work should be done within a single group. Cross-group collaboration -- including discussion of the merits/flaws of different hypothetical designs -- is not allowed. Peer discussion of designs will be the purpose of assignment 7.

Introduction

You have been hired by the agency that runs the state lottery to design a strategy for managing the interaction between the lottery's central office and the "lottery terminals" in stores throughout the state. Your task in this assignment is to write a memo describing your proposed design, and discussing how well your design meets the criteria set out below. You will be graded partly on your design, and partly on your analysis and critique of your own design.

How the Lottery Works

Lottery tickets are sold for $1 each and can be bought from lottery terminals that are placed in convenience stores throughout the state. Each lottery ticket must have at least three things printed on it: the identity of the terminal that printed it, a timestamp (of up to 1 millisecond accuracy) that marks when it was printed, and a "lucky number" which is an integer between 0 and 9,999,999 inclusive. You may add additional information to each ticket. Lottery tickets go on sale at 8:00 AM every Monday, and can be bought until 11:00 PM on Saturday. Lottery terminals are programmed to refuse to dispense tickets between 11:00 PM Saturday and 8:00 AM Monday.

At 11:30 PM every Saturday, a random number generator in the central lottery office generates the "weekly drawing" which is a randomly chosen integer between 0 and 9,999,999 inclusive. On Sunday, anybody who has a ticket that (a) was sold within the last week, and (b) has a lucky number that matches the weekly drawing, can turn in that ticket. The lottery agency has one week to validate the ticket; if it is successfully validated, the person who turned it in gets $5,000,000 in cash. Any number of winning tickets, or none at all, might exist. Each valid winning ticket gets $5,000,000.

Tickets are dispensed by lottery terminals, which are small hardware devices that the lottery agency leases to the owners of convenience stores throughout the state. The store puts the terminal next to the store's cash register. A customer who wants to buy a lottery ticket enters his or her chosen lucky number by pressing buttons on the terminal, or the customer presses a special button asking the terminal to generate a lucky number randomly. The customer then pays the store clerk $1. Finally, the store clerk presses a button that causes the terminal to dispense the ticket to the customer.

At the end of the week, each store tells the lottery agency how many tickets the store sold that week. The store gives the lottery ninety cents for each sale that the store reports; the store gets to keep the other ten cents.

Practical Considerations

Tickets are printed on special, identifiable paper that is produced by the lottery agency and is not sold to anybody else, and they use special ink that is hard to erase. But since the cost to create each ticket is necessarily low, it is certainly possible for a determined criminal to forge a ticket or to modify a legitimate ticket. In other words, you can't necessarily tell whether a ticket is forged just by looking at it.

You can assume that the lottery terminals are tamperproof, in the sense that there is no way to open up the terminal or modify its inner workings without irrevocably breaking the terminal. However, a criminal might steal a terminal and hide it or might smash a terminal to bits deliberately.

Each terminal has an accurate, tamperproof clock inside it.

Some store owners are dishonest and may try to "lowball" you by lying about how many tickets they sold and pocketing the extra money. One of your goals is to make it hard for store owners to do this without getting caught.

Each terminal costs you $50 per week; this includes maintenance plus the amortized cost of buying the terminal.

You can add a wireless link to any terminal if you want. Each wireless link costs $10 per week to operate. Once installed, you must continue to pay for the wireless link (i.e. you cannot turn it on and off to save money). Wireless link hardware that you decide to "build in" to a terminal can be put inside the tamperproof module so that it is impossible for anyone to tamper with the wireless link hardware without destroying the terminal.

If you want, you can have each terminal create a weekly log of its activities on a thumb drive. This facility costs $1 per terminal per week, and you can assume that it is tamperproof. If you do not pay the $1, then the lottery terminal has no storage. You can have a lottery courier drive out to a store and use a special key to open the terminal and get a copy of the log, or you can use the wireless link to transmit the contents of the log. A courier can visit 200 stores per week, and it costs you $2000 per week per courier for salary, benefits, the courier's car, and clerks to do background checks on the couriers. It is ok if the number of couriers varies over time.

We are open to other minor tweaks to the overall organization of the lottery or the equipment used in ticket sales (e.g. add more information to the printed tickets, hire jackbooted thugs to guard lottery terminal, give additional prizes for 'close' tickets). If you want to do something that seems to break the rules above, then post on Piazza and we'll get back to you with costs for your proposal. Be creative!

Note to the left brained: These numbers are not meant to act as hard constraints for an optimization problem. There is not a single correct answer.

There are 10,000 lottery terminals in the state.

Criteria

Your design should strive to meet the following three criteria, which are listed in decreasing order of importance: These criteria are naturally in conflict (e.g. a system with no security would have the lowest cost). You should justify how you balanced these critera in your design. In addition to these criteria, you must also obey the one absolute rule: If someone possesses a legitimate winning ticket, they must be able to redeem it. Imagine the chaos.

Logistics

No code this week. Or next week. Or ever again in this class... or is there?

You should prepare a report describing and justifying your design, and explaining how it satisfies the three criteria. If you cannot satisfy all of the criteria perfectly, it is better to be honest about that fact and discuss the limitations of your solution in a straightforward way. When you need to make trade-offs, please explain these trade-offs in as much detail as possible.

If you'd like to do something out of the box, or you need any additional information for analyzing your design that is not given in "practical considerations" above, then please post on Piazza.

Your grade will be based primarily on the robustness and self-analysis of your design, e.g. how it works, why you think it best satisfies the criteria, and if it actually reasonably satisfies the criteria. Unlike HW4, there is no code to implicitly serve as a mathematical description of your design, and thus we will also be grading on clarity and organization.

Your solution should be submitted in either pdf or HTML format. If you're using pdf format, please name your report submit6.pdf. If you're using HTML, please package everything you're submitting into a single zip-file, called submit6.zip. You can submit using this link.

If you're using HTML, the report should be an HTML file named index.html. This HTML report may contain images, links to other files, etc. if you include those files in your submission. Though your solution will be graded on content AND presentation, you do not need to design a beautiful document (e.g. you do not have to: perform A/B testing on your layout, use css, include steganographic images of the teaching staff, have MIDI files playing in the background, etc.).

Disclaimer

Many people think that state lotteries are a bad idea, for either moral or practical reasons. This assignment is not an endorsement of state lotteries. We chose the lottery application because it poses technical challenges that make a good homework assignment.

Copyright 1998-2014, Edward W. Felten.