Reconciling Two Views of Cryptography

Short Description
Two distinct, rigorous views of cryptography have developed over …. This section explains the two views of cryptography, still informally. It …

Website: www.cs.ucdavis.edu | Filesize: 285kb

Content
Reconciling Two Views of Cryptography
(The Computational Soundness of Formal Encryption)
Mart’? Abadi
Bell Labs Research
Lucent Technologies
abadi@lucent.com
www.pa.bell-labs.com/~abadi
Phillip Rogaway
Department of Computer Science
University of California at Davis
rogaway@cs.ucdavis.edu
www.cs.ucdavis.edu/~rogaway
July 25, 2000
An abridged, preliminary version of this paper will appear in the proceedings of the IFIP International
Conference on Theoretical Computer Science (IFIP TCS2000), Sendai, Japan, August 2000.
This is a draft for the full paper.
Abstract
Two distinct, rigorous views of cryptography have developed over
the years, in two mostly separate communities. One of the views relies
on a simple but effective formal approach; the other, on a detailed
computational model that considers issues of complexity and probability.
There is an uncomfortable and interesting gap between these
two approaches to cryptography. This paper starts to bridge the gap,
by providing a computational justification for a formal treatment of
encryption.Contents
1 Two Views of Cryptography 1
2 Background and Related Work 3
3 Formal Encryption and Expression Equivalence 5
3.1 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3 Some examples and some subtleties . . . . . . . . . . . . . . . 10
4 The Computational View: Encryption Schemes and Indistinguishability
11
4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2 Aspects of encryption-scheme security . . . . . . . . . . . . . 12
4.3 Definitions of encryption-scheme security (types 0, 1, 3) . . . 14
4.4 Achieving type-0 and type-1 security with standard tools . . 16
5 The Computational Soundness of Formal Equivalence 18…