Constructing cryptographic definitions

Document Type: REVIEW PAPER

Author

Abstract

This paper mirrors an invited talk to ISCISC 2011. It is not a conventional paper so much as an essay summarizing thoughts on a little-talked-about subject. My goal is to intermix some introspection about definitions with examples of them, these examples drawn mostly from cryptography. Underpinning our discussion are two themes. The first is that definitions are constructed. They are invented by man, not unearthed from the maws of scientific reality. The second theme is that definitions matter. They have been instrumental in changing the character of modern cryptography, and, I suspect, have the potential to change the character of other fields as well.

[1] Mihir Bellare. Practice-Oriented Provable Security. Lectures on Data Security, Modern Cryptology in Theory and Practice, Summer School, Aarhus, Denmark, July 1998. Lecture Notes in Computer Science, vol. 1561, Springer, pp. 1-15, 1999.

[2] I. Damgård. A "Proof-Reading" of Some Issues in Cryptography. Automata, Languages and Programming, 34th International Colloquium, ICALP 2007. Lecture Notes in Computer Science, vol. 4596, Springer, pp. 2{11, 2007.

[3] O. Goldreich. Foundations of Cryptography - A Primer. Foundations and Trends in Theoretical Computer Science, vol. 1, no. 1, now publishers, pp. 1-116, 2005