Optional Lesson: One-way Functions - The WiFi Hotspot Problem
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 human!) to solve, then perhaps it is possible to make truly secure encryptions.
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.
Students will be able to:
- Describe the properties of a one-way function.
- Construct a wireless hotspot map, starting from a solution key.
- Explain why the wireless hotspot problem is a computationally hard problem.
- Describe the difference between the Traveling Salesman Problem and the Wireless Hotspot Problem and why one-way functions are desirable when creating cryptographic methods.
- Paper copies of both worksheets, one of each per student
For the Teacher
- KEY - Wireless Hotspot Problem - Answer Key
- KEY - Make Your Own Wireless Hotspot Problem - Answer Key
- Optional Lessons on Code Studio
For the Students
Review: Say: In the previous lesson we explored a computationally hard problem called the Traveling Salesman Problem. The only known way to find the shortest path is to perform a brute force search, or in other words, try every possible path. There are heuristics for getting close to a good solution but no known way to get the exact solution without trying every possible path, which is prohibitively large. It would take an unreasonable amount of time to solve.
As we saw, it’s fairly easy to draw a map which will take a computer (or person) thousands of years to solve. An interesting thing about the Traveling Salesman Problem is that, even if you are the one making the map (assuming it’s not trivial), it’s also impossible for you to know the correct solution without also using the brute force approach.
Computationally hard problems are used to make encryption really strong, but we don’t totally know how this works yet. Today we’re going to look at another hard problem that moves us back toward the path to encryption. We’d like to have some way to construct a problem that is computationally hard to solve but to which we know the answer!
You may choose to skip this introduction if you would rather not clue students in on the surprise of today’s lesson. If you feel students are comfortable with the vocabulary and concepts of the previous lesson, dive right into trying to crack the Wireless Hotspot Problem, and make the connection between the previous lesson and this one after students have experienced the challenge and learned to create the problem themselves.
How is this different from one-way functions we’ve seen before?
The Caesar and Vigenère encryption algorithms are attempts to create a one-way function. However, they result in ciphertexts that are crackable using heuristics and techniques like frequency analysis. Up to this point, we have not seen a one-way function that produces a problem that is actually computationally hard to solve.
Distribute: Provide students with copies of Wireless Hotspot Problem - Worksheet. Students may work 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.
Work on the Challenge: Students should work on the challenge for several minutes, but probably 10 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.
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 solution is in KEY - Wireless Hotspot Problem - Answer Key.
Share Results: Ask students to stop working and compare their results with classmates, other groups, or as a class. Prompts:
- What was the smallest set of hot spots they were able to find?
- What types of heuristics did you employ to find your solution? (e.g., pick the most connected corners first)
- Use this opportunity to recall this vocabulary from the previous lesson. A heuristic is just a strategy for arriving at a “pretty good” solution when there’s no obvious way to get a perfect one.
- Note: Even if some heuristics for this problem do a good job, none will always guarantee a perfect solution.
- Are you sure this is the actual smallest? How could you be certain?
- Students should begin to suspect that this problem can only be solved through a brute force search, i.e., trying every combination with one node, then two, then three, and so on, until a solution is found. Clearly, this could take a very long time, just like the Traveling Salesman Problem.
Discuss: Relate the experience with this problem to that on the Traveling Salesman Problem.
- How is this problem similar to the Traveling Salesman Problem?
- Possible points: it’s a graph algorithm, you’re looking for one best solution, it just seems hard to do. This question is more to draw the original connection and prepare for the following question.
- How would a computer approach this problem? How long is it going to take?
- If students have not already noticed, confirm that this is a computationally hard problem and would require a brute force search. Just like in the Traveling Salesman Problem, the number of possible solutions is multiplied every time another node is added, so even for small graphs, this problem can take an extremely long time to solve.
If you are interested in the math….how hard is this problem?
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 see 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.
Transition: 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. Let’s see how.
Distribute: Distribute to each group or student the Make Your Own Wireless Hotspot Problem - Worksheet. 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 see 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.
The following questions can be found on Code Studio.
Multiple Choice: Which of the following correctly defines a one-way function?
a) Hard to create and hard to solve
b) Hard to create and easy to solve
c) Easy to create and hard to solve
d) Easy to create and easy to solve
Matching: Match each word to the phrase that best describes it:
Word/Phrase Description a. Heuristic 1. Requiring many computers or a long time in order to be solved b. Brute force 2. Requires much more effort to solve than to create c. One-way function 3. Trying every possible solution d. Computationally hard 4. Rules or an algorithm for finding an approximate solution
Free Response: Given that the Traveling Salesman Problem and the Wireless Hotspot Problem are computationally hard to solve, why might the Wireless Hotspot Problem be a more ideal candidate for using an encryption method? Make reference to properties of the two problems in your answer.
- 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.
- The Problem: Given a list of positive and negative numbers, is there some group of these numbers which adds up to 0?
- Example: (45, -100, 23, 11, -14, 25, -81, 37, 10) The solution is 45, -100, 23, 11, -14, 25, 10. Don’t worry if you didn’t get it yourself; the whole point is that it’s hard to find a solution!
- Creating the problem: Choose a set of numbers known to add up to 0 beforehand. For example, -12, -10, 3, and 19. Then add in a bunch of “distractor” values. Present a randomly sorted list containing the solution values and the distractors. There’s no guaranteed solution, other than checking all possibilities by brute force!
- 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. They can use this Graph Creator tool: http://illuminations.nctm.org/Activity.aspx?id=3550
Reflect: Students should complete the reflection questions at the bottom of their worksheets in preparation for the following discussion.
Discuss: Say: 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.
- When else have we seen things that act like one-way functions?
- Students may make the connection to encryption. With the Vigenère cipher, if you know the key, encrypting the text is easy, but undoing it is very hard.
- Important Note: The Vigenère cipher is actually NOT a computationally hard problem to solve. It is an attempt to make text hard to crack, but there are techniques for cracking it very quickly. The Wireless Hotspot Problem is the first one-way function we’ve actually seen that results in a computationally hard problem.
- Why might we want to use a one-way-function when designing a method of cryptography?
- When we encrypt a piece of information, we would like it to be easy for the person doing the encryption, but hard for even a powerful computer to crack the encryption.
- In the Wireless Hotspot Problem, what could act as a “key” to our encryption?
- Recall that the key is the portion of the encryption that remains a secret. When constructing your own map, perhaps there is some way of using those “secret nodes” as a key.
- Note: Students don’t yet need to know HOW this will be done.
Unit 4: Lesson 2 - Rapid Research - Data Innovations
In this lesson you will conduct a small amount of research to explore a computing innovation that leverages the use of data. You will research a topic of personal interest and respond to questions about how that innovation produces, uses or consumes data.
- One-pager: A business/corporate term for a one-page document that summarizes a large issue, topic or plan. The purpose is to distill and highlight the most important pieces of information in a digestible manner so that the reader can be quickly acquainted with the relevant details of the "big picture."
- Watch a video about big data
- Choose and research a Data Innovation.
- Prepare your one-pager.
- Video: (choose at least one)
- Activity Guide: Rapid Research - Data Innovations
- Worksheet: Data Innovations One-Pager Template
- (click tabs to see student view)
The AP Explore Performance task requires you to provide short written responses about an innovation that you research. Here are portions of the AP writing prompts to consider:
Using specific details, describe: • the data your innovation uses; • how the innovation consumes (as input), produces (as output), and/or transforms data
Practice an AP response by responding the prompt above, summarizing the data innovation you researched for this lesson. Your first sentence should name the innovation you are writing about.
CSTA K-12 Computer Science Standards (2011)
CT - Computational Thinking
- CT.L3B:1 - Classify problems as tractable, intractable, or computationally unsolvable.
- CT.L3B:2 - Explain the value of heuristic algorithms to approximate solutions for intractable problems.
- CT.L3B:3 - Critically examine classical algorithms and implement an original algorithm.
- CT.L3B:4 - Evaluate algorithms by their efficiency, correctness, and clarity.
Computer Science Principles
4.2 - Algorithms can solve many but not all computational problems.
4.2.1 - Explain the difference between algorithms that run in a reasonable time and those that do not run in a reasonable time. [P1]
- 4.2.1A - Many problems can be solved in a reasonable time.
- 4.2.1C - Some problems cannot be solved in a reasonable time, even for small input sizes.
4.2.4 - Evaluate algorithms analytically and empirically for efficiency, correctness, and clarity. [P4]
- 4.2.4A - Determining an algorithmâ€™s efficiency is done by reasoning formally or mathematically about the algorithm.
- 4.2.4C - The correctness of an algorithm is determined by reasoning formally or mathematically about the algorithm, not by testing an implementation of the algorithm.
6.3 - Cybersecurity is an important concern for the Internet and the systems built on it.
6.3.1 - Identify existing cybersecurity concerns and potential options to address these issues with the Internet and the systems built on it. [P1]
- 6.3.1H - Cryptography is essential to many models of cybersecurity.
- 6.3.1I - Cryptography has a mathematical foundation.