Signature Options

Here are the various things we can do with signatures, along with references to how computationally expensive the best known implementations are.

Of particular interest are 1 of N and M of N schemes, particularly done via a Schnorr scheme. Here are the main questions of interest.

• How tunable is knowledge of the signers' identities?
  • Does the recipient of the signed message know who signed it?
  • Does everyone in the N-person group know?
  • Does some group admin know?
  • Can the rest of the group figure it out?
• Who can do the "tuning" at which time?
  • Is this controllable when setting up the group of signers?
  • Can the signers choose how anonymous they are within the group?
  • Can the level of anonymity be retroactively changed?

Schnorr signatures

These are of interest because of size and computation efficiency.

Notation

We use the following syntax.

• gh and g*h represent the group "multiplication" of elements g and h. Note that while it may look like standard multiplication of numbers, this is usually at least a little different, such as being modulo some particular number.
• g^x represents x iterations of application of group element g. For example, g^3=ggg.
• || represents concatenation. For example, "abc" || "123" = abc123 and x || y equals the concatenation of the values of x and y.

One signer (default, simplest case)

The basic case is a one-signer method, where the signer has a known public key and anyone can thus verify a signed message. The main advantage is simplicity (implementation, runtime, and size).

Public Parameters

Start with a publicly known (typically Schnorr) group G of large (around 2^256 for 2017-level security) prime order (size) q with generator g and a hash function H. This group must have a hard discrete logarithm problem. This (group, generator, hash function) tuple (G, g, H) defines the public parameters.

A signing user generates a random private key x and publicly releases the corresponding public key x*g. (Recall that x*g is our notation for g^x, that is g "multiplied" by itself x times.)

1-of-N (ring signature variant)

As described here,

Types of signatures

One signer

This is the default use of signatures. Any signature scheme should be able to do this efficiently as its most basic case. Please see here for a list of public-key cryptographic systems, most of which can be used for a single signer use case.

1 of N signatures

This is where one person signs, with the authority of a group of N people.

Ring signatures

Ring signatures are where if one actor out of N in an org signs a message it is known that one of the N actors signed it and nothing more. In particular, not even a "leader" or "manager" in the org can tell who signed it.

Group signatures

• Anonymous unless/until the revocation manager revokes anonymity
• Impossible to tell whether two different signed messages were signed by the same signature
• Implementations:
  • Ballare, Micciancio, Warinschi, 2003
  • Boneh, Boyen, Shacham, 2004
  • Practical Group Signatures without Random Oracles
  • Direct Anonymous Attestation

M of N signatures

This is where at least M people must sign to bear the authority of the group of N people. This is the obvious generalization of 1 of N schemes.

Further reading and other links

• Group Signature Schemes and Payment Systems Based on the Discrete Logarithm Problem (Schnorr signatures and many others)
• signature-json where I'm trying to make signature choice determination scriptable...