Special Signature Schemes and Key Agreement Protocols

by Caroline J. Kudla

Abstract:

This thesis is divided into two distinct parts. The first part of
the thesis explores various deniable signature schemes and their
applications. Such schemes do not bind a unique public key to a
message, but rather specify a set of entities that could have
created the signature, so each entity involved in the signature can
deny having generated it. The main deniable signature schemes we
examine are ring signature schemes.

Ring signatures can be used to construct designated verifier
signature schemes, which are closely related to designated verifier
proof systems. We provide previously lacking formal definitions and
security models for designated verifier proofs and signatures and
examine their relationship to undeniable signature schemes.

Ring signature schemes also have applications in the context of fair
exchange of signatures. We introduce the notion of concurrent
signatures, which can be constructed using ring signatures, and
which provide a "near solution" to the problem of fair exchange.
Concurrent signatures are more efficient than traditional solutions
for fair exchange at the cost of some of the security guaranteed by
traditional solutions.

The second part of the thesis is concerned with the security of
two-party key agreement protocols. It has traditionally been
difficult to prove that a key agreement protocol satisfies a formal
definition of security. A modular approach to constructing provably
secure key agreement protocols was proposed, but the approach
generally results in less efficient protocols.

We examine the relationships between various well-known models of
security and introduce a modular approach to the construction of
proofs of security for key agreement protocols in such security
models. Our approach simplifies the proof process, enabling us to
provide proofs of security for several efficient key agreement
protocols in the literature that were previously unproven.