<p>Honestly, it seems to me that a lecture on the level (and with the focus) of Goldreich's book will be beyond an incoming MSc student. (Calling zero knowledge a "main construct" of cryptography, while leaving out private-key encryption, is certainly a non-standard viewpoint.)</p>

<p>I would suggest a (slightly) more applied focus, on the lines of the Katz-Lindell book.</p>

CC BY-SA 3.0
2012-02-26T20:05:33.160Z
2012-02-26T20:05:33.160Z
user6584
<p>Since you can't rely on a knowledge of complexity theory, you have to emphasize the change in paradigm from security by obscurity to security by intractability, by positing the idea that some problems are hard to solve efficiently. This of course elides the many problems associated with the Impagliazzo worlds of intractability, but it gives a flavor of the way modern crypto works. </p>

<p>for ZKP, which are truly awesome, there are many ways to convey the basic ideas intuitively. See for example <a href="https://mathoverflow.net/questions/22624/example-of-a-good-zero-knowledge-proof/22675#22675">my answer on MO</a>, as well as the <a href="http://sparrow.ece.cmu.edu/group/630-f08/readings/ZK-IntroPaper.pdf" rel="nofollow noreferrer">hilarious Ali Baba and the 40 thieves story</a>. While these were originally designed for a younger crowd, they work well at all ages to convey the right intuition. </p>

CC BY-SA 2.5
2010-12-15T21:55:07.317Z
@Suresh: Thanks a lot. Any ideas on the second issue (motivating unsolved problems at the M.Sc. level)?
Sadeq Dousti
CC BY-SA 2.5
2010-12-16T02:04:58.710Z
The two links are the same.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-16T04:10:46.763Z
that's a hard one. there aren't many problems that are tractable at that level without knowing complexity.
Suresh Venkat
CC BY-SA 2.5
2010-12-16T12:52:45.897Z
@Suresh: Yeah, that's been my problem ever since I started giving talks on the subject. Anyway, I have to make compromises; so you may safely assume that people somehow understand the complexity well! Then, how can I given them motivating problems for M.Sc. thesis?
Sadeq Dousti
CC BY-SA 2.5
2010-12-16T12:54:59.387Z
I know very little about crypto, so :(. in geometry, there's a nice list of open problems. maybe you should troll through the list of open question that was posted here some time ago.
Suresh Venkat
CC BY-SA 2.5
2010-12-16T14:22:12.293Z
@Suresh: Thanks a lot. Crypto has a nice list of open problems, but they're too open! I'll troll through the list, as you suggested, and wait to see if others have good suggestions as well.
Sadeq Dousti
CC BY-SA 2.5
2010-12-15T21:09:29.340Z
2010-12-16T04:10:05.453Z
2017-04-13T12:57:54.777Z
Suresh Venkat
<p>This question is in the same vein as <a href="https://cstheory.stackexchange.com/q/2386/873">inspirational talk for final year high school pupils</a>. My Ph.D. advisor asked me to give an <em>inspirational talk</em> for new M.Sc. students. The subject is <strong>foundations of cryptography</strong>, which is best illustrated by <a href="http://www.wisdom.weizmann.ac.il/~oded/foc-book.html" rel="nofollow noreferrer">Goldreich's book</a>. The talk will take about one hour, and I want to familiarize the students to the <strong>main constructs</strong> (like one-way functions/permutations, pseudor-random generators, zero-knowledge proofs, encryption/signature schemes, etc.), and <strong>solved and unsolved problems</strong> in the field.</p>

<p>I want to keep the talk very <strong><em>motivating</em></strong>.
The main problem is two-fold:</p>

<ol>
<li>Foundations of cryptography needs a very good understanding of the <strong>computational-complexity theory</strong>. Alas, the M.Sc. students have not passed any course related to this theory.</li>
<li>I need to present some problems as possible topics for an M.Sc. thesis. While there are a lot of unsolved problems in the field, most of them are too hard for an M.Sc. student.</li>
</ol>

<p>Suggestions are most welcome. In addition, I'm very interested in pointers to similar talks.</p>

<hr>

<p><strong>Edit:</strong> I found the <a href="http://www.wisdom.weizmann.ac.il/~oded/students.html" rel="nofollow noreferrer">list of Goldreich's students</a> extremely inspiring. I'll be searching for other such lists, but you can help me if you know any similar lists. See also: <a href="http://www.wisdom.weizmann.ac.il/~oded/on-master.html" rel="nofollow noreferrer">Demystifying the Master Thesis and Research in General: The Story of Some Master Theses</a>.</p>

<reference-request><soft-question><cr.crypto-security><teaching>
Motivating Talk on Foundations of Cryptography
Sadeq Dousti
# Motivating Talk on Foundations of Cryptography

(Asked by: username_0 on 2010-12-15)

This question is in the same vein as [inspirational talk for final year high school pupils](https://cstheory.stackexchange.com/q/2386/873). My Ph.D. advisor asked me to give an *inspirational talk* for new M.Sc. students. The subject is **foundations of cryptography**, which is best illustrated by [Goldreich's book](http://www.wisdom.weizmann.ac.il/~oded/foc-book.html). The talk will take about one hour, and I want to familiarize the students to the **main constructs** (like one-way functions/permutations, pseudor-random generators, zero-knowledge proofs, encryption/signature schemes, etc.), and **solved and unsolved problems** in the field.

I want to keep the talk very ***motivating***.
The main problem is two-fold:

1. Foundations of cryptography needs a very good understanding of the **computational-complexity theory**. Alas, the M.Sc. students have not passed any course related to this theory.
2. I need to present some problems as possible topics for an M.Sc. thesis. While there are a lot of unsolved problems in the field, most of them are too hard for an M.Sc. student.

Suggestions are most welcome. In addition, I'm very interested in pointers to similar talks.

---

**Edit:** I found the [list of Goldreich's students](http://www.wisdom.weizmann.ac.il/~oded/students.html) extremely inspiring. I'll be searching for other such lists, but you can help me if you know any similar lists. See also: [Demystifying the Master Thesis and Research in General: The Story of Some Master Theses](http://www.wisdom.weizmann.ac.il/~oded/on-master.html).

**Tags:** reference-request, soft-question, cr.crypto-security, teaching

---

## 2 answers

### Answer by username_2 on 2010-12-15. Score: 11 | Accepted answer

Since you can't rely on a knowledge of complexity theory, you have to emphasize the change in paradigm from security by obscurity to security by intractability, by positing the idea that some problems are hard to solve efficiently. This of course elides the many problems associated with the Impagliazzo worlds of intractability, but it gives a flavor of the way modern crypto works.

for ZKP, which are truly awesome, there are many ways to convey the basic ideas intuitively. See for example [my answer on MO](https://mathoverflow.net/questions/22624/example-of-a-good-zero-knowledge-proof/22675#22675), as well as the [hilarious Ali Baba and the 40 thieves story](http://sparrow.ece.cmu.edu/group/630-f08/readings/ZK-IntroPaper.pdf). While these were originally designed for a younger crowd, they work well at all ages to convey the right intuition.

> **Comments:**
> **username_0**: @Suresh: Thanks a lot. Any ideas on the second issue (motivating unsolved problems at the M.Sc. level)?  
> **username_3**: The two links are the same.  
> **username_2**: that's a hard one. there aren't many problems that are tractable at that level without knowing complexity.  
> **username_0**: @Suresh: Yeah, that's been my problem ever since I started giving talks on the subject. Anyway, I have to make compromises; so you may safely assume that people somehow understand the complexity well! Then, how can I given them motivating problems for M.Sc. thesis?  
> **username_2**: I know very little about crypto, so :(. in geometry, there's a nice list of open problems. maybe you should troll through the list of open question that was posted here some time ago.  
> **username_0**: @Suresh: Thanks a lot. Crypto has a nice list of open problems, but they're too open! I'll troll through the list, as you suggested, and wait to see if others have good suggestions as well.  

---

### Answer by username_1 on 2012-02-26. Score: 4

Honestly, it seems to me that a lecture on the level (and with the focus) of Goldreich's book will be beyond an incoming MSc student. (Calling zero knowledge a "main construct" of cryptography, while leaving out private-key encryption, is certainly a non-standard viewpoint.)

I would suggest a (slightly) more applied focus, on the lines of the Katz-Lindell book.


---

