ECDH-OMR: ECDH based Oblivious Message Retrieval

ECDH-OMR aims to solve the following problem:

1. Alice wants to leave a message for Bob on a server.
2. The server is not supposed to know that the message is for Bob.
3. Eve should neither be able to count the amount of real messages available for pick-up on the server, nor if new messages came in or old ones were removed.
4. Bob should be able to pick their message up from the server without the server knowing whether this has happened or not.

ECDH-OMR solves this by using the commutative property of Diffie-Hellman key exchanges to implement a form of public key blinding, allowing third parties to send messages to a recipient this third party cannot identify at rest or when relaying it. It enables a form of Private Information Retrieval.

This library implements this scheme with x25519-dalek and (generically) with RustCrypto's elliptic-curves, as well as their AEADs (again, generically).

Warning This work has not yet been independently audited!

While the scheme at its core received preliminary reviews with positive results, more rigorous proofs should be published before considering its use. The implementation is a first stab at what a reasonable generic API for this could look like and has not received any reviews so far.

For experimental use and research only.

Basics

Although not widespread in practice, ECDH supports multi-party shared secrets due to its commutative nature. This allows keys to be combined in different orders while still producing the same shared secret:

• ECDH ( ServerSK, ECDH ( AliceSK, BobPK ) )
• ECDH ( BobSK, ECDH ( ServerSK, AlicePK ) )

Because both produce the same shared secret, the server can encrypt messages for Bob without ever seeing Bob's public key, while Bob can decrypt them without revealing his identity to the server.

Single hint scheme flow

For the purposes of this breakdown, we show Alice sending an unencrypted message to Bob through a server. In practice, message encryption would be handled by higher protocol layers.

1. Alice blinds Bob's public key

   • Obtains Bob's public key (out of band): BobPK
   • Generates ephemeral secret key: EphemeralSK
   • Derives blinding factor from ephemeral secret: BlindedBobBF = G^EphemeralSK
   • Blinds Bob's public key, hiding Bob's identity from the server: BlindedBobBK = ECDH ( EphemeralSK, BobPK )

   Alice → Server: HintSeed { BlindedBobBK, BlindedBobBF, Message }

2. Server creates hint

   • Generates ephemeral (per-request) secret key and nonce: RequestSK, Nonce
   • Blinds Alice's blinding factor: BlindedBlindingFactorBK = ECDH ( RequestSK, BlindedBobBF )
   • Derives shared secret with Bob from Alice's blinded materials: ZZ = ECDH ( RequestSK, BlindedBobBK )
   • Encrypts Alice's message: MessageCiphertext = AEAD Enc ( ZZ, Nonce, Message )

   Server → Anyone: Hint { BlindedBlindingFactorBK, Nonce, MessageCiphertext }

3. Bob decrypts the server's hint, revealing Alice's message

   • Recovers shared secret with server: ZZ' = ECDH ( BobSK, BlindedBlindingFactorBK )
   • Decrypts server's message ciphertext, recovering Alice's message: Message' = AEAD Dec ( ZZ', Nonce, MessageCiphertext )

At no point does the server need to know Bob's public key to encrypt a message to Bob.

Multi-hint scheme flow

In practice, servers don't process individual hints but rather batches of hints to obscure communication patterns and protect against traffic analysis.

On the server:

1. Fixed batch sizes: The server always creates the same number of hints (e.g., 5000), regardless of how many real messages it stores
2. Decoy padding: If there aren't enough real messages, the server generates fake hints that look identical to real ones
3. Batch shuffling: All hints are randomly mixed together so observers can't tell which ones might be important or worth brute forcing
4. Ephemeral keying: Each batch generates new secret keys, ensuring identical messages create distinct ciphertexts across batches which remain decryptable by their intended recipients

This creates indistinguishable hint batches where observers cannot determine how many real messages exist, how many recipients there are, or when messages were added and removed.

On the client:

1. Download everything: The recipient downloads the entire batch without revealing what they're looking for or who they are

2. Trial decryption: The recipient attempts to decrypt every hint. Only hints encrypted with the recipient's blinded public key will decrypt successfully, while others fail silently

API Flow

For an annotated version of this that involves the use of "decoy hints", please see examples/decoyed.rs.

use ecdh_omr::{curves::X25519, Blind, Hinting, TakeTheHint};

use rand_core::{OsRng, RngCore};
use x25519_dalek::*;

type Hint = ecdh_omr::Hint<X25519, ocb3::Ocb3<aes::Aes128>, 32>;

fn main() {
    // Bob
    let bob_secret = StaticSecret::random_from_rng(&mut OsRng);
    let bob_public = PublicKey::from(&bob_secret); // -> Alice

    // Alice
    let bob_blinded = bob_public.blind(&mut OsRng); // -> Server
    let alice_message = [42u8; 32]; // -> Server

    // Server
    let mut salt = [0u8; 32];
    OsRng.fill_bytes(&mut salt); // -> Bob
    let hint = Hint::new(&bob_blinded, &alice_message, &salt, &mut OsRng).unwrap(); // -> Bob

    // Bob
    let bob_recovered_message = bob_secret.take_the(&hint, &salt).unwrap(); // ✅

    assert_eq!(alice_message, bob_recovered_message);
}

Notes

Terminology

ECDH-OMR's namesake is the 2022 paper Oblivious Message Retrieval (eprint) by Zeyu Liu and Eran Tromer, which describes a protocol using Fully Homomorphic Encryption to achieve similar properties where a server stays oblivious as to which messages a recipient decrypts.

A key difference in terminology between the two approaches though is that ECDH-OMR's uses the term hint where OMR would use clue. However, the author's use of hint precedes their awareness of OMR, and they decided to stick with it: Clues are usually more concrete pieces of evidence that directly point towards a solution or answer, whereas hints are commonly more veiled indications that can guide someone towards the intended meaning without giving away the game. Clues you can collect and combine, while hints you have to "get" by using pre-existing knowledge, or in a more adversarial setting you may also be asked to "take" them.

Scale

Fundamentally, because it is a polling based scheme, rather than Fuzzy Message Detection (eprint) for example where the server does matching work, its scale is limited by bandwidth in addition to compute.

Post-Quantum Considerations

• CSIDH/CTIDH technically supports this scheme, but aren't researched well enough to be viable at this point. Due to the scale limitations of ECDH-OMR though, it may be conceivable that CTIDH-OMR or ECDH-CTIDH-OMR could be usable in certain circumstances, provided the implementation is fast enough to handle a reasonable amount of hints. An experimental non-constant-time proof-of-concept is available.

• ML-KEM is not commutative, so this would require a way for a third party to change the ciphertext without changing the secret embedded within. We're not aware of whether this is possible or not.

Acknowledgements

ECDH based Oblivious Message Retrieval was developed by @eaon as part of Reach, an end-to-end encrypted communication platform designed for collaborative groups who wish to let anonymous individuals contact them with information and/or requests. Reach and the research that led to this crate has been self-funded so far, please get in touch if you would like to change that 😉

The author also contributed the scheme to SecureDrop's E2EE protocol research.

• The author would like to thank Davide @TheZero for his early contribution to the aforementioned research, whereby an unusual use of multi-party Diffie-Hellman key exchanges were used to ephemerally "prove" secret key possession in a challenge/response protocol.

• The author would also like to express their gratitude to Jacob Young for highlighting how the challenge/response protocol would allow servers to quickly correlate messages and infer identity properties of recipients, leading the author to take up this problem once again. And then also for taking even more time at Recurse Center to review the ECDH based Oblivious Message Retrieval scheme implemented in this crate. 🐙