I had an idea to use something like public message boards to pass secrets anonymously and non-interactively (similar to TV/Movie Trope : http://tvtropes.org/pmwiki/pmwiki.php/Main/PublicSecretMessage ). So here's the basic construction: Bob encrypts a message for Alice and then posts it with an anonymous address tag. Bob calculates this anonymous address using a pre-agreed elliptic curve (EC) by selecting a secure random value r and posting the address tag as (I, J) = (rG, rA), where G is the generator point and A is Alice's public address point. Alice then knows (wvhp) the message is for her if a * I = J. I postulate this is anonymous as it is basically the Decisional Diffie-Hellman assumption as I understand it (right?).

One concern I have is that given a significant number of messages it would become somewhat computationally expensive to perform a large number of scalar multiplications (especially if Alice were my thermostat or my front door lock).

So I'm looking for a much more efficient but not necessarily definitive mechanism for Alice to reject the majority of messages without divulging the intended recipient of the message. So here's the problem statement:

  • Alice must be able to calculate the bloom filter value efficiently (much more efficient that scalar multiplication of an arbitrary EC point), it can be substantially more expensive for Bob

  • Eve should not be able to infer that the message is more likely to be intended for Alice than any other message

  • There should be no false negatives (i.e. every message intended for Alice should pass the filter)

  • There should be a low false positive rate, potentially configurable (i.e. most of the messages not for Alice are rejected by the filer)

  • The bloom filter tag/element should not be large (or not significantly larger than two encoded EC points)

  • The plaintext message size for the tag could be relatively small (32 bits or even 16 bits) as even with a 16 bit tag the filter could have a false positive rate as low as 1/65536.

So given that problem statement, anybody got an idea on an implementation?

(btw, I've been looking into proposed cryptocurrency stealth addresses, which are essentially the same "ratio of EC Points"... but those designs don't seem to improve the performance)



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.