Digital Signatures

Digital signatures, not unlike the handwritten ones, are used to authenticate information: that is, to securely tie the contents of an electronic document to a signer (more precisely, to the signer's public key). Only the true signer should be able produce valid signatures, and anyone should be able to verify them in order to convince oneself that the signer indeed signed the document. While many digital signature schemes have been proposed and a few are used in practice today, research into designing schemes that are more secure, more efficient, or have additional properties continues.

Silvio Micali and Leonid Reyzin. Signing with Partially Adversarial Hashing. MIT/LCS/TM-575.

 

Digital signatures usually utilize one-way hash functions designed by other parties. It is thus possible that such hash functions are adverserially designed so as to enable forging signatures in otherwise secure schemes.

We initiate the study of signing with adversarial hashing by considering hash functions for which an adversary can fix arbitrarily the input-output values at polynomially many inputs.

On the negative side, we show that many known signature schemes are vulnerable against such partially adversarial hashing attacks. On the positive side, we show that a surprisingly simple modification makes any scheme invulnerable against such attacks. The computational requirements of our modification are so mild that it could be easily integrated into any signature scheme.

Silvio Micali and Leonid Reyzin. Improving the Exact Security of Digital Signature Schemes.

 

We provide two contributions to exact security analysis of digital signatures:

  1.  
  2. We put forward a new method of constructing Fiat-Shamir-like signature schemes that yields better "exact security" than the original Fiat-Shamir method; and
  3.  
  4. We extend exact security analysis to exact cost-security analysis by showing that digital signature schemes with "loose security" may be preferable for reasonable measures of cost.

 
Note: A preliminary version of this work appears in R. Baumgart (ed.), Secure Networking -- CQRE [Secure] '99, Lecture Notes in Computer Science1740, (c) Springer-Verlag, 1999. A fuller version will soon appear in the Journal of Cryptology.

Michel Abdalla and Leonid Reyzin. A New Forward-Secure Digital Signature Scheme.

 

Ordinary digital signatures have an inherent weakness: if the secret key is leaked, then all signatures, even the ones generated before the leak, are no longer trustworthy Forward-secure digital signatures were proposed in Crypto 1999 by Bellare and Miner [BM99] to address this weakness: they ensure that past signatures remain secure even if the current secret key is leaked.

The work [BM99] also presented a scheme that is forward-secure in the random oracle model. We improve their result by giving a scheme that has significantly shorter keys and is, therefore, more practical than that of [BM99]. By using a direct proof technique not used for forward-secure schemes before, we are able to provide better security bounds not only for our new scheme, but also for the scheme of [BM99].

Bellare and Miner also presented a method for constructing such schemes without the use of the random oracle. We conclude by proposing an improvement to their method and an additional, new method for accomplishing this.

 
This work appears in Advances in Cryptology -- Asiacrypt 2000, Tatsuaki Okamoto, editor, Lecture Notes in Computer Science 1976, Springer-Verlag, 2000. © IACR.

Gene Itkis and Leonid Reyzin. Forward-Secure Signatures with Optimal Signing and Verifying.

 

Ordinary digital signatures have an inherent weakness: if the secret key is leaked, then all signatures, even the ones generated before the leak, are no longer trustworthy. Forward-secure digital signatures were recently proposed to address this weakness: they ensure that past signatures remain secure even if the current secret key is leaked.

We propose the first forward-secure signature scheme for which both signing and verifying are as efficient as for one of the most efficient ordinary signature schemes (Guillou-Quisquater): each requiring just two modular exponentiations with a short exponent. All previously proposed forward-secure signature schemes took significantly longer to sign and verify than ordinary signature schemes.

Our scheme requires only fractional increases to the sizes of keys and signatures, and no additional public storage. Like the underlying Guillou-Quisquater scheme, our scheme is provably secure in the random oracle model.


This work appears in Advances in Cryptology -- Crypto 2000, Joe Kilian, editor, Lecture Notes in Computer Science, Springer-Verlag, 2000. © IACR. 

Silvio Micali, Kazuo Ohta and Leonid Reyzin. Accountable-Subgroup Multisignatures.

 

Formal models and security proofs are especially important for multisignatures: in contrast to threshold signatures, no precise definitions were ever provided for such schemes, and some proposals were subsequently broken.

In this paper, we formalize and implement a variant of multi-signature schemes, Accountable-Subgroup Multisignatures (ASM). In essence, ASM schemes enable any subgroup, S, of a given group, G, of potential signers, to sign efficiently a message M so that the signatureprovably reveals the identities of the signers in S to any verifier.

Specifically, we provide:

  1. The first formal model of security for multisignature schemes that explicitly includes key generation (without relying on trusted third parties);
  2. A protocol, based on Schnorr's signature scheme [Sch91], that is both provable and efficient:
    • Only three rounds of communication are required per signature.
    • The signing time per signer is the same as for the single-signer Schnorr scheme, regardless of the number of signers.
    • The verification time is only slightly greater than that for the single-signer Schnorr scheme.
    • The signature length is the same as for the single-signer Schnorr scheme, regardless of the number of signers.

Our proof of security relies on random oracles and the hardness of the Discrete Log Problem.

            Gzipped PostScript File (286K)
            PostScript File (596K)
            Adobe Acrobat (.pdf) File (318K)

An extended abstract of this work appears in CCS'01, Procedings of the Eighth ACM Conference on Computer and Communications Security, ©ACM 2001. Posted by permission of ACM. 

  •