Design and analysis of human identification protocols

Human identification protocols are authentication protocols that enable a human using an insecure terminal to authenticate to a remote server. The goal of such protocols is to ensure secure authentication in the presence of an adversary who can not only view the user's inputs, and the internal computations and display of the terminal, but also eavesdrop on the communication link between the terminal and the server. An active adversary can in addition actively interfere with this communication link. However, protocols secure against active adversaries fall well short of usability. As a result, the focus of recent research has been on security against passive adversaries. Traditional authentication methods such as password-based authentication are not secure under this model, since the adversary can impersonate the user by learning the user's password after observing a single authentication session. -- Since the introduction of the problem by Matsumoto and Imai in 1991, there have been sporadic attempts at constructing secure human identification protocols. However, to date there is no accepted solution, mainly because such protocols require mental computations from humans, and therefore the tradeoff between security and usability is huge. State-of-the-art protocols take between one to three minutes for authentication, but guarantee stronger security than traditional authentication methods. While this authentication time is not acceptable for most practical purposes, many interesting new mathematical problems and ideas have resulted in search for usable protocols. -- This thesis aims to further the research in human identification protocols by focusing on the mathematical and analytical aspects of such protocols. We generalize some aspects of these protocols by analyzing their general structure. We give detailed security analysis of two protocols from literature, showing that without a thorough security analysis, these protocols are vulnerable to simple but innovative attacks. We also give the construction of two protocols with detailed security analysis and clearly defined design goals. Finally, we analyze the link between fixed-parameter intractability and human identification protocols. It is suggested that problems that are fixed-parameter intractable can be natural candidates for primitives in human identification protocols.