Transfinite Cryptography
Jacques Patarin
Let us assume that Alice, Bob, and Charlie, the three classical people of cryptography are not limited anymore to perform a finite number of computations on real computers, but are limited to α computations and to α bits of memory, where α is a fixed infinite cardinal. For example α = ?0 (the countable cardinal, i.e. the cardinal of N the set of integers), or α = C (the cardinal of the set R of real numbers). Is it possible to do secret key cryptography? Public-key cryptography? Encryption? Authentication? Signatures? Is it possible to generalize the notion of one-way function? The aim of this paper is to give some elements of answers to these questions.We will see for example that for secret-key cryptography there are some simple solutions. However for public-key cryptography the results are much less clear.
Keywords: Cryptography with infinite computations, Generalizations of cryptographic problems and algorithms, Foundations and introduction to transfinite cryptography.