In this dissertation, we design and analyze five authentication protocols that answer to the a firmative the following fi ve questions associated with the authentication functions in computer networks. 1. The transport protocol HTTP is intended to be lightweight. In particular, the execution of applications on top of HTTP is intended to be relatively inexpensive and to take full advantage of the middle boxes in the Internet. To achieve this goal, HTTP does not provide any security guarantees, including any authentication of a server by its clients. This situation raises the following question. Is it possible to design a version of HTTP that is still lightweight and yet provides some security guarantees including the authentication of servers by their clients? 2. The authentication protocol in HTTPS, called TLS, allows a client to authenti- cate the server with which it is communicating. Unfortunately, this protocol is known to be vulnerable to human mistakes and Phishing attacks and Pharm- ing attacks. Is it possible to design a version of TLS that can successfully defend against human mistakes and Phishing attacks and Pharming attacks? 3. In both HTTP and HTTPS, a server can authenticate a client, with which it is communicating, using a standard password protocol. However, standard password protocols are vulnerable to the mistake of a client that uses the same password with multiple servers and to Phishing and Pharming attacks. Is it possible to design a password protocol that is resilient to client mistakes (of using the same password with multiple servers) and to Phishing and Pharming attacks? 4. Each sensor in a sensor network needs to store n - 1 symmetric keys for secure communication if the sensor network has n sensor nodes. The storage is constrained in the sensor network and the earlier approaches succeeded to reduce the number of keys, but failed to achieve secure communications in the face of eavesdropping, impersonation, and collusion. Is it possible to design a secure keying protocol for sensor networks, which is e fficient in terms of computation and storage? 5. Most authentication protocols, where one user authenticates a second user, are based on the assumption that the second user has an "identity", i.e. has a name that is (1) fi xed for a relatively long time, (2) unique, and (3) ap- proved by a central authority. Unfortunately, the adoption of user identities in a network does create some security holes in that network, most notably anonymity loss, identity theft, and misplaced trust. This situation raises the following question. Is it possible to design an authentication protocol where the protocol users have no identities? / text

Online/offline signature schemes are useful in many situations, and two such scenarios are considered in this dissertation: bursty server authentication and embedded device authentication. In this dissertation, new techniques for online/offline signing are introduced, those are applied in a variety of ways for creating online/offline signature schemes, and five different online/offline signature schemes that are proved secure under a variety of models and assumptions are proposed. Two of the proposed five schemes have the best offline or best online performance of any currently known technique, and are particularly well-suited for the scenarios that are considered in this dissertation. To determine if the proposed schemes provide the expected practical improvements, a series of experiments were conducted comparing the proposed schemes with each other and with other state-of-the-art schemes in this area, both on a desktop class computer, and under AVR Studio, a simulation platform for an 8-bit processor that is popular for embedded systems. Under AVR Studio, the proposed SGE scheme using a typical key size for the embedded device authentication scenario, can complete the offline phase in about 24 seconds and then produce a signature (the online phase) in 15 milliseconds, which is the best offline performance of any known signature scheme that has been proven secure in the standard model. In the tests on a desktop class computer, the proposed SGS scheme, which has the best online performance and is designed for the bursty server authentication scenario, generated 469,109 signatures per second, and the Schnorr scheme (the next best scheme in terms of online performance) generated only 223,548 signatures. The experimental results demonstrate that the SGE and SGS schemes are the most efficient techniques for embedded device authentication and bursty server authentication, respectively.