[Cryptography] Aggregate signatures

[Dirk-Willem van Gulik]

On 8 Jun 2014, at 11:47, xor <crypto at idlecore.com> wrote:

> I'm a programmer, I need a way to have several people sign the same
> message, and then send that message to several other people. I'd like to
> be able to scale 'several people' to up to a million, so a list of
> individual signatures doesn't work so well. I'm not sure what
> cryptographic tool I require, but I'm looking into aggregate signatures.
> Something like this:
> 
> http://theory.stanford.edu/~dfreeman/cs259c-f11/finalpapers/aggregatesigs.pdf
> 
> I couldn't find however a single implementation, I couldn't find one in
> openssl, nss, or anywhere else. Does anyone know of a decent
> implementation? Does anyone know if there is even a standard?

Firstly - a million private keys  is a very large number - even in todays internet day and age - it is hard to find a PKI environment that large (but for a few; such as  build-in certs on certain classes of mobile phones, the various medical cards, passports).   So getting that going - i.e. enough keys - is going to be hard.

Having said that - the current PKCS#7 scheme (e.g. as used in S/MIME)  is not that inefficient; it is a fairly compact record of the signature with a modicum of metadata. So if you assume you are going to track at least who signed \& when - it is not a bad start. It is well below a 100 bytes for a simple signature; with over 80% taken up by the actual signature, the time stamps, the sha signed and the keyids.  You can get very close to optimum if you leave out the S/MIME Capabilities block.

And as ASN1/S-mime parsers are quite fast and forgiving - it is very easy to experiment with this.

If you are looking at combining multiple pools of people who have signed; and for some reason concatenating the them ‘flat’ is not an option - check out the bibtex below. We found it fairly easy to implement; but in the end settled on simply concatenating PKCS#7 records; as it was compact; and we gained nothing from nesting/overlapping, etc (our usecase was a test with massive signing by the populous of what ‘they had observed’ at some point - ssl observatorium style).

Thanks,

Dw.

http://cs-www.bu.edu/~reyzin/papers/multisig.pdf

@inproceedings{subgroup-sign-Micali:2001:AME:501983.502017,
author = {Micali, Silvio and Ohta, Kazuo and Reyzin, Leonid},
title = {Accountable-subgroup Multisignatures: Extended Abstract},
booktitle = {Proceedings of the 8th ACM Conference on Computer and Communications Security},
series = {CCS '01},
year = {2001},
isbn = {1-58113-385-5},
location = {Philadelphia, PA, USA},
pages = {245--254},
numpages = {10},
url = {http://doi.acm.org/10.1145/501983.502017},
doi = {10.1145/501983.502017},
acmid = {502017},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {digital signature, multisignature},
}
@article{Okamoto:1988:DMS:48012.48246,
author = {Okamoto, Tatsuaki},
title = {A Digital Multisignature Scheme Using Bijective Public-key Cryptosystems},
journal = {ACM Trans. Comput. Syst.},
issue_date = {Nov. 1988},
volume = {6},
number = {4},
month = nov,
year = {1988},
issn = {0734-2071},
pages = {432--441},
numpages = {10},
url = {http://doi.acm.org/10.1145/48012.48246},
doi = {10.1145/48012.48246},
acmid = {48246},
publisher = {ACM},
address = {New York, NY, USA},
} 
@misc{agg-sigs-cryptoeprint:2002:175,
   title = {Aggregate and Verifiably Encrypted Signatures from Bilinear Maps},

   author = {Dan Boneh and Craig Gentry and Ben Lynn and Hovav Shacham},

   howpublished = {Cryptology ePrint Archive, Report 2002/175},
   year = {2002},
}