In this lesson, students continue their exploration of computationally hard problems as they investigate a one-way function, a problem which is easy to construct in such a way that you know the solution, but it is computationally hard to solve. Students will begin the lesson by trying to solve the "Wireless Hotspot Problem" (also know as the vertex cover or dominating sets problem) to experience first-hand the challenge of solving it. They will then be instructed on how easy it is to create such a problem and will practice doing so themselves. In the Wrap Up, students are introduced to the concept of a one-way function and consider why such problems might be useful tools when constructing methods of encryption. If it's easy to create a problem that is hard for a computer (or a human!) to solve, then perhaps it is possible to make truly secure encryptions.
Students will be able to:
Modern encryption techniques are designed around a set of problems that are known to be computationally hard to solve. A computationally hard problem is one for which the number of possible solutions grows quickly (typically exponentially), and which requires a computer to check each possible solution, also called a brute force search. The Traveling Salesman problem is computationally hard, but it has the drawback that even the person who constructed the problem might not know the optimal solution. In other words, the creator also has to do a brute force search, just like everyone else. Some computationally hard problems, such as the one covered in this lesson, can easily be constructed so that the creator knows the solution, but they are still computationally hard for anyone else to solve. These problems are called one-way functions and are very useful for encryption, since all encryption is an attempt to create a one-way function.
Remind the students the following:
For today's lesson:
After distributing the "Wireless Hotspot Problem" worksheet, allow the students to work either individually or in pairs on this challenge. You may choose to read the instructions together, to ensure that the challenge is clear and students know how to proceed.
Students should work on the challenge for several minutes, but only 10 minutes at the most. You should offer help as needed, and encourage students to continue to work on their solutions. Just because students found a good solution doesn't mean that it's actually the best! With a more competitive class, you might want to keep a running track of the best solution found so far. Alternately, ask students to check one another's solutions or help one another get started if they're having trouble.
Ask students to stop working and compare their results with classmates, other groups, or as a class.
Some of the questions to facilitate discussion:
If one group claims to have found a solution, ask how many hotspots they needed, and challenge other groups to find the same or a better solution. (The optimal number is 5. If anyone claims fewer than 5, they're missing a connection somewhere.)
It's possible that no one will find the optimal solution. That's the point! This is a chance to better understand another computationally hard problem. Ideally, this will also drive home the significance of the fact that they can easily create this kind of problem and know the solution.
The goal of this discussion is to relate the experience with this problem to that on the Traveling Salesman Problem.
The problem we just explored is actually a very famous one in computer science, technically known as the vertex cover problem. It is significant because, just like the Traveling Salesman Problem, it is computationally hard to solve perfectly. Heuristics give good solutions, but perfect solutions can only be found with a brute force search. But there is one very big difference between the Traveling Salesman Problem and the Wireless Hotspot Problem: the person who creates the problem can know the solution ahead of time - WITHOUT performing a brute force search
There is no known algorithmic way to figure out the placement of the hotspots besides brute force. That means if you think there is a 3-hotspot solution, you have to try every possible placement of 3 hotspots in the map to verify that it does (or doesn't) work.
Our town has 23 locations in it. So there 23 ways to place the first hotspot, 22 remaining locations to place the second, 21 for the third, and so on.
This means for 5 hotspots (the actual minimum number), to make sure that you would find the solution, you would have to try: 23 x 22 x 21 x 20 x 19 = 4,037,880 possibilities! Of course, you’d have to try all the possibilities for fewer hotspots first, since you wouldn’t actually know ahead of time that 5 was the minimum. To help you understand how fast this grows: a 100-node map, with a 10-hotspot solution (something you could draw by hand in minutes) would have 100 x 99 x 98 x …. x 91 = 62,815,650,955,529,470,000 (62 quintillion) possibilities.
Distribute the 'Make Your Own Wireless Hotspot Problem' Activity Guide. Students may either read through the explanation there or you can review the explanation as a class.
Following the instructions the worksheet, students have been provided space to create their own maps. Ask students to follow the steps to make a map, and keep track of their solution somewhere else (a separate sheet of paper, their journals, etc.) They should then exchange with a partner to determine if they can find the results. If they follow the steps, it’s quite easy to make a problem that their classmates will have a very hard time cracking, even with just a few nodes.
Students should complete the reflection questions at the bottom of their worksheets in preparation for the following discussion.
The Wireless Hotspot Problem is one of a category of problems called "one-way functions." The person who creates the problem can easily know the solution, but for anyone else, finding the solution requires a brute force search. A problem you create in 20 seconds could take even the most powerful computers years to solve.
The list of Word/Phrase is as follows:
The list of Description is as follows:
Subset Sum Problem: Another one-way function that students can practice with is the subset sum problem. The problem is perhaps even easier to make than the Wireless Hotspot Problem, and has the same property of being computationally hard to solve. If you have time, this may be a good way to provide additional examples of a one-way function and further reinforce the mathematical foundations of cryptography using familiar mathematical concepts. Students can quickly make these problems for classmates and challenge them to solve them.
Make Your Own Graphs: Students can practice cracking one-way functions with the provided map and key, or practice creating one-way functions using maps and keys of their own creation.