Cryptology III.B Complexity Theory for Cryptology

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

Contents

1. Probabilistic circuits [PDF]
2. Polynomial size families of circuits (PPC) [PDF]
3. Efficient algorithms [PDF]
4. Hard problems [PDF]
5. Basic cryptographic functions [PDF]

The complete Appendix B as PDF file

Overview

For (at least) three reasons »ordinary« complexity theory (using TURING machines) is insufficient for cryptologic needs:

1. Complexity theory addresses the question whether the worst case is hard (i. e. not efficiently computable). To preclude an efficient cryptanalysis we want the normal case to be hard. We saw that the existence of strong basic cryptographic functions implies P ≠ NP, but conversely this inequality (if true) would not suffice to prove the existence of strong cryptography.
   
   A similar phenomen is known from other parts of mathematics. For instance the NEWTON algorithm for determining roots of polynomials and the simplex method for linear optimization are hard in the worst case, but very efficient in the normal case.
   
   »Ordinarily an algorithm that only occasionally works is useless, but a cryptanalysis algorithm that occasionally works makes the cryptosystem useless.« (Neal Wagner's Law CRYPTO 4)
   
   
2. The cryptanalyst is free to use probabilistic algorithms (»Monte Carlo« algorithms) that are very efficient but don't give a correct result in all cases. We saw several examples for number theoretic problems.
   
   The exact mathematical treatment uses concepts from probability theory: Parts of the input are taken from a probability space Ω. The results are statements on the distribution of the output.
   
   
3. Moreover the cryptanalyst is free to adapt her methods to the concrete problem at hand. She doesn't necessarily need a universal algorithm that is efficient for all instances of her problem. For example she could choose a different algorithm depending on the key length. Thus we have to consider non-uniform models of computation.

As a consequence the ordinary theory of TURING machines is insufficient for formalizing complexity theory as it is needed in cryptology. We could remedy this shortage by considering families of TURING machines—say a different one for each input length—, and also admitting probabilistic input.

However an alternative model of computation, using Boolean circuits, has a simpler, more intuitive description and a more direct and elegant application: families of probabilistic circuits (FPC for short). Realizing common algorithms by circuits is distinctly simpler and more intuitive than programming a TURING machine.