[edent]

It is perfectly possible to encrypt a message such that two different keys can decrypt it. There is nothing in modern encryption that makes that impossible. See https://faculty.cc.gatech.edu/~aboldyre/papers/bbks.pdf and many others.

So your chat app encrypts your message with the recipient's public key and the state's public key.

Hey presto, you have a message which cannot be read by someone who casually intercepts it. If the state seizes your message - or records it for later analysis - they do not need to break encryption. There's no plain-text version laying around for anyone to sniff.

Is this a good idea? No. Even ignoring the civil liberties aspect, we know that key management is extremely difficult. A leak of the state's private key(s) could be devastating.

But let's not pretend that this is somehow technologically impossible.

[analog31]

>>> A leak of the state's private key(s) could be devastating.

Preventing this leak is what's technologically impossible. A leak includes when the government that's keeping the keys decides to start abusing their access to the data.

[edent]

It's really hard to say whether something like that is impossible.

I'm not aware of, for example, Google's private signing keys for Android being leaked. Sure, plenty of CAs have been breached - but not all. That suggests it is possible to key these keys secure.

[analog31]

That's fair. But it turns "possible" into a statement about a company's or government's expected degree of restraint, rather than a mathematical statement about the robustness of an encryption scheme.

The famous case is what happened to government birth records when the Netherlands were overrun by Germany in WWII. They weren't even encrypted, but mere transfer of access led to tragedy.

[wizzwizz4]

Why would someone want to breach Google's private signing keys? It's easy enough to get malware signed just by submitting it through their ordinary processes.

A better analogy would be the keys used by Microsoft to secure Outlook inboxes.

[palata]

> Sure, plenty of CAs have been breached - but not all. That suggests it is possible to key these keys secure.

"Sure, plenty of people lose at the casino - but not all. That suggests it is possible to find a winning strategy."

[GeoAtreides]

> Preventing this leak is what's technologically impossible.

Is it? Put the key in a TPM module in a well guarded server in a well guarded datacenter. Have the prosecution send the encrypted blob to the server and then receive the messages in clear from the server.

That way, there is absolutely no way the private keys can be leaked.

[dmitrygr]

When people say it is impossible, they clearly mean it is impossible to do in a way that isn’t entirely broken by losing one key. You know this and please don’t pretend that you don’t. When competent cryptographers say the word impossible it has a very clear definition.

[edent]

But how is that any different from the intended recipient losing control their key?

Take a look at the number of people who lose their crypto keys and watch their money vanish.

All encryption is broken by the virtue that key management is impossible for most people.

[amarant]

The intended recipient does not hold a master key to an entire nations communication. That's the difference.

[toss1]

The govt key decrypts everything, real-time and stored/archived, sent in that nation during the time it is in use, and that key is in use in multiple places/machines, and is in an org that is a high-profile target for many other reasons (so could likely be exposed in a crack that initially had other purposes.

In contrast, a person's key can decrypt only that person's messages, is used only in one place (usermset of machines), and is a generally low-value target.

Insanely huge difference between losing a person's key vs the key to an entire nation's communications, even if it is the key of the nation's president -- still far lower value & consequences (start with: if you have the nation's key you can decrypt the president's comms anyway).

[Akronymus]

One person losing control of their keys only really affects them and people they talk directly to. The government having some super key(s) that access everyones messages affects everyone.

[thaumasiotes]

> It is perfectly possible to encrypt a message such that two different keys can decrypt it. There is nothing in modern encryption that makes that impossible.

Not really, any more than it's possible to write a message that says the same thing whether you read it in English or Swahili. You might be able to do it once as a novelty, but the approach won't generalize.

There are multiple-recipient schemes, but they don't rely on using two different keys to decrypt the same message. Instead, you encrypt the message (once) using a (single) symmetric key, and you prepend a bunch of different messages saying "the symmetric key is xxxxxxxxxxx", one for each intended recipient. Those are encrypted with keys specific to each recipient, and each recipient has to attempt to decrypt them all and select the one that decrypted successfully.

The paper you link appears to be discussing an entirely different problem: its definition of a "multi-recipient encryption scheme" does not contemplate sending the same message to several different recipients:

> There are n receivers, numbered 1, ..., n. Each receiver i has generated for itself a secret decryption key sk_i and corresponding public encryption key pk_i. The sender now applies a multi-recipient encryption algorithm to pk_1, ..., pk_n and messages M_1, ..., M_n to obtain ciphertexts C_1, ..., C_n.

> Each receiver i can apply to sk_i and C_i a decryption algorithm that recovers M_i.

> We refer to the primitive enabling this type of encryption as a multi-recipient encryption scheme (MRES).

Note that there is no requirement for anyone other than recipient i to be able to understand message M_i. As described, all encryption schemes are multi-recipient encryption schemes, because you can just consider each message M_k individually and encrypt it to recipient k using a single-recipient scheme.