| This thesis concerns two subjects whose primary applications are in the field of cryptography: reversible programs and multi-party protocols.The first part of the thesis investigates a model of computation called a "reversible program", and its relationship to the level of cryptographic security attainable by a "simple product cipher" (which is a type of method for encrypting fixed-length blocks of data).The notion of a simple product cipher is motivated by the design of some ciphers, including the widely used Data Encryption Standard.Informally, reversible programs and simple product ciphers both have the property that they can be expressed as a composition of "very simple" permutations on the set of n-bit binary strings. We show that, under a cryptographic assumption (namely, that there exists a pseudorandom function generator that is feasibly computed by a particular kind of computation, called an "iterated integer matrix product"), there exists a cryptographically secure simple product cipher. This can be regarded as progress towards showing that a secure simple product cipher exists. A by-product of our investigation of reversible programs is a result of independent interest in the field of algebraic complexity theory: over an arbitrary ring, any polynomial-size algebraic formula is computed by an algebraic straight-line program that uses only three registers.The second part of the thesis investigates the cryptographic security attainable in two-party protocols that carry out "collective coin flipping" transactions (or "games"), and "secret bit exchanging" transactions. In both cases, we construct protocols that, under some widely believed number theoretic intractability assumptions, attain various levels of security for the transaction. We also prove some non-trivial lower bounds on the level of security attainable by any protocol for either of the transactions. |
