A digital signature is the electronic counterpart of real life signatures: they can be easily certified as authentic by everybody, but only the legitimate signer can efficiently produce them. Digital signatures are probably the most important and widely used cryptographic primitive enabled by public key technology, and they are the building block of many modern distributed computer applications, like electronic contract signing, certified email, and secure web browsing. More advanced applications often requires more than simple digital signatures. This project expores various extension of the basic concept of digital signatures, providing formal security definitions, solutions, and rigorous security analyses.
The enhanced digital signature schemes we studied so far, fall in 4 categories:
An complex example of enhanced digital signature is given by group signature schemes. A group signature scheme allows several parties to sign messages on behalf of a central organization (the group), while maintaining a controlled form of anonymity: the identity of the signer should be normally conceeled (except for certifying that the signer is a member of the group), but it can be recovered by a special entity (e.g., the group manager) if the situation calls for it. The notion of group signature was originally proposed by Chaum in the early 90’s, and the corresponding notion of security was subsequently refined considering more and more complex kind of attacks, e.g., allowing for collusion, etc. The notion of group signature employed in most early work was informal, and didn’t offer a sufficiently rigorous definition to formally validate concrete proposals.
One time signatures are digital signature schemes with signing and verification times tipically much faster than conventional digital signatures, but whose security is guaranteed only as long as the keys are not used to sign multiple messages. In many cryptographic constructions, this is enough to guarantee security of the overall application, and one time signatures can be profitably used to speed up the signing and verification process. Most one time signature schemes belong to a general class of “graph based” signatures put forward by Bleichembauer and Maurer, but the security of this general scheme was an open problem.
The unforgeability property of digital signatures depend in a critical way on the secrecy of the private key used to sign messages. If the secret key is leaked, then an adversary that knows the key can produce seemengly good signatures. Therefore, not only the legitimate signer need to pick a new key to sign new messages, but also the digital signatures of all previously signed messages cannot be trusted as authentic. Forward secure digital signature schemes alleviate the problem of key exposure, but updating the secret signing key from time to time, so that today’s key cannot be used to sign messages from a previous time period, and past signatures can still be trusted. The first forward secure digital signature schemes required the maximum number of update operations (i.e., number of time periods) to be fixed in advance, and their performance was directly related to this number (logarithmically, or even linearly).
Incremental digital signatures are digital signatures that can be updated (when the underlying document is modified) faster than recomputing the signature from scratch. Incremental digital signatures are useful each time one want to sign many related documents (e.g., letters that follow a template), or automatically mainain digital signatures of documents being written, so that signatures are immediately available. Incremental signature however also rise new security concerns: the signature might reveal information about the way a given document was written, possibly violating the user’s privacy.