|
Cryptology
III.6 Equivalences of Basic Cryptographic Functions |
a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h:
Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø |
|
Contents
- One-way functions [PDF-Datei]
- Hash functions [PDF-Datei]
- Conversion tricks [PDF-Datei]
- Physical complexity [PDF-Datei]
- TURING machines [PDF-Datei]
- The class NP [PDF-Datei]
The complete chapter as PDF file
Overview
In real world applications the basic cryptographic functions
- Symmetric ciphers:
- bitblock ciphers
- bitstream ciphers
- Asymmetric ciphers
- Keyless ciphers:
- one-way functions
- hash functions
- Random generators:
- physical random generators
- (algorithmic) (pseudo-) random generators
- Steganographic procedures
are used for the construction of cryptographic protocols. We'll see that the
existence of most of them—1a, 1b, 3a, 3b, 4b in suitable variants—is
equivalent with the basic problem of theoretic computer science P ?=? NP,
and thus lacks a proof.
Warning: Most parts of this section are mathematically inexact.
Statements on complexity are
formulated in the naive way and justified by heuristic arguments. Then we sketch the approach
to formalizing them by TURING machines. However this model turns out as insufficient for
cryptology. The mathematically sound versions of complexity results for cryptologic procedures
are given in Appendix B. For mathematical sound versions of
the equivalency statements in Section 3 see the book by GOLDREICH in the
reference list.
Author: Klaus Pommerening, 2000-Oct-29;
last change: 2021-Mar-06