Authentication protocols in pervasive computing

The popularity of personal computing devices (e.g. smart cards) exposes users to risks, notably identity theft, and creates new requirements for secure communication. A recently proposed approach to creating secure communication is to use human trust and human interactions. These approaches potentially eliminate the need for passwords as in Bluetooth, shared secrets or trusted parties, which are often too complex and expensive to use in portable devices. In this new technology, handheld devices exchange data (e.g. payment, heart rates or public keys) over some medium (e.g. WiFi) and then display a short and non-secret digest of the protocol’s run that the devices’ human owners manually compare to ensure they agree on the same data, i.e. human interactions are used to prevent fraud. In this thesis, we present several new protocols of this type which are designed to optimise the work required of humans to achieve a given level of security. We discover that the design of these protocols is influenced by several principles, including the ideas of commitment without knowledge and separation of security concerns, where random and cryptographic attacks should be tackled separately. Underpinning the technology is a new cryptographic function, termed a keyed digest function, which produces a short number for humans to compare. This is similar to the notion of a universal hash function, but its output length is shorter (e.g. 16 bits). Hence, it should be faster to compute. We propose several digest constructions using Toeplitz matrices, integer multiplication and pseudorandom numbers. The application of digest functions leads us to develop more efficient alternatives to standard digital signatures. Our protocol security analysis leads to a new bound on the key length for an almost universal hash function, which can be derived by the pigeon-hole principle. The new bound turns out to be tighter than another similar bound derived from the combination of the Singleton bound in coding theory and an equivalence between error-correcting codes and almost universal hash functions.