On Provable Security of Entity Authentication Schemes

Entity authentication is the process allowing a user, in a distributed system, to gain confidence in the identity of one (or more) communication user. Such a process may be either unilateral (the users are involved in a conversation in which only one of them, called the verifier, gains confidence that it is the other, called the prover, with whom he is speaking) or mutual (both users gain confidence about the identity of the communication partner). Moreover, the users might share some secret information, or might not. A one-message unilateral entity authentication scheme allows one party, called the prover, to authenticate himself, i.e. to prove his identity, to another party, called the verifier, by sending a single authentication message. We consider schemes where the prover and the verifier do not share any secret information, such as a password, in advance. We propose the first theoretical characterization for one-message unilateral entity authentication schemes, by formalizing the security requirements for such schemes with respect to different kinds of passive and active adversaries. More in details, we consider both static and adaptive adversaries for each kind of attack (passive/active). Afterwards, we explore the relationships between the security notions resulting from different adversarial behaviours for one-message unilateral entity authentication scheme. Finally, we propose three different constructions for one-message unilateral entity authentication schemes and analyse their security with respect to the different security notions previously formalized in the work. [edited by Author]