What do you mean? When users sign up to a Key Registry, they are explicitly acknowledging that their emails and public keys can be used in the way described by the protocol. AFAIK, that's perfectly legal.

This assumes all requests are made by the owner of the e-mail address, with sufficient understanding to give consent vs. e.g. an e-mail provider that fails to understand the privacy concerns.

Even then, as pointed out by others, this does not preclude the user from withdrawing consent to continued use of the information.

It may or may not become a legal problem. But they really need to consider the privacy implications and have lawyers that actually know the relevant national laws throughout the EU member states to evaluate it.

in EU, you can say at any point to a company 'delete every piece of personal information about me that you have', and email is considered an personal information. Even if you gave consent, you can withdraw consent at any point in time.

So, basically, I can tell my bank/credit agency/hospital "please forget that I got a mortgage/defaulted/tested positive for HIV"? Doesn't that sound rather risky?

It's not like that. You can demand to be informed about when the data is processed and for what purposes, get a copy of it, request corrections and object to processing in certain circumstances.

In practice, no, you can't demand to be wiped out from the internal database if you creditor. You probably can prevent them from publishing a debtors' list with your name, though.

It's not that simple (in the UK at least), you only have to stop processing information if "unwarranted and substantial damage or distress" is being caused.

Additionally, all stop processing / deletion regulations require a court order, which will be subject to all the usual requirements of justice.

It only takes a single successful demand before an append-only log because untenable.

There are of course exceptions ;)

Yes, but if users later can't remove their information because the list is append only then that may not be legal in the EU.

This is not worst than the key infrastructure right now, that not only reveals all the email address but their relationships.

One more reason to implement the append-only log using blockchain technology. Seems like a good fit. I don't think privacy laws can be applied to a blockchain, but probably that is still unclear. For example, if I post my email address in a Bitcoin transaction, can I then force every user to delete their blockchain?

You would not be able to stop individual users from doing so, but you could potentially make it legally untenable for commercial/corporate operators.

But personally, regardless of legality, if Google implements this with the degree of disclosure of e-mail details, I'll find another operator that isn't implementing this proposal.

The whole point is ease of key exchange. Of course if you don't want any hint of your email details out in the world you shouldn't use it.

Ease of key exchange does not justify publishing what is effectively a public ledger of who I start communicating with when.

I think you're misunderstanding the gossip protocol, but, regardless, that was not the claim I was responding to, it was that the disclosure of email addresses (or a hash of them) with no way to remove them from the Key Directory is somehow beyond the pale for a public (and automated) key exchange system.