Re: Recognising one's own messages on an anonymous broadcast channel?

Kristian Gjøsteen wrote:
<bergstrom.henrik@xxxxxxxxx> wrote:
On 29 Jan, 12:37, Kristian Gjøsteen <kristiag+n...@xxxxxxxxxxxx> wrote:
<bergstrom.hen...@xxxxxxxxx> wrote:
3. No collisions! I.e. no client should mistakenly identify a result
as his own.Ok as long as the nonce is sufficiently long - 128 bits should do it.
We did consider a similar approach - including a random "correlation id" in the input message which is echoed back in the output message - but we need to guarantee that no collisions occur between id:s nonces, etc., not just offering "high probability" of no collisions.

You talked about 10^5 messages per second, or approximately 10^12 ~ 2^40
messages per year. The collision probability for 2^40 128 bit strings is
(very) approximately 2^80/2^128 ~ 2^(-48). If you are unconfortable with
that level, increase the length to 256 bits.

Is it impossible, or does it just require loads of cpu cycles on the server or enough bits in the output?

While there probably are efficient methods, I can only come up with very
silly methods that are less efficient than the above method.


Would constructing a nonce from a 128 bit encryption (sender has and keeps his own key secret) of user ID and unique message number work in this case?
.

Relevant Pages