Check out the new USENIX Web site.

Home About USENIX Events Membership Publications Students
Abstract - Security Symposium - 2000

Probabilistic Counting of Large Digital Signature Collections

Markus G. Kuhn, University of Cambridge


A large number of people digitally sign the same document. The signature collectors want to use only a small amount of memory to demonstrate to any third party approximately how many persons have signed it. The scheme described in this paper uses a non-uniform secure hash function to select a small subset of signatures that the collectors store. The size of this subset becomes a verifiable estimate for the logarithm of the number of signers.

Applications for this scheme range from Web page metering, through ranking mechanisms for electronic discussion systems, to the distributed verifiable and scalable delegation of power in jointly-administrated systems.

  • View the full text of this paper in PDF form.

  • If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.

  • To become a USENIX Member, please see our Membership Information.

?Need help? Use our Contacts page.

Last changed: 29 Jan. 2002 ml
Technical Program
Conference index