Conversations in-person can be very private. Read a quote from this conversation:
Steve Hsu: You know, when I would visit your [the former Chief Advisor of the British Prime Minister's] house and we would have a serious conversation, we would put our phones outside. When I went into No. 10, they would take my phone and put it into a little cubby hole on the left.
The current gold standard for private communication is people alone in an isolated room, with no devices capable of recording the conversation present. This is how truly important secrets are shared, and this is because any information shared in that room can only leave the room as hearsay. If Sam Altman pulls you into a room and tells you that GPT-8 will be publicly available in September 2024, the importance of that statement is inherently tied to the fact that Sam Altman was the one saying it. You could go out and say, "GPT-8 will be publicly available in September 2024", but who would confidently believe that, coming from some random? And even if you claimed that you talked to Sam Altman and Sam was the one who said it, Sam could easily deny having done so, creating a classic "he said, she said" situation. [1]
It's galling to me that we have no digital version of this important mode of communication. We have digital bulletin boards, digital signed mail, digital newspapers and digital books, but we don't have the digital equivalent of two people privately conversing in isolation. I personally care about this, because this missing digital communication mode seems like one of the main obstacles to online friendships forming. People can feel this, to the point where we've tried to paper over the issue with anti-leaking norms: there's a Sword of Damocles hovering over everyones' heads, where every private message they send to friends has the potential to be screenshot with cryptographic proof, permanently associating that message with them. Whether you think any particular person you're communicating with will actually do this to you, the knowledge that your private messages can be permanently associated with you changes, at least subconsciously, the type of messages you send in the first place.
But what if it didn't have to be this way? We would like our messaging apps to be such that someone can send a message, and only the intended recipient can ever be convinced that they sent it [4]. Somewhat surprisingly, cryptography, paired with good app design, allows us to do this.
For this post, Alice sends messages, Bob is the recipient of these messages, and Oscar is a third party interested in knowing if Alice sent a message M. Bob is willing to betray Alice by colluding with Oscar, in order to obtain cryptographic evidence: he is willing to modify how he operates in the communication protocol with Alice and send over that modified transcript (including cryptographic artifacts) to Oscar, but he is not willing to compromise his personal private keys or device to Oscar. For why I don't consider these two scenarios here and our thoughts on those scenarios, first read the rest of this section, and then see [5].
Right now, when Alice sends a message M to Bob on an end-to-end encrypted messaging app (such as Signal or WhatsApp), Bob gets evidence that can convince Oscar that Alice sent M. Bob can take screenshots of the messages, or even recordings of the device in the case of a messaging app's self-deleting messages. If Bob is really sophisticated, he can modify the app he's using to store the typically discarded cryptographic transcript of the conversation, getting strong cryptographic evidence that will convince Oscar. Your first thought might have been that existing end-to-end encrypted messaging apps, like Signal or Whatsapp, already have good enough deniability because they have self-deleting messages; sadly, self-deleting messages are merely necessary yet insufficient because they don't stop either of these kinds of evidence.
Our goal is to prevent Bob from being able to get either of these kinds of evidence. We'll start with the cryptographic evidence, because it's actually the easier one to fix.
Current end-to-end encrypted messaging apps use the Signal Protocol to keep messages encrypted, and supposedly deniably authenticate users. The protocol attempts this by initially establishing the sender's deniability through the X3DH handshake, and then extends this deniability for the rest of the conversation using the Double Ratchet algorithm's symmetric key ratchet (and the HMAC it uses). The symmetric key ratchet does its job well, but the problem lies with the initial handshake, which fails to provide deniability for Alice, the message sender.
In section 4.4 of the Signal Protocol's X3DH specification, the following statement is made: "If either party is collaborating with a third party during protocol execution, they will be able to provide proof of their communication to such a third party. This limitation on "online" deniability appears to be intrinsic to the asynchronous setting [2015 paper citation]." This conclusion is actually a misreading of the paper they cite. In section 6.5 and 6.6 of that paper, the authors describe a potential choose-2-of-3 between forward secrecy, non-interactivity and recipient online repudiation (deniability for Bob in the face of an Oscar who wants to coordinate with Bob to change how the protocol is run from Bob's side). But recipient deniability isn't actually what we care about [6]. To create a screenshot-proof messaging app, we just need sender deniability for Alice, and Deniable Authenticated Key Exchanges (DAKEs) like the one laid out in the paper provide this sender deniability: from the paper, "However, [Alice] still maintains online repudiation in this setting—[Alice] can reliably simulate a response from any party, even in the presence of online judges—and all other security properties of the protocol continue to hold. Thus, non-interactive Spawn∗ still provides stronger deniability guarantees than triple Diffie-Hellman (3-DH), the current (non-interactive) TextSecure key exchange protocol."
And so my recommendation is for messaging apps to modify the Signal Protocol such that senders have cryptographic deniability, by using a non-interactive DAKE like Spawn∗ in place of X3DH. I recommend that you do not use the paper's second proposed DAKE, Spawn, because non-committing encryption isn't actually that computationally expensive (even for mobile devices), and the threat model that the paper considers unlikely (that information might not be erased by certain parties (either by choice or not) and that Oscar can adaptively corrupt Bob during the protocol's execution) seems both very plausible to me and important for establishing Alice's sender deniability.
Update: their 2018 paper, the sequel to their 2015 paper, also highlights the need for online deniability (which DAKEs can give, but X3DH falls short of delivering), and offers some new DAKEs that fix some of the shortcomings of the ones proposed in the 2015 paper.
That there is no cryptographic evidence to prove that Alice authored M is actually not enough: if Bob screenshots or records his device, that on its own is often enough to convince people that Alice sent M, especially in more informal settings than a court, like social media. What can be done about this?
Let's look to history for inspiration. Right now, raw footage from a camera is arguably the strongest form of evidence we currently have. It's not literally impossible to edit a video such that it shows something false happening, but the amount of effort required to produce natural-seeming footage (natural-seeming both to our human eye and to our programmatic means of detecting video editing) is extremely high, to the point where people default to trusting footage. Some court decisions have been made entirely on the basis of CCTV footage recording a crime. But as deepfakes become more widespread and easy to use, some people believe that their widespread use will make us lose our trust in video evidence, taking us back to something like the pre-1800s world where older forms of sensemaking and justice needed to be used. Not all at once, of course: right now, deepfakes (which also go by the benign term "generative AI video") either fall into the uncanny valley, have broken physics (see some of the examples here, ctrl-F "room for improvement"), or leave artifacts in the video file that are plainly detectable by programmatic means. But like a GAN, the pressure against discernable deepfakes is very large, meaning this probably won't last forever even if programmatic means for detecting deepfakes try to keep pace.
The core idea is that widespread undetectable deepfakes make video evidence, even legitimate video evidence, a much less reliable indicator of something having actually happened in the real world, because no one can easily discern if a video's real or fake. The same idea can be applied to this post in reverse: if Alice doesn't want screenshots and device recordings to be taken of messages she sends, Bob needs to be able to easily fake that Alice sent a message, so Oscar will have a difficult time trusting him. It needs to be at least as easy to fake screenshots and device recordings as it is to generate them.
My proposed solution is for the messaging app to have a feature where Bob can spoof messages, such that those messages appear to both Alice and Bob as if they legitimately came from Alice. There are a few different ways of doing this, but one that I'm fond of is to design the UI of the messaging window to be like an anonymous messaging board, such that each message has no label or visual indicator (such as by positioning messages from each person on different sides) for who sent which message. Alice and Bob themselves can determine who sent each message, because they know what they personally sent, and can just infer that messages they didn't send came from the other person [7].
This takes care of screenshots, but video of the messaging app (whether a screen capture or a recording of the device itself), still works as evidence because a video could show to Oscar that messages are coming into Bob's app that Bob wasn't sending out himself. One way to make it so Bob could fake even that video is for the app to have the ability to schedule messages. As long as the scheduling of the messages isn't in the video, Bob now has the ability to spoof any potential interaction with Alice [8] [9].
It should be noted that Alice messaging things that Bob would be unlikely to be able to spoof can lose her her deniability. Notable examples include images, which for whatever reason only she could've taken, and messaging stylometry (capitalization, punctuation, word choice, etc), if Oscar for some reason thinks Bob is not capable of mimicking it well [10]. Another is the generalization of the Satoshi's secret phrase example from [1]: if Alice sends some information that only she could have known, Oscar knows that the message undeniably came from Alice [11]. The app should probably warn users so they don't accidentally lose their deniability in one of these ways.
So far, we've only been talking about one-to-one messaging, but group chats are a pretty big part of messaging apps. It is possible to make a group chat where all the members can credibly deny having sent a message, just by expanding the ring signature ring. But for the reasons laid out in [7], this doesn't allow someone to deniably authenticate: not just Oscar, but all the members of the group chat themselves won't be able to tell who exactly sent M. I'm not actually sure if deniable authenication in the group setting is possible, but if it is, it relies on a different principle.
Another possible extension is Signal's sealed sender feature. One issue is that if you make it so people can send messages that are both deniable and anonymized from the server, then you're gonna get quite a bit of spam. Hell, Signal already notes the spam problem in the linked sealed sender blogpost. Solutions to this include things like multiple accounts per user (each with their own private identity key) and automated local spam filters on messages from new people (similar to what email has had for decades) [12].
[1] To be clear, information that can be independently verified is dangerous to release even as hearsay. For example, if someone pulls you into a room and tells you Satoshi's seed phrase, you can take a few minutes to check it yourself. And if you unwisely choose to share that seed phrase with others, they too can take a few minutes to check it themselves and drain the ~$50b wallet, without caring much for where the information originally came from. But the vast majority of information is more like announcing GPT-8 than Satoshi's seed phrase, and confidence in the person authoring a statement is critical in the believability of that statement. [2] [3]
[2] Aside: this's actually one of the core purposes of ethos as a rhetorical mode.
[3] Sam Altman simultaneously messaging "GPT-8 coming out in 9/2024" to all 2500 of his employees, even if all the messages are individually deniable, creates pretty good circumstantial evidence that he said it. Remember: each of his employees here is personally convinced that Sam said the release date, even if they can't prove that Sam said it to other people. The in-person equivalent would be him giving a speech to all his employees in an auditorium, with no recording devices present (eh, disregarding for now that people in an auditorium can see the other audience members hearing Sam's announcement, creating something closer to common knowledge). Journalists and courts have gone off of rumors and hearsay that are far more speculative than the cross corroboration from that would be, and the "he said, she said" judicial idea I linked above only holds up when the number of witnesses on each side are roughly balanced. For reasons like this, one-to-one deniable communication feels far easier to pull off than one-to-many deniable communication.
[4] Note: getting into a room with someone alone, either in-person or in the digital equivalent, requires you to trust they won't do something weird or that you're okay if they do. This (probably?) isn't something you do with strangers. Unlike with end-to-end encryption, which should be turned on by default on all messaging apps, it's not immediately obvious to me that we want screenshot-proof messaging on by default everywhere. I think the way this plays out is there'll be some regular undeniable encrypted messaging apps, and some new messaging apps where all messages are both encrypted and deniable (because you can only even get participation deniability on a messaging app if the very first message is deniable).
[5] Scenarios where Oscar has Bob's private keys or has compromised Bob's device are fairly aberrant, so they're not in the main post. I'll consider them here.
If Oscar is in control of either Bob's device or his private key, either by Bob cooperating or Oscar having compromised the device, Alice still has hope for deniability. The goal is to create a situation where Oscar, despite having access to Bob's device or private key, still has doubts on whether Bob is capable of spoofing a response from Alice or not. I'm not sure what exactly the best way is, but one option is to have Bob's private identity key be derived from from a memorizable password or secret phrase akin to what cryptocurrency wallets currently do, meaning Oscar can never be sure that something Alice sent wasn't a spoofed scheduled message from another device Bob might have. This also helps in scenarios where Oscar, with control over Bob's main device, doesn't just spy on Bob's activities, but also modifies the messaging app to be unable to spoof messages from Alice.
This isn't a bulletproof solution, due to circumstantial evidence: how likely is it that Bob actually managed to memorize the secret phrase, and load it into another device to spoof messages from? However, this's the same class of circumstantial evidence as Oscar simply trusting Bob, due to their working relationship. Our goal, which seems possible from what I've described here and in the main post, is to create at least a sliver of potential mistrust between Oscar and Bob, through which Alice can claim deniability. Widening that sliver helps, but is merely extra credit.
Aside: it's mildly amusing to think about what the equivalent of these scenarios are in the {in-person two people alone in a room} scenario I mentioned in the main post. It's something like Bob having an unnoticed mic or Oscar having Mission Impossible-style face masks and voice changers to talk to you alone in that room, which makes it kinda surprising that we can get even that sliver of deniability.
Update: I recently realized that Oscar, in response to the app having a secret phrase, could try to prevent Bob from ever seeing such a secret phrase by modifying the app such that the secret phrase is never exposed in the UI on creation and cannot be exported later. He might even be able make it so the private key is only handled on the device's trusted execution environment. At this point, any further methods that Bob might be able to use to access the secret phrase, like using an exploit to read the private key from his device's memory, are difficult to believe. I guess it's still open question on whether we can keep that sliver of deniability open.
[6] Eh, we do kinda care about Bob's deniability. But given the potential choose-2-of-3 from the paper, this might involve making the initial handshake an interactive instead of non-interactive protocol, which would mean that a central server (like Signal, WhatsApp, etc all have) couldn't orchestrate communications between the various parties... and that's quite an involved rearchitecting of the system. So it might be possible, but it's definitely outside the scope of this post.
[7] This's roughly the same insight that allows you to achieve deniable authenication using a ring signature or designated verifier signature (either Schnorr or ZKP): if Bob receives a signature proving that "either Alice or Bob signed this message M", and he didn't himself sign M, then he can infer that Alice (or someone with her private key) did. Notably, this doesn't work if you used more than 2 people for the ring signature ring or more than just Alice for the alternative branch of the designated verifier signature, because then Bob can only narrow down the possibilities, instead of immediately learning who signed M deniably. Aka the sacred knowledge that 2 - 1 = 1, but >2 - 1 != 1.
[8] Refer to the solutions suggested in [5] if the video being taken of Bob's device is 24/7, such that scheduling messages from the same device as the video being taken isn't an option.
[9] There's some nuance regarding where the scheduled messages are queued up. If they're queued on the servers, there's an issue of how the server gets the latest key in the conversation's symmetric key ratchet before sending the message off to all parties, because unscheduled messages could have been sent in the time between the scheduled message's scheduling and sending. For this reason, it's probably better to queue them up on device. The concern that on-device storage of scheduled messages could be monitored by Oscar is ameliorated by realizing that Oscar having that capability implies Oscar could also see the messages being scheduled in the first place, which means you need the solutions suggested in [5] anyway.
[10] To prevent these two types of deniability breaking, it might be possible to have LLMs normalize the style of all parties (while keeping message content the same), and to have sent images be passed through some diffusion model to scramble the list of potential image authors a bit. But these ideas are outside of the scope of this post.
[11] On the other hand, if "Alice" sends something that she couldn't possibly have known, Oscar knows that Bob has for some reason spoofed Alice. This's more of a recipient deniability issue than a sender deniability one though, which we address more in [6].
[12] E2EE messaging apps all have a built-in notion of a new conversation, because they can just check if a particular conversation is already in its symmetric ratchet (as opposed to the initial DAKE or X3DH handshake). Even if a user uses disappearing messages, that cryptographic data is still there.
