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.

- In
**Foundations of Group Signatures: Formal Definition, Simplified Requirements and a Construction Based on General Assumptions**,**(Eurocrypt 2003)**D. Micciancio, with collaborators M. Bellare and B. Warinschi, laid the theoretical foundation for the study of group signatures by giving the first rigorous definition for this complex cryptographic primitive. Their definition only requires two security properties: strong anonimity and strong traceability. Still, the two properties are strong enough to guarantee security in a variety of previously considered attack scenarios. This work also gives the first probably secure group signature scheme (based on standard complexity assumptions), showing that the strong security notion proposed in the paper can be achieved.

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.

- In
**The provable security of Graph-Based One-Time Signatures and extensions to algebraic signature schemes (Asiacrypt 2002)**, D. Micciancio and A. Hevia propose a practical instantiation of the graph-based signatures of Bleichembauer and Maurer based on the standard primitives of one-way hash functions and pseudo-random generators, and show that the resulting construction is provably secure, provided the building blocks satisfy their respective security notions.

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).

- In
**Efficient generic forward-secure signatures with an unbounded number of time periods**(Eurocrypt 2002), Daniele Micciancio, with collaborators T. Malkin and S. Miner, gave the first forward secure signature scheme that allows for a virtually unlimited number of time periods. The scheme is generic, in the sense that it can be instantiated using any underlying standard (or one-time) digital signature scheme, and had very good performance properties.

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.

- In
**Oblivious data structures: applications to cryptography****(STOC 1997)**, Daniele Micciancio introduces the notion of obliviuos data structure: a data structure that hides all information about the sequence of operations applied to it, except for the final result. An oblivious version of 2-3 trees is then defined and analyzed, and subsequently used to solve the privacy problem for a tree based incremental digital signature scheme of Bellare, Goldreich and Goldwasser.