## Overview

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.

## Vocabulary

• One-way Function: a process that is easy to follow for any given input, but yields an output that is hard to turn back to the original input. Brute force is typically required to solve if the key is unknown.

## Goals

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

## Purpose

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.

## Getting Started

Remind the students the following:

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.

For today's lesson:

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 review 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!

## Activity

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:

• 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.

#### Tips

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.

#### Discussion

The goal of this discussion is to relate the experience with this problem to that on the Traveling Salesman Problem.

Prompts:

• How is this problem similar to the Traveling Salesman Problem?
• Possible points: it’s a graph algorithm, you’re searching 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.

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

#### Tips

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.

#### Make Your Own Wireless Hotspot Problem

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.

## Wrap Up

Students should complete the reflection questions at the bottom of their worksheets in preparation for the following discussion.

#### 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.

• When else have we encountered 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 encountered 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.

## Assessment

#### Q1: 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

#### Q2: Matching the following Word/Phrase with the corresponding Description. You can use the picture or the list provided.

The list of Word/Phrase is as follows:

1. Heuristic
2. Brute force
3. One-way function
4. Computationally hard

The list of Description is as follows:

1. Requiring many computers or a long time in order to be solved
2. Requires much more effort to solve than to create
3. Trying every possible solution
4. Rules or an algorithm for finding an approximate solution

## Extended Learning

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.

## Standards Alignment

• CSTA K-12 Computer Science Standards: CT.L3B:1, CT.L3B:2, CT.L3B:3, CT.L3B:4
• Computer Science Principles: 4.2.1 (A, C)
• Computer Science Principles: 4.2.4 (A, C)
• Computer Science Principles: 6.3.1 (H, I)