9
$\begingroup$

This question is in the same vein as inspirational talk for final year high school pupils. 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. 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 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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
11
$\begingroup$

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, as well as the hilarious Ali Baba and the 40 thieves story. While these were originally designed for a younger crowd, they work well at all ages to convey the right intuition.

Improve this answer
$\endgroup$
6
  • $\begingroup$ @Suresh: Thanks a lot. Any ideas on the second issue (motivating unsolved problems at the M.Sc. level)? $\endgroup$
    – Sadeq Dousti
    Dec 15, 2010 at 21:55
  • 1
    $\begingroup$ The two links are the same. $\endgroup$
    – Tsuyoshi Ito
    Dec 16, 2010 at 2:04
  • $\begingroup$ that's a hard one. there aren't many problems that are tractable at that level without knowing complexity. $\endgroup$
    – Suresh Venkat
    Dec 16, 2010 at 4:10
  • $\begingroup$ @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? $\endgroup$
    – Sadeq Dousti
    Dec 16, 2010 at 12:52
  • $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Dec 16, 2010 at 12:54
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.