Score:7

signatures that are verifiably generated by one of several private keys without revealing which one

in flag

is there an encryption algorithm that allows to:

  • generate a set of different private keys
  • sign data with those private keys
  • allow to publicly verify that such a signature has been created by ONE of keys in the set without revealing which one it was
  • give the person that did create the signature a way to create a proof that the signature was created by him specifically

If so, which one has these properties?

Score:10
es flag

This is called a Linkable Spontaneous Anonymous Group Signature (LSAG).

I describe below an EC implementation of an LSAG called a linkable ring signature.

A ring signature proves that the private key holder of one of a set of declared public keys has signed a message, but it is impossible to know which key holder did it. This is called Signer Ambiguity.

This can be extended to the concept of a "linkable ring signature". The ring is signed such that a "key image" is also declared as part of the signature. The key image is the scalar multiplication of the signer's private key on a public key created by extracting a point from the hash of the signer's public key. key image = private key * hash_to_ec_point(public key). The construction of the ring signature proves that the key image is formed from the same private and public key owned by the real signer, without an observer being able to tell whom the key image belongs to.

The real signer can prove they were the real signer by providing a signature (such as a simple Schnorr signature) proving they know the private key for the key image that was declared as part of the original linkable ring signature.

For an implementation example, see "Back’s Linkable Spontaneous Anonymous Group (bLSAG) signatures". I've included the algebra below, excerpted from Zero to Monero section 3.4.

enter image description here

Score:0
cn flag

If when you write "sign data with those private keys", you mean "sign data with one of this private keys" You can achieve the three first properties with Group Signatures. About the last property, you can probably achieve this by using a system proof of knowledge compatible with the Group signatures.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.