Q:

Motivating Talk on Foundations of Cryptography

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.

A:

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. 

A:

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.

