This is a practical application of cryptography question and I hope this is the right place to ask it. Any advice would be very much appreciated.

I'm looking for a low-bandwidth, non-interactive protocol for proving a message has traversed some set of relay nodes. These relay nodes communicate via radio and so can only communicate with a small set of nearby nodes.

The key protocol goal is how can you pass a message along a circuit of nodes and at the end prove no one who touched the message has been removed from the list of relays.

One naive solution is to just hash the public key of each relay node before they relay to the next node. Any sequence of public keys that hashes to that final hash is proven to have been part of the circuit. There might be some false nodes added, but no previous nodes are removed.

The problem is that anyone can reconstruct a chain of hashes that omits intermediate public key hashes if they know the first public key in the list.

We want a one-way non-interactive solution for bandwidth saving so there is no way to get the first node to sign the hash along the way. We also don't know the exact list of relay nodes ahead of time.

Aggregate signatures seem like a way to solve this because instead of building up a hash, we have a signature which requires a secret key to generate it. Even if you know the public key list, you can't reconstruct a new sequence of signatures just by knowing the first public key in the list.

If you knew the aggregate signature at an earlier point, you could add your signature from there, but that's fine because it just means you have a shorter path, but you can't take the signature created from a longer path and factor out intermediate signatures after the first one with out having the private keys needed to create those signatures, even if you do know the exact sequence of public keys.

I'm thinking of BLS aggregate signatures as a solution because of their small size and that the protocol is non-interactive (signatures are simply multiplied together).

Am I missing some simpler way to do this?

Are there any other non-interactive schemes that accomplish signature aggregation besides BLS?

  • $\begingroup$ I'm not sure I understand what you need (not through any fault of your own), but for some reason your question reminds me of signatures for network coding. Is that perhaps related? $\endgroup$ – Ella Rose Feb 3 '18 at 1:19
  • $\begingroup$ Very interesting and perhaps a more advanced version of what I'm proposing. This scheme not only could be used to recover the list of signers but also compress the data being relayed. I'll need to read it a few more times though to be sure. $\endgroup$ – Richard Myers Feb 3 '18 at 1:35
  • $\begingroup$ This paper by Katz and Waters gives a bit more of an overview. It's really interesting stuff. I'm still not sure from my skim of these papers if the receiver can identify the signer's identities, or if the signatures can only be used to determine which packets are corrupted. $\endgroup$ – Richard Myers Feb 3 '18 at 2:16

Your Answer

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

Browse other questions tagged or ask your own question.