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