Efficient Signatures with Tight Real World Security in the Random-Oracle Model
Christoph Bader
In Proceedings of the 13th International Conference, CANS 2014
Abstract
Security for digital signature schemes is most commonly analyzed in an ideal single user setting where the attacker is provided only with a single public key. However, when digital signature schemes are deployed in practice they are often used by many users, each having its own public key, e.g., in authenticated key exchange (AKE) protocols. Common security models for AKE model real world capabilities of an adversary by allowing it (among others) to corrupt secret user keys. For digital signatures it is well known that security in the idealized single user setting implies security in this stronger and more realistic multi user setting with corruptions. However, the security reduction loses a factor which is linear in the number of users. It is not clear how to avoid this loss in general. In this paper we propose an efficient signature scheme whose security reduction in the above setting is tight. The security reduction loses a factor of about 2. When 80 bits of security are required our signatures are of size roughly 2700 bits.
[paper]