[JoGu]

Cryptology

III.6 Equivalences of Basic Cryptographic Functions

a7Hzq .#5r<
kÜ\as TâÆK$
ûj(Ö2 ñw%h:
Úk{4R f~`z8
¤˜Æ+Ô „&¢Dø

Contents

  1. One-way functions [PDF-Datei]
  2. Hash functions [PDF-Datei]
  3. Conversion tricks [PDF-Datei]
  4. Physical complexity [PDF-Datei]
  5. TURING machines [PDF-Datei]
  6. The class NP [PDF-Datei]

The complete chapter as PDF file


Overview

In real world applications the basic cryptographic functions

  1. Symmetric ciphers:
    1. bitblock ciphers
    2. bitstream ciphers
  2. Asymmetric ciphers
  3. Keyless ciphers:
    1. one-way functions
    2. hash functions
  4. Random generators:
    1. physical random generators
    2. (algorithmic) (pseudo-) random generators
  5. 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