Encrypted Computation

Abstract

The ability to construct software, call it a functional ciphertext, which can be remotely executed in encrypted form as an entirely self-contained unit, has the potential for some interesting applications. One such application is the construction of autonomous mobile agents capable of entering into certain types of legally binding contracts on behalf of the sender. At a premium in such circumstances is the ability to protect secret cryptographic keys or other secret information, which typically is necessary for legally binding contracts. Also important is the ability to do powerful computations, that are more than just one-off secure function evaluations.

The problem of constructing computation systems that achieve this, has been attempted by many to little or no avail. This thesis presents three similar cryptographic systems that take a step closer to making such encrypted software a reality.

First is demonstrated how one can construct mappings from finite automata, that through iteration can do computations. A stateless storage construction, called a Turing platform, is defined and it is shown that such a platform, in conjunction with a functional representation of a finite automaton, can perform Turing universal computation.

The univariate, multivariate, and parametric ciphers for the encryption of multivariate mappings are presented and cryptanalyzed. Cryptanalysis of these ciphers shows that they must be used very carefully, in order to resist cryptanalysis. Entirely new to cryptography is the ability to remotely and securely re-encrypt functional ciphertexts made with either univariate or multivariate encryption.

Lastly it is shown how the ciphers presented can be applied to the automaton representations in the form of mappings, to do general encrypted computation. Note: many of the novel constructions in this thesis are covered by a patent application.