Storing PQXDH Kyber Prekeys on a Messaging Server: An Operator's Guide

Adding Kyber to the Signal handshake makes every prekey bundle about ten times larger. The PQXDH spec tells clients what to publish, but very little is written for the people who run the server that stores those keys. This post covers the sizes, the key types and their lifetimes, how to hand keys out atomically, when to replenish, what the server should check, and what it costs per device. Everything about Lupyd below comes from the code of Firefly, our open-source messaging engine, and every number is either worked out from the spec and libsignal or measured.

What PQXDH Asks the Server to Store

PQXDH extends X3DH with a post-quantum KEM. Per the specification, Bob uploads his identity key, a signed curve prekey, a signed last-resort PQ prekey, a set of one-time curve prekeys, and a set of signed one-time PQ prekeys. When Alice asks for Bob's bundle, the server hands out one one-time PQ prekey and deletes it. If Bob has none left, the bundle carries the last-resort PQ prekey instead. The spec gives Kyber-1024 as the example parameter set, and libsignal's KeyType::Kyber1024 is what Signal and Firefly both use.

libsignal serialises every public key with a one-byte type prefix. A Curve25519 key is 32 bytes of key material, so 33 bytes serialised. A Kyber-1024 public key is 1568 bytes, so 1569 serialised. Signatures over prekeys are 64-byte XEdDSA signatures made with the identity key.

The last-resort key exists so that a session can always be started, even when an offline device has run out of one-time keys. The cost is that it is reused. As a libsignal maintainer put it in issue #547, Kyber prekeys work like the curve one-time prekeys, except clients keep a last-resort key that is not discarded after use. The spec also notes that an initial message that used no one-time prekey can be replayed to Bob and he will accept it.

How Lupyd Stores Prekeys: Whole Bundles

Firefly does not keep separate pools. The server table holds complete, ready-to-use bundles, one row each, serialised as a protobuf PreKeyBundle:

CREATE TABLE IF NOT EXISTS pre_key_bundles (
  id INT NOT NULL DEFAULT floor(random() * 32000)::int,
  address BIGINT REFERENCES addresses (id) ON DELETE CASCADE,
  bundle BYTEA NOT NULL
);

CREATE INDEX IF NOT EXISTS pre_key_bundles_addr ON pre_key_bundles (address);

On the client, every bundle gets its own one-time curve prekey, its own signed curve prekey and its own Kyber-1024 prekey, each signed by the identity key. Key IDs are random numbers below 32,000.

const MAX_KEY_ID: u32 = 32000;
let pre_key_id = rng.next_u32() % MAX_KEY_ID;
let kyber_key_id = rng.next_u32() % MAX_KEY_ID;
let signed_pre_key_id = rng.next_u32() % MAX_KEY_ID;

let pre_key = KeyPair::generate(&mut rng);
let signed_pre_key = KeyPair::generate(&mut rng);
let kyber_pre_key = kem::KeyPair::generate(KeyType::Kyber1024, &mut rng);

let signed_pre_key_signature = identity_key_pair
    .private_key()
    .calculate_signature(&signed_pre_key_public, &mut rng)?;
let kyber_pre_key_signature = identity_key_pair
    .private_key()
    .calculate_signature(&kyber_pre_key_public, &mut rng)?;
// all three private records are saved locally, then the public halves
// are returned as one bundle for upload

The result is that every key a peer receives is used for one bundle only. There is no last-resort Kyber key and no signed prekey shared across bundles, so signed prekey rotation happens automatically: a new signed prekey is created with every bundle.

The trade-offs. Whole bundles make the claim a single-row delete with no joins across key pools, and no key is ever handed to two peers. They also cost storage: a reused signed prekey and identity key are stored again in every row, and without a last-resort key, a device that has used up its bundles cannot be reached by new peers until it comes back online and uploads more. Signal's design accepts a reused PQ key so that this never happens. Ours accepts unreachable devices so that keys are never reused. Which one fits depends on how long your devices stay offline compared with how often new conversations start.

Bundle Size Arithmetic

Each protobuf field costs a one-byte tag, a length prefix for byte fields, and the data. The Kyber key is longer than 127 bytes, so its length prefix takes two bytes. Firefly's IDs (registration, prekey, signed prekey, Kyber prekey) are below 32,000, so each varint is one to three bytes.

The Kyber key and its signature account for 1,572 + 66 = 1,638 of those bytes, about 90%. Take them out and the same bundle is about 183 bytes. For scale, a 512 KiB upload, the server's body limit, could carry 524,288 / 1,825 ≈ 287 bundles, but the per-device cap described below stops it at 64.

Atomic Claim-and-Delete

A one-time key handed to two senders is no longer one-time. Firefly picks and removes one bundle per device of the target user in a single statement:

WITH selected AS (
    SELECT chosen.pre_key_ctid
    FROM addresses a
    CROSS JOIN LATERAL (
        SELECT pk.ctid AS pre_key_ctid
        FROM pre_key_bundles pk
        WHERE pk.address = a.id
        ORDER BY random()
        LIMIT 1
        FOR UPDATE SKIP LOCKED
    ) chosen
    WHERE a.username = $1
)
DELETE FROM pre_key_bundles pk
USING selected
WHERE pk.ctid = selected.pre_key_ctid
RETURNING pk.id, pk.address, pk.bundle,
    (SELECT a.device_id FROM addresses a WHERE a.id = pk.address)

Three details matter:

• FOR UPDATE SKIP LOCKED means two concurrent senders never lock the same row. Each one either takes a different bundle or skips that row. If a device has a single bundle left and two requests arrive together, one gets it and the other gets nothing for that device instead of waiting.
• DELETE … RETURNING returns the bundle and deletes it in the same statement, so there is no gap between reading a bundle and deleting it.
• CROSS JOIN LATERAL drops devices that have no rows. A device with an empty pool is simply missing from the response. This is where a last-resort key would have been used.

ORDER BY random() is cheap here because each device has at most 64 rows. The same pattern, keyed by address IDs instead of username, serves GET /user/preKeyBundles?ids=… when a client only needs specific devices.

Replenishment and Thresholds

The PQXDH spec does not say when clients should upload more keys. In libsignal issue #488, a maintainer described Signal's iOS client checking about every 12 hours and uploading when about two-thirds of its keys are used, and noted that the server does not notify clients when keys run out.

Firefly tops up whenever the client runs its setup check, which happens when it connects and when it has to re-register its device address. The client fetches only the IDs of its bundles still on the server, deletes any whose private key it no longer holds, and refills to 32:

// ids of this device's bundles still on the server (GET ?id=..&onlyIds=true)
for bundle in bundles.entries {
    if prekey_store.get_pre_key(PreKeyId::from(bundle.id)).await.is_err() {
        key_ids_to_delete.push(bundle.id); // private half gone locally
    }
}
// DELETE /user/preKeyBundles?addressId=..&ids=.. for those ids

const MAX_KEYS_LIMIT: usize = 32;
let keys_remaining = bundles_length - key_ids_to_delete.len();
if keys_remaining < MAX_KEYS_LIMIT {
    let keys_to_create = MAX_KEYS_LIMIT - keys_remaining;
    // generate keys_to_create bundles, POST /user/preKeyBundles
}

That reconciliation step is worth copying. If the server and the device drift apart, for example after a local data reset, the server would otherwise keep handing out bundles the device can never decrypt. Checking the private one-time curve prekey by ID is enough to catch this, because every bundle has its own.

The target is 32 on the client and the hard cap is 64 on the server, so a client that uploads twice in a race still cannot grow its pool without limit.

What the Server Must Check

The server cannot read messages, but it decides which keys a sender gets, so it must not let one user upload keys for, or swap keys into, another user's devices. On upload (POST /user/preKeyBundles), Firefly's server:

• requires a valid access token and takes the username from it, not from the request body;
• rejects bodies over 512 KiB and anything that is not a PreKeyBundleEntries protobuf;
• rejects a batch if any entry has no bundle, or if entries name different device IDs or address IDs;
• rejects any entry whose row ID differs from the bundle's preKeyId;
• inside one SQL function, checks that the address belongs to that username and device, and that the device would not end up with more than 64 bundles.

IF NOT EXISTS (SELECT 1 FROM addresses
    WHERE id = address_id AND username = adder AND device_id = p_device_id) THEN
  RAISE EXCEPTION 'address does not exist';
END IF;
SELECT COUNT(1) INTO existing_key_count FROM pre_key_bundles WHERE address = address_id;
IF existing_key_count + cardinality(bundles) > 64 THEN
  RAISE EXCEPTION 'keys are exceeeding limit 64';
END IF;
INSERT INTO pre_key_bundles (address, id, bundle)
SELECT address_id, id, bundle FROM UNNEST(bundles);

Listing all of a device's bundles (?id=…) and deleting them likewise require the address to belong to the requesting user.

What the server does not check: signatures. It stores bundles as opaque bytes. Verification happens on the sender's device, where libsignal's process_prekey_bundle checks the identity key's signature over both the signed curve prekey and the Kyber prekey and refuses the bundle if either fails. Firefly's client also drops any returned entry whose username is not the one it asked for, or whose bundle names a different device than the entry. This is the right place for the checks. If only the server checked, a compromised server could swap in its own keys, so the server should never be trusted to vouch for them.

One more thing to plan for: every claim consumes keys. The spec warns that a server can withhold one-time keys and suggests rate limits on bundle fetches. The same applies to clients that drain a victim's pool on purpose. Firefly's prekey endpoint has no dedicated rate limit in the current server code. With no last-resort key, a drained pool makes the device unreachable for new sessions until it reconnects, so operators of a Firefly-style server should put a per-requester limit in front of it.

Storage Cost per Device

To get real numbers rather than estimates, we created Firefly's pre_key_bundles table and index in PostgreSQL 18.6, filled it for 1,000 devices with 32 bundles each (random bytes of the 1,825-byte typical size), ran VACUUM, and read pg_relation_size. We repeated it with 183-byte rows to see what the same table costs without Kyber.

A few things follow from this. Four Kyber rows fit in a page and a fifth does not (5 × 1,869 is more than the 8,168 usable bytes), so each device's 32 bundles take exactly 8 pages. At the 64-bundle cap that is 16 pages, or 128 KiB. Rows stay under PostgreSQL's default TOAST threshold of about 2 KB, so they are stored inline and never compressed, and random key material would not compress anyway. Kyber makes this table about 8.5 times larger (65,536,000 / 7,716,864). For a million devices at 32 bundles, the heap is 65,536 × 1,000,000 bytes, about 65.5 GB (61 GiB), before WAL and replicas.

Of the raw 32 × 1,825 = 58,400 bytes of bundle data per device, the identity key (33 bytes) and the repeated registration and device IDs are copies in every row. Splitting those out would save little, because the Kyber key is 90% of each row and is unique by design.

Operator Checklist

• Budget about 1.8 KB per stored Kyber-1024 bundle on the wire and about 2 KB of heap per row, and size the table from your device count and pool target.
• Claim and delete in one statement with row locks that skip rather than wait, so no bundle is handed out twice.
• Cap bundles per device on the server, not only in the client.
• Bind uploads to the authenticated user and device; check IDs and device fields match before inserting.
• Leave signature checks to the sender's device; store bundles as opaque bytes.
• Decide on purpose whether you keep a last-resort Kyber key. Without one, add rate limits so a pool cannot be drained.
• Let clients reconcile: list their IDs on the server and remove the ones they can no longer decrypt.

For the background on prekeys and identity keys, see how encryption and keys work. For why Lupyd uses the Signal Protocol for direct messages and MLS for groups, see libsignal vs MLS. The code quoted here is on GitHub.

Frequently Asked Questions

Final Takeaway

Kyber-1024 makes prekey storage a real line item: about 1.8 KB per bundle, 90% of it the Kyber key. The server-side work is still plain database engineering: an atomic claim, a per-device cap, uploads bound to the authenticated device, and a reconciliation path. The real design choice is whether to keep a reused last-resort key or to keep every key single-use and protect the pool with rate limits. Lupyd chose single-use whole bundles. Download Lupyd to see it in use, or read the code.

Last updated: 3 November 2026.