Two Independent Post-Quantum PGP Implementations Now Interoperate • Daniel Herman

I spent the weekend testing post-quantum cryptography in PGP. Not reading about it - actually generating keys, encrypting files, signing documents, and checking whether two independent implementations can talk to each other.

They can. The standard works. Keyservers don’t accept the keys yet. And almost nobody is using any of this.

The finding

The IETF draft draft-ietf-openpgp-pqc defines hybrid algorithms for OpenPGP - ML-DSA-65+Ed25519 for signing, ML-KEM-768+X25519 for encryption. Two implementations exist:

Sequoia PGP (Rust) - sq 1.4.0-pqc.1, backed by the Sequoia team and Red Hat
Proton’s GopenPGP (Go) - v3.4.1-proton, the library behind Proton Mail

I generated PQC keys with each tool, encrypted messages, and decrypted them with the other:

	Sequoia decrypts	GopenPGP decrypts
Sequoia encrypts	✓	✓
GopenPGP encrypts	✓	✓

	Sequoia verifies	GopenPGP verifies
Sequoia signs	✓	✓
GopenPGP signs	✓	✓

Two teams, two languages, one spec. Interoperability is the whole point of a standard, and this one works.

What broke

Keyservers don’t accept PQC keys. When I tried uploading to keys.openpgp.org:

Error: OpenPGP v6 (RFC 9580) is not yet supported.

PQC requires v6 keys (RFC 9580), and the keyserver infrastructure hasn’t caught up. So right now, you can generate and use PQC keys locally or share them out-of-band, but there’s no public distribution mechanism. This is probably the biggest practical blocker.

Everything else worked on the first try, which genuinely surprised me given these are pre-release implementations of a draft standard.

Performance

Measured on an M4 MacBook Pro (native, not Docker):

Operation	Time
PQC key generation (4 subkeys)	75 ms
Encrypt 1 MB file	179 ms
Sign 1 MB file	14 ms
Decrypt	~180 ms

For comparison, classical Ed25519/X25519 operations are roughly the same speed. The lattice math is not the bottleneck - I/O is.

The size tax

This is the part that matters for infrastructure:

	Classical (Ed25519/X25519)	PQC (ML-DSA-65/ML-KEM-768)	Factor
Public key	889 bytes	47,674 bytes	54x
Encrypted message	344 bytes	1,888 bytes	5.5x
Detached signature	271 bytes	4,752 bytes	17.5x

For encrypting files - irrelevant, 48KB is nothing. For certificate transparency logs, DANE records, keyservers, or anything that aggregates thousands of signatures - this is a real problem. Package managers with PQC signature chains will need to think about bandwidth.

The ecosystem

OpenPGP (IETF) has full PQC - encryption and signing. Sequoia and GopenPGP implement it.

LibrePGP (GnuPG’s fork) supports ML-KEM for encryption only. Koch’s position is that signing “is not an important topic for now.” I think he’s wrong - code signing and package verification are arguably the most important PGP use case left, and those need quantum-resistant signatures. Encryption protects data at rest; signatures protect the supply chain.

Proton co-authored the IETF draft. When they ship PQC to 100M+ users, it’ll be the largest PQC email deployment. But today, if you generate a PQC key, GPG users cannot decrypt your messages.

The build problem

Sequoia PQC requires OpenSSL 3.5+ because ML-KEM/ML-DSA support was only added in March 2025. Debian 12 ships 3.0. Ubuntu 24.04 ships 3.0. Ubuntu 26.04 ships 3.5 and works out of the box. For older distros, you have to compile OpenSSL from source before building Sequoia.

I packaged this into Docker images so nobody else has to deal with it:

docker pull ghcr.io/detrin/pqc/sequoia:latest

On Ubuntu 26.04, you can also build natively (it ships OpenSSL 3.5):

sudo apt install libssl-dev pkg-config capnproto clang libclang-dev
cargo install sequoia-sq --version 1.4.0-pqc.1 \
  --locked --no-default-features --features crypto-openssl

Full walkthrough: Sequoia PQC

Here is the complete workflow - keygen, encrypt, decrypt, sign, verify:

SQ="docker run --rm -v $(pwd):/data ghcr.io/detrin/pqc/sequoia"

# 1. Generate a post-quantum key pair
$SQ key generate \
  --own-key \
  --name "Your Name" \
  --email [email protected] \
  --without-password \
  --profile rfc9580 \
  --cipher-suite mldsa65-ed25519 \
  --output /data/key.pgp \
  --rev-cert /data/key.rev

# 2. Extract public certificate (share this with others)
$SQ key delete \
  --cert-file=/data/key.pgp \
  --output=/data/key.pub.pgp

# 3. Encrypt a file
echo "confidential data" > secret.txt
$SQ encrypt \
  --for-file /data/key.pub.pgp \
  --without-signature \
  --output /data/secret.pgp \
  /data/secret.txt

# 4. Decrypt
$SQ decrypt \
  --recipient-file /data/key.pgp \
  --output /data/decrypted.txt \
  /data/secret.pgp

# 5. Sign a document (detached signature)
$SQ sign \
  --signer-file /data/key.pgp \
  --signature-file /data/doc.sig \
  /data/secret.txt

# 6. Verify
$SQ verify \
  --signer-file /data/key.pub.pgp \
  --signature-file /data/doc.sig \
  /data/secret.txt

Alice and Bob: cross-implementation communication

This is where it gets interesting. Alice uses Sequoia (Rust), Bob uses pqcrypt (Go, built on Proton’s GopenPGP). Different tools, same standard - and they interoperate.

# Alice generates her key with Sequoia
docker run --rm -v $(pwd):/data ghcr.io/detrin/pqc/sequoia key generate \
  --own-key \
  --name "Alice" \
  --email [email protected] \
  --without-password \
  --profile rfc9580 \
  --cipher-suite mldsa65-ed25519 \
  --output /data/alice.pgp \
  --rev-cert /data/alice.rev

# Bob generates his key with pqcrypt (Go)
docker run --rm -v $(pwd):/data ghcr.io/detrin/pqc/gopenpgp keygen \
  --name "Bob" \
  --email [email protected] \
  --pqc \
  --output /data/bob

# Alice encrypts a message for Bob using his public key
docker run --rm -v $(pwd):/data ghcr.io/detrin/pqc/sequoia encrypt \
  --for-file /data/bob.pub.asc \
  --without-signature \
  --output /data/for-bob.pgp \
  /data/secret.txt

# Bob decrypts with pqcrypt - different implementation, works fine
docker run --rm -v $(pwd):/data ghcr.io/detrin/pqc/gopenpgp decrypt \
  --key /data/bob.key.asc \
  --input /data/for-bob.pgp \
  --output /data/bob-reads.txt

# Bob signs a response with pqcrypt
docker run --rm -v $(pwd):/data ghcr.io/detrin/pqc/gopenpgp sign \
  --key /data/bob.key.asc \
  --input /data/bob-reads.txt

# Alice verifies Bob's signature with Sequoia
docker run --rm -v $(pwd):/data ghcr.io/detrin/pqc/sequoia verify \
  --signer-file /data/bob.pub.asc \
  --signature-file /data/bob-reads.txt.sig \
  /data/bob-reads.txt

Two implementations, two languages, two independently generated PQC keys - full interoperability confirmed.

Verify it yourself

I signed the following message with my PQC key using:

echo "This message was signed with a post-quantum key (ML-DSA-65+Ed25519) on 2026-05-30." > message.txt
sq sign --signer-file key.pgp --cleartext message.txt > signed-message.txt

Here is the result - a real cleartext-signed message from my PQC key. You can verify it:

To verify, download my public key and run:

curl -O https://raw.githubusercontent.com/detrin/pqc/main/keys/daniel-herman.pub.pgp
sq verify --signer-file daniel-herman.pub.pgp --cleartext signed-message.txt

Output: Authenticated signature made by B9ABC16E... (Daniel Herman) - 1 authenticated signature.

My key fingerprint: B9ABC16EC9A26EE929EEA07860A15523A3F3362853D38D14ACC24A1B55015DB2

”PGP is dead, just use Signal”

I hear you. For person-to-person messaging, PGP lost. But PGP isn’t just email:

Code signing (git commits, package managers, firmware)
File encryption at rest (backups, archives that outlive you)
Document signing (legal, compliance)

These don’t have Signal alternatives. They need PQC because the documents they protect have 10-30 year lifetimes - well within the “harvest now, decrypt later” threat window.

How ML-KEM actually works

ML-KEM (FIPS 203) is a Key Encapsulation Mechanism. It does not encrypt data directly - it establishes a shared 32-byte secret between two parties, which then serves as the AES-256 key for symmetric encryption.

The security is based on the Module Learning With Errors (M-LWE) problem. The core idea:

Key generation produces a public matrix $\mathbf{A} \in R_q^{k \times k}$ and computes:

$\mathbf{t} = \mathbf{A} \cdot \mathbf{s} + \mathbf{e} \pmod{q}$

where $\mathbf{s}$ is the secret key vector and $\mathbf{e}$ is a small random error vector sampled from a centered binomial distribution. The public key is $(\mathbf{A}, \mathbf{t})$ . The private key is $\mathbf{s}$ .

Encapsulation (sender side) picks a random vector $\mathbf{r}$ and computes:

$\mathbf{u} = \mathbf{A}^\top \cdot \mathbf{r} + \mathbf{e}_1 \pmod{q}$

$v = \mathbf{t}^\top \cdot \mathbf{r} + e_2 + \left\lceil \frac{q}{2} \right\rceil \cdot m \pmod{q}$

where $m$ is the message to encapsulate (a random shared secret), and $\mathbf{e}_1$ , $e_2$ are fresh small noise terms. The ciphertext is $(\mathbf{u}, v)$ .

Decapsulation (recipient side) computes:

$v - \mathbf{s}^\top \cdot \mathbf{u} = \left\lceil \frac{q}{2} \right\rceil \cdot m + \underbrace{(\mathbf{e}^\top \cdot \mathbf{r} + e_2 - \mathbf{s}^\top \cdot \mathbf{e}_1)}_{\text{small noise, roundable}}$

The derivation: since $\mathbf{t} = \mathbf{A} \cdot \mathbf{s} + \mathbf{e}$ , we get $\mathbf{t}^\top \cdot \mathbf{r} = \mathbf{s}^\top \cdot \mathbf{A}^\top \cdot \mathbf{r} + \mathbf{e}^\top \cdot \mathbf{r}$ , and the $\mathbf{s}^\top \cdot \mathbf{A}^\top \cdot \mathbf{r}$ terms cancel, leaving only the message plus small noise.

The noise terms are bounded: $|\mathbf{e}^\top \cdot \mathbf{r} + e_2 - \mathbf{s}^\top \cdot \mathbf{e}_1| < \frac{q}{4}$ , so rounding recovers $m$ exactly. But without knowing $\mathbf{s}$ , an attacker sees only noisy linear equations and cannot separate signal from noise.

LWE visualization - clean lattice vs noisy lattice

The visualization shows the key intuition. Left: in classical crypto (RSA, ECC), values lie on a clean algebraic structure - Shor’s algorithm exploits this periodicity. Right: in ML-KEM, each value (red) is displaced from its lattice position (blue ghost) by random noise e. The legitimate recipient knows s and can cancel the noise. An attacker would need to solve the M-LWE problem - finding s given only A and t = A·s + e - which no known quantum algorithm can do efficiently.

ML-KEM-768 parameters (from FIPS 203):

Polynomial ring: $R_q = \mathbb{Z}_q[X]/(X^{256} + 1)$ , with $q = 3329$
Module rank $k = 3$ (hence “768” = $3 \times 256$ )
Public key: 1,184 bytes
Ciphertext: 1,088 bytes
Shared secret: 32 bytes

Why RSA falls and lattices don’t

RSA relies on factoring: $n = p \times q$ . Shor’s algorithm reduces this to quantum period-finding in the group $(\mathbb{Z}/n\mathbb{Z})^*$ - a clean algebraic structure that the Quantum Fourier Transform exploits in polynomial time $O((\log n)^3)$ .

ML-KEM relies on M-LWE: given $(\mathbf{A}, \mathbf{t} = \mathbf{A} \cdot \mathbf{s} + \mathbf{e})$ , recover $\mathbf{s}$ . There is no group structure, no period, no hidden subgroup. The noise destroys any algebraic regularity. The best known quantum attack is Grover-accelerated lattice sieving, which provides only a quadratic speedup - reducing security from $\sim 2^{192}$ to $\sim 2^{96}$ , which is still computationally infeasible.

The hybrid construction in OpenPGP PQC combines both:

$k_{\text{shared}} = \text{KDF}(k_{\text{X25519}} \| k_{\text{ML-KEM}})$

An attacker must break both X25519 (classical) and ML-KEM (post-quantum) to recover the key.

Should you use this today?

Yes, if you’re encrypting data that needs to stay secret for 10+ years, or signing packages where you want the signatures to remain valid past 2030.

No, if you need GPG compatibility, keyserver distribution, or are waiting for the final RFC.

The honest timeline: working today → RFC ratified 2026-2027 → Proton ships to users 2027-2028 → NIST mandate 2029.

We’re in the “works but nobody uses it” phase.

Repo: github.com/detrin/pqc - Docker images, interop tests, and a Go CLI wrapper.