[Cryptography] Feedback requested: ECC anonymous signatures with per-message revocable anonymity and pair-wise message linkability

[Natanael]

@Richard Clayton: I'm aware of Fawkes signatures. They are somewhat
applicable, but in some circumstances they aren't useful and/or safe.

Here's the best case stateless implementation of Fawkes signatures that I
can see that matches this usecase;

Use a seed and a counter to derive commitment values, which are then
committed with hashes in the message and revealed in the next message in
the chain (for keeping your pseudonym alive). To remain stateless, you also
derive counter encryption keys from the same seed and put encrypted
counters in the messages. To create a new message, you must access your
previous one to decrypt the counter so you can safely iterate it.

Multiple messages can also be posted without being linked to previous
messages (don't reveal earlier commitments), and later linked by a single
message revealing multiple commitments. But in this case of not having
simply a single chain of messages, tracking which commitments you have
revealed already requires additional state to be kept unless you have
access to all your messages (tracking which ones is yours could be made
stateless by having an iterated identifier value in the message, derived
from the seed, where you recalculate all identifiers and look up those
messages - but this access leaks metadata that can correlate your different
messages to your identity).

This scheme breaks if you forget the counter and also fails to access the
most recent message (such as if you have to go offline or can't access the
closed network with your most recent messages, and don't have the
electronics with you where you keep the counter updated). Then you'll
repeat your values and keys and the second message will look like a
forgery. If you screw up and publish the message to early after
timestamping its hash as a commitment, you can also break your pseudonym
through causing uncertainty about if the new commitment in the disputed
message is valid or not.

Due to uncertainties in the general perception of timestamping in various
cases (a single somewhat credible entity claiming to have seen the message
earlier than the timestamp causes uncertainty), Fawkes signatures are most
effective even used towards a small target audience (as higher assurances
can be achieved regarding when it really was first seen).

Accessing your most recent message to decrypt the counter can also put you
at a greater risk of local attackers.

Den 14 apr 2015 22:00 skrev "Mattias Aabmets" <mattias.aabmets at gmail.com>:

> Why are you making it so complicated?

1: Its a mental exercise, and I want to see if I can construct something
that actually could work. Keeping it too simple wouldn't be an interesting
mental exercise.

2: Its (subjectively) a neat construction.

3: Flexibility. You've got plenty of freedom even after posting a message
in deciding what to link to what and how. You can link together multiple
messages in independent sets to establish two or more independent
pseudonyms to build reputation. You get to decide when to reveal your
identity.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150415/13b61897/attachment.html>