Macquarie University
2 files

Design and analysis of human identification protocols

Download all (4 MB)
posted on 2022-03-28, 23:39 authored by Hassan Jameel Asghar
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.


Table of Contents

1. Introduction -- 2. Preliminaries and related work -- 3. Security analysis of PAS (Predicate-based Authentication Service) -- 4. Security analysis of CHC (Convex Hull Click) -- 5. Protocol construction 1: Kangaroo Hopping -- 6. Protocol construction 2: Counting Edges -- 7. Fixed-parameter intractable problems in human identification protocols -- 8. Conclusion and future research directions.


Bibliography: p. 149-154

Awarding Institution

Macquarie University

Degree Type

Thesis PhD


Thesis (PhD), Macquarie University, Faculty of Science, Dept. of Computing

Department, Centre or School

Department of Computing

Year of Award


Principal Supervisor

Josef Pieprzyk

Additional Supervisor 1

Ron Steinfeld


Copyright disclaimer: Copyright Hassan Jameel Asghar 2012.




1 online resource (xviii, 154 p.) col. ill

Former Identifiers

mq:25321 1839266

Usage metrics

    Macquarie University Theses


    Ref. manager