Crate ecdh_omr

Expand description

§ECDH-OMR: ECDH based Oblivious Message Retrieval

ECDH-OMR aims to solve the following problem:

Alice wants to leave a message for Bob on a server.
The server is not supposed to know that the message is for Bob.
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.
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.

The protocol is designed as a minimal cryptographic primitive focused on a single task: oblivious message retrieval. By keeping the scope narrow and the mechanics simple, ECDH-OMR becomes both formally verifiable and practical to integrate into larger systems. Authentication, rate limiting, and additional encryption layers are intentionally left to other layers, allowing protocol designers to choose implementations that match their specific security requirements.

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 ( Server_SK, ECDH ( Alice_SK, Bob_PK ) )
ECDH ( Bob_SK, ECDH ( Server_SK, Alice_PK ) )

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.

Alice blinds Bob’s public key
- Obtains Bob’s public key (out of band): Bob_PK
- Generates ephemeral secret key: Ephemeral_SK
- Derives blinding factor from ephemeral secret: BlindedBob_BF = G^Ephemeral_SK
- Blinds Bob’s public key, hiding Bob’s identity from the server: BlindedBob_BK = ECDH ( Ephemeral_SK, Bob_PK )
Alice → Server: HintSeed { BlindedBob_BK, BlindedBob_BF, Message }
Server creates hint
- Generates ephemeral (per-request) secret key and nonce: Request_SK, Nonce
- Blinds Alice’s blinding factor: BlindedBlindingFactor_BK = ECDH ( Request_SK, BlindedBob_BF )
- Derives shared secret with Bob from Alice’s blinded materials: ZZ = ECDH ( Request_SK, BlindedBob_BK )
- Encrypts Alice’s message: MessageCiphertext = AEAD Enc ( ZZ, Nonce, Message )
Server → Anyone: Hint { BlindedBlindingFactor_BK, Nonce, MessageCiphertext }
Bob decrypts the server’s hint, revealing Alice’s message
- Recovers shared secret with server: ZZ’ = ECDH ( Bob_SK, BlindedBlindingFactor_BK )
- 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:

Fixed batch sizes: The server always creates the same number of hints (e.g., 5000), regardless of how many real messages it stores
Decoy padding: If there aren’t enough real messages, the server generates fake hints that look identical to real ones
Batch shuffling: All hints are randomly mixed together so observers can’t tell which ones might be important or worth brute forcing
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:

Download everything: The recipient downloads the entire batch without revealing what they’re looking for or who they are
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

§What ECDH-OMR Doesn’t Provide

By design, ECDH-OMR focuses solely on oblivious retrieval and deliberately excludes:

Authentication: Messages are not authenticated, use authenticated encryption or signatures for this
Forward Secrecy: Not inherent to the protocol, but achieved through key management, ideally use one-time or short-lived keys for recipients
Rate Limiting: No built-in DoS protection, implement at a higher layer
Bidirectional Communication: One-way only, compose with other primitives for replies

§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. The batch download approach provides stronger privacy guarantees than selective retrieval schemes, but at the cost of bandwidth efficiency. Consequently ECDH-OMR’s target audience wants to build high-security, moderate-scale systems rather than mass-market applications.

§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. 🐙

Modules§

curves: Shorthands for compatible elliptic curve implementations.

Structs§

BlindedPublicKey: An ECDH public key that has been blinded, enabling a third party to send a message without knowing the cryptographic identity of the recipient.
Hint: Message encrypted by a third party, decryptable by an anonymous recipient that doesn’t know whether it is addressed to them or not.
HintSeed: Pairing of message contents and the BlindedPublicKey of its recipient.
Hints: Batch of Hints that enforces inner vector size as well as shuffling, and also mitigates potential timing leaks at creation time.

Enums§

Error: Error type.

Traits§

Blind: Blind a public key.
Blinded: (De)serialization for BlindedPublicKey.
Decoy: Generate legitimate looking instances of data structures without user input.
Hinting: Semi generic implementations to create new Hints
TakeTheHint: Decrypt Hint and Hints. Also a silly pun.

Crate ecdh_omrCopy item path