0

Suppose I have n subordinates at work. Any subordinate should be able to submit his or her report anonymously to me via digital means.

Also suppose that I have no means of broadcasting any form of information securely to my subordinates. That is - any message I broadcast to my subordinates should be able to be sniffed by an eavesdropper. I am also not able to communicate directly (unicast) one-on-one with my subordinates.

Is there any way to develop a protocol for my subordinates to submit their report while preventing (or identify) attackers (that are not any of my subordinates) forging a report that could also be submitted to me?

There are no other assumptions other than those bolded and I should be free to make any other assumptions as needed.

What I've got so far:

  • Any public key exchange system - Each of my subordinates broadcast their public key which I can use to verify their signature of the message. The problem with this is that it is not anonymous. Each subordinate can be identified using the unique public key once published.
  • 1
    If I'm understanding your question correctly - you should be able to to broadcast your public key. Then, each of your senders would be able to encrypt a message to you using your public key, so that only you would be able to decrypt the message. This allows your senders to submit reports to you securely, and anonymously. Note that your senders will want to ensure that the public key that you advertise is in fact yours, perhaps through some out-of-band means. – mti2935 Oct 16 at 11:13
  • @mti2935 That does not prevent forgery - any other attacker who is not my subordinate can use my public key to encrypt (forge) the report and submit it to me, without me ever knowing. Notice the assumption is that I am unable to broadcast my public key securely and that this particular problem is focusing on the signature aspect, not so much the encryption of public key cryptography. I don't believe the answer to this question is as straightforward as that. – Michael Bluth Oct 16 at 11:23
  • Thank you for clarifying the question, and for editing the question to incorporate these clarifications. So, it boils down to a problem where you want to ensure that the report was sent by one of your subordinates, without you being able to discern which of your subordinates sent the report. And, you have public keys for each of your subordinates, and your subordinates have your public key. Correct? – mti2935 Oct 16 at 11:45
  • @mti2935 Almost correct. If each subordinate has their own unique public key, then the report they submit to me would not be anonymous. For the purposes of the problem, I believe that any individual subordinate that generates and publishes a key pair cannot use the same key pair for encrypting the message to be sent to me, given that they would have to publish the public part of the key pair, hence identifying the individual. If there's somehow a way to mask this - this might work – Michael Bluth Oct 16 at 11:55
2

You can implement this scheme by doing the following:

1.1) Create a key pair.

1.2) Sign the key pair using your private key.

1.3) For each subordinate, encrypt the key pair using the subordinate's public key, and send the encrypted key pair to the subordinate along with the signature that you created in step 1.2. Note, you are sending the same key pair to all subordinates.

Then, each subordinate does the following:

2.1) Subordinate decrypts the key pair that you sent in step 1.3 above using subordinate's private key, and verifies the signature to ensure that it was sent by you. Now, the subordinate has the key pair that you created in step 1.1, and can verify that it was sent by you.

2.2) Subordinate signs the report using the private key from the key pair created in step 1.1. Subordinate encrypts the report using your public key, and sends the encrypted report along with the signature.

Upon the receipt of a report from a recipient, you do the following:

3.1) Decrypt the report using your private key.

3.2) Verify the signature using the public key of the key pair created in step 1.1.

Because only the group of subordinates has the keypair that you created in step 1.1, this ensures that it was one of the subordinates that signed the report. However, because all of the subordinates in the group have the same keypair that you created in step 1.1., you have no way of determining which subordinate signed the report.

  • Perfect. This works under the assumption that I know each and every of my subordinates public key. Just pondering, are there any implications if say an attacker spoofed a message using one of my subordinates public key? (Suppose the attacker had access to a decryption oracle to one of my subordinates under, i.e. attacker possesses CCA capability and can decrypt the message at step 2.1) – Michael Bluth Oct 18 at 7:23
  • If an attacker is able to pull-off an attack like you describe, then yes, this would enable the attacker to impersonate a subordinate. Having said that, most secure protocols that we use today would be compromised if an attacker has the ability to pull off this type of attack. – mti2935 Oct 18 at 14:11
1

if I understood that correctly, you are looking for something which can be achieved via anonymous signature schemes, group signature schemes or ring signature schemes.

There's work to make known signature schemes anonymous (see Yang-Wong-Deng-Wang, PKC’06 / https://eprint.iacr.org/2005/407.pdf). The main difference between group and ring signature schemes is that you can decide who is in a group in contrast to a ring in which every member can add new members.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.