Position-based quantum cryptography and catalytic computation

In this thesis, we present several results along two different lines of research. The first part concerns the study of position-based quantum cryptography, a topic in quantum cryptography. By combining quantum mechanics with special relativity theory, new cryptographic tasks can be developed that use the causality constraints of relativity theory in a constructive way. Position-based cryptography is a type of cryptography that wants to use location as a credential, instead of (or in addition to) a secret key – for instance to create a protocol to send messages that can only be read at one specific location.
In the second part we introduce a new notion of computation, catalytic computation, and study this new model within complexity theory. Catalytic computation is a computation that has a small amount of clean space available and is equipped with additional auxiliary space, with the caveat that the additional space is initially in an arbitrary, possibly incompressible, state and must be returned to this state when the computation is finished. The term ‘catalytic’ comes from chemistry, where it refers to a reactant which speeds up a chemical reaction but is not consumed – just like the extra space available to the computation.