# Distributed key generation + signature scheme?

I'm looking for a special signature scheme that has the following features:

1. There is a group. The group consists of $n$ key centers and 1 user.
2. All group members have their own private keys, and public keys that satisfies feature 3.
3. If the user signs (or, private key operation) a message using his private key, then the $n$ key centers (or specific $t < n$) can find out what the public key that used to sign the message is (or, who is the user).

Is there any scheme appropriate for these features? Or a scheme which is similar?

I looked at lots of signature schemes such as group/threshold/ring..., but I cannot find a suitable one.

• If the user signs a document, how is someone supposed to validate that signature? If the user exports a public key, can't someone with that public key validate the signature (and thus identify the user)? Or, are there actually $N$ users, and they can all sign the document with the same public key (and you want anonymity of the signer unless $t$ key cernters collude? – poncho Nov 8 '16 at 12:21
• @poncho When the signer signs the message using his private key, I want for the all other n (or t) key centers should be able to cooperate to be able to verify the signature. (I assumed that pub/priv key pairs are not just rsa key pairs, and it is very connected) – takita Nov 8 '16 at 12:40
• Although someone who is not in a group knows the public key of the user, but I want he cannot verify the signature. – takita Nov 8 '16 at 12:42
• If the sole requirement is "any $t$ key centers can validate the signature (and verify the user), no one else can validate anything", then why don't you just use a $(t,n)$ secret-sharing scheme for the public key, and give each key center one share? – poncho Nov 8 '16 at 12:45
• Sounds like a group signature scheme with group manager key threshold-shared to $n$ centers. User signatures are verifiable against public key of the group. Please double-check operations/definitions for group signatures. Not sure whether key sharing was explicitly described in the context of group signature scheme anywhere; just pick appropriate general sharing. – Vadym Fedyukovych Nov 8 '16 at 14:29

If I understand you correctly, you want a system designed such that

• A group of $n+1$ people -- Alice, Bob, Eve, Trent, and James -- each have their own private key, and each one knows who is in the group and all of the corresponding public keys of everyone in the group.
• Alice can sign a message and package the message and the signature, and then transmit the packaged message publicly in such a way that:
• Any one person in the group, such as Eve -- using only the information in the packaged message itself and her own list of people in the group and their corresponding public keys -- does not have enough information to figure out who the message came from, without the cooperation of anyone else in the group
• If people in the group cooperate -- all $n$ people cooperate, or some specific threshold of people $1<t \leq n$ -- they can verify that the packaged message was signed with Alice's private key.

Off the top of my head (warning: untested protocol), perhaps something like this would fulfil those requirements:

1. Alice takes the original plaintext message, and signs it with her private key to generate a detached signature file.
2. Alice uses any secret splitting technique to divide a signing message -- something like "My name is Alice, and I sign Manifesto X thus:" concatenated to the detached signature file -- into $n+1$ share files.
3. Alice uses each one of the $n+1$ public keys in her list of group members to encrypt one of the share files.
4. Alice packages up all $n+1$ encrypted share files and (optionally) tags each encrypted file with the name of someone in the group and (optionally) the original plaintext message file, in one big packaged message.
5. Alice securely erases the detached signature file and the (unencrypted) share files, and then broadcasts the packaged message.
6. Eve attempts to decrypt all the share files in the packaged message, but her private key is only able to decrypt one of them (the one tagged "Eve"). Also, the decrypted contents of that file are a share file, which alone is not enough to recover any information about the signing message.
7. If enough people in the group cooperate, they can combine (decrypted) share files to reveal the signing message.
8. Once a person has the original plaintext message and the signing message and Alice's public key, that person can extract the detached signature and use it to verify that Alice's private key was used to sign that message. (If the signing message includes only the detached signature file, without any additional identification, then repeat this step with every public key of everyone in the group to find one that verifies).

I suspect there may be a group signature scheme or ring signature that may be a better solution than the above untested protocol.