Foundations of Modern Cryptography

Abstract

The need for cryptography has been recognized since ancient times. One of its main goals, private communication in the presence of adversary, is traced back to the ancient Roman empire, whose emperor Julius Ceasar used to communicate to his allies by replacing each letter in his message with the third next letter in the alphabet. Classical cryptography went on until the end of last century focusing on the art of designing and breaking secrecy codes. Modern cryptography has significantly enlarged its scope to the rigorous analysis of any system that is potentially subject to malicious threats and the design of solution that can guarantee the system to withstand such threats. As a consequence, many goals have been added to that of private communication in the presence of adversary, and cryptography has moved from an engineering art built on a number of heuristic techniques to a scientific discipline based on mathematically rigorous design requirements, solution techniques and correctness proofs. We present here an introduction to some basic topics in the foundation of modern cryptography; specifically: one-way functions, pseudo-random generators, pseudo-random functions and zero-knowledge protocols.