# Bedrock
Tectonic's common cryptography library
Bedrock provides post-quantum cryptographic primitives including digital signatures and key encapsulation mechanisms (KEMs). The library supports NIST-standardized algorithms (ML-DSA, ML-KEM) as well as other post-quantum schemes (Falcon/FN-DSA, Classic McEliece).
## Features
- **ML-DSA (FIPS 204)**: Module-Lattice-Based Digital Signature Algorithm
- **Falcon/FN-DSA**: Fast Fourier Lattice-based Compact Signatures
- **MAYO**: Multivariate oil-and-vinegar signatures with compact public keys
- **ML-KEM (FIPS 203)**: Module-Lattice-Based Key-Encapsulation Mechanism
- **Classic McEliece**: Code-based Key Encapsulation Mechanism
- **ETHFALCON**: Ethereum-compatible Falcon variant with Keccak-256 XOF
- **X-Wing**: Hybrid KEM combining X25519 with ML-KEM or Classic McEliece
- **HQC (FIPS 207)**: Code-based Key-Encapsulation Mechanism over quasi-cyclic codes
- **Streamlined NTRU Prime**: Lattice-based KEM avoiding ring structure, all six sizes
- **FrodoKEM**: Conservative plain-LWE Key-Encapsulation Mechanism
- **XMSS (RFC 8391 / SP 800-208)**: Stateful hash-based signatures
- **Bird-of-Prey-2**: Hybrid signatures combining Ed25519 with ML-DSA or FN-DSA
## Supported Algorithms
### ML-DSA (Digital Signatures)
Three security levels following NIST standards:
- **ML-DSA-44** (NIST Level 2) - Deprecated; use ML-DSA-65 or higher
- **ML-DSA-65** (NIST Level 3) - Default
- **ML-DSA-87** (NIST Level 5)
### Falcon/FN-DSA (Digital Signatures)
Two security levels plus Ethereum variant:
- **FN-DSA-512** (NIST Level 1) - Default
- **FN-DSA-1024** (NIST Level 5)
- **ETHFALCON** (Ethereum-compatible Falcon-512 with Keccak-256)
### MAYO (Digital Signatures)
Multivariate "oil and vinegar" signatures with compact public keys, via the `mayo` feature. Four NIST parameter sets:
- **MAYO-1** (NIST Level 1) - Default
- **MAYO-2** (NIST Level 1) - Smallest signatures
- **MAYO-3** (NIST Level 3)
- **MAYO-5** (NIST Level 5)
HD wallet (HHD) key derivation is supported for MAYO-1, MAYO-2, and MAYO-3. The 32-byte
SLIP-0010 child key is truncated to the parameter set's keygen seed size (24 bytes for
MAYO-1/2, 32 bytes for MAYO-3). MAYO-5 is not offered in HHD because its 40-byte seed
would require expanding, rather than stripping, the child key.
### ML-KEM (Key Encapsulation)
Two security levels following NIST standards:
- **ML-KEM-768** (NIST Level 3) - Default when `ml-kem` feature enabled
- **ML-KEM-1024** (NIST Level 5)
### Classic McEliece (Key Encapsulation)
- **ClassicMcEliece-348864** (NIST Level 1) - Default when only `mceliece` feature enabled
### X-Wing (Hybrid Key Encapsulation)
Hybrid KEM combining X25519 with post-quantum KEMs:
- **X25519-ML-KEM-768** (X25519 + ML-KEM-768) - Default
- **X25519-ML-KEM-1024** (X25519 + ML-KEM-1024)
- **X25519-ClassicMcEliece348864** (X25519 + Classic McEliece)
### HQC (Key Encapsulation)
Code-based KEM standardized as **FIPS 207**, using quasi-cyclic codes with a concatenated
Reed-Solomon / Reed-Muller construction under a Fujisaki-Okamoto transform. The code-based
counterpart to ML-KEM: larger ciphertexts in exchange for a security assumption that does
not rest on structured lattices. Enabled by the `hqc` feature.
- **HQC-128** (NIST Level 1)
- **HQC-192** (NIST Level 3) - Default when `hqc` is the only KEM enabled
- **HQC-256** (NIST Level 5)
Seed-derived key generation is supported (32-byte seed). Decapsulation is pinned to the
official NIST KAT vectors in `tests/kat_kem.rs`.
### Streamlined NTRU Prime (Key Encapsulation)
Lattice-based KEM designed to avoid the ring structure that ring-LWE schemes rely on, via
the `sntrup` feature. All six parameter sets are offered:
- **sntrup653** (NIST Level 1) - lowest margin in the family
- **sntrup761** (NIST Level 2) - the set OpenSSH deploys in `sntrup761x25519-sha512`
- **sntrup857** (NIST Level 3)
- **sntrup953** (NIST Level 4)
- **sntrup1013** (NIST Level 5)
- **sntrup1277** (NIST Level 5)
Every set generates keys deterministically from a 32-byte seed, so all six support
seed-derived generation.
### FrodoKEM (Key Encapsulation)
Conservative KEM built on plain LWE with no ring or module structure, via the `frodo`
feature. Six parameter sets:
- **FrodoKEM-640-AES** / **FrodoKEM-640-SHAKE** (NIST Level 1)
- **FrodoKEM-976-AES** / **FrodoKEM-976-SHAKE** (NIST Level 3)
- **FrodoKEM-1344-AES** / **FrodoKEM-1344-SHAKE** (NIST Level 5)
The AES and SHAKE variants of a given `n` differ only in how the matrix **A** is derived,
and are byte-identical in every key, ciphertext and shared-secret length. They are
therefore distinguished exclusively by the scheme stored alongside the key material —
never by encoding length.
**FrodoKEM does not support seed-derived key generation.** Its key seed is 64, 88 or 112
bytes depending on parameter set, above the 32-byte ceiling a single SLIP-0010 child key
can supply without expansion. `keypair_from_seed` returns
`Error::DeterministicKeygenUnsupported` for any input, including an empty seed. Use
`KemScheme::supports_seeded_keygen()` to test for this rather than inspecting `seed_size`,
which is zero for these schemes and would otherwise be ambiguous.
### XMSS (Stateful Hash-Based Signatures)
Hash-based signatures per **RFC 8391** and **SP 800-208**, via the `xmss` feature. Twelve
parameter sets: SHA2 and SHAKE256, each at tree heights 10, 16 and 20, each at 256- and
512-bit output.
**XMSS is stateful.** Every signature consumes one one-time-signature leaf, and releasing
two signatures under the same leaf index reveals the secret key. Because bedrock performs
no I/O, state persistence is the caller's responsibility: implement the `XmssStateStore`
trait. The signer commits advanced state through the store *before* releasing a signature,
so a failed commit yields no signature. Exhausting the tree returns
`Error::XmssKeyExhausted` rather than wrapping around.
### Bird-of-Prey-2 (Hybrid Signatures)
Strong-unforgeability-preserving hybrid signatures combining Ed25519 — treated as a
Fiat-Shamir identification scheme with unique responses — with a post-quantum signature,
following eprint 2025/1844 and §4 of `draft-prabel-cfrg-suf-hybrid-sigs`. Enabled by the
`bird-of-prey` feature.
- **Ed25519-ML-DSA-65**
- **Ed25519-FN-DSA-512**
The Ed25519 commitment `R` is recovered at verification rather than transmitted, so the
classical half of the signature is a single 32-byte scalar instead of a full 64-byte EdDSA
signature. The classical component is serialized first in both keys and signatures.
Because the combiner hashes the post-quantum signature into its Fiat-Shamir challenge, that
signature must be a deterministic function of key and message — otherwise a repeated
message would pair a fixed classical nonce with two different challenges and leak the
classical secret key. The FN-DSA branch is therefore driven by an RFC 6979 HMAC-SHA-512
DRBG (`det_rng`); the ML-DSA branch uses bedrock's already-deterministic signer directly.
No cross-implementation test vectors exist for BoP-2 yet, so byte-level interoperability
with other implementations is not claimed.
### Excluded Schemes
The weakest ML-KEM parameter set is intentionally **not** offered. ML-DSA-44 remains
available for compatibility, but is deprecated and should not be used for new deployments:
| **ML-KEM-512** | Level 1 | Removed | Use ML-KEM-768 (the new `KemScheme` default) or higher. |
| **ML-DSA-44** | Level 2 | Deprecated | Available for compatibility; use ML-DSA-65 (the `MlDsaScheme` default) or higher. |
| **X25519-ML-KEM-512** | — | Removed | Hybrid built on ML-KEM-512; use X25519-ML-KEM-768 or higher. |
Removing the KEMs dropped the `KemScheme::MlKem512` and
`XwingScheme::X25519MlKem512` variants. See the [CHANGELOG](./CHANGELOG.md) for the
full breaking-change entry. ML-DSA-44's APIs remain available with deprecation warnings.
The serde discriminants and BIP-85 child indices of the surviving schemes are unchanged,
so existing serialized keys and derivation paths for the stronger schemes remain valid.
**Deprecation path for existing data.** The wire discriminants (`1`) and name strings
(`"ML-KEM-512"`, `"X25519-ML-KEM-512"`) of the removed schemes stay
**reserved**: deserializing or parsing data produced by an older version of the library
returns a specific `Error::DeprecatedScheme { scheme, replacement }` — naming the removed
scheme and its recommended replacement — rather than a generic `InvalidScheme`. This gives
anything that may already have used these schemes a clear, actionable migration error
instead of a silent or confusing failure. The discriminants are never reassigned to other
schemes.
> **Note:** exclusion applies only to the weakest ML-KEM / ML-DSA lattice sets. Level 1
> parameter sets from other families — FN-DSA-512, MAYO-1, MAYO-2, and
> ClassicMcEliece-348864 — remain available, since their security margins and intended
> use cases differ.
## API Reference
### ML-DSA Methods
#### `MlDsaScheme`
**Key Generation:**
- `keypair() -> Result<(MlDsaVerificationKey, MlDsaSigningKey)>`
Generate a new ML-DSA signing and verification key pair (requires `kgen` feature)
**Signing:**
- `sign(message: &[u8], signing_key: &MlDsaSigningKey) -> Result<MlDsaSignature>`
Sign a message with the specified signing key (requires `sign` feature)
**Verification:**
- `verify(message: &[u8], signature: &MlDsaSignature, verification_key: &MlDsaVerificationKey) -> Result<()>`
Verify a signature (requires `vrfy` feature)
#### `MlDsaSigningKey`, `MlDsaVerificationKey`, `MlDsaSignature`
Common methods for all types:
- `scheme() -> MlDsaScheme` - Get the scheme used by this key/signature
- `to_raw_bytes() -> Vec<u8>` - Convert to raw byte representation
- `from_raw_bytes(scheme: MlDsaScheme, bytes: &[u8]) -> Result<Self>` - Create from raw bytes
- `as_ref() -> &[u8]` - Get byte slice reference
### Falcon/FN-DSA Methods
#### `FalconScheme`
**Key Generation:**
- `keypair() -> Result<(FalconVerificationKey, FalconSigningKey)>`
Generate a new Falcon signing and verification key pair (requires `kgen` feature)
- `keypair_from_seed(seed: &[u8]) -> Result<(FalconVerificationKey, FalconSigningKey)>`
Generate a key pair from a seed (32-64 bytes, requires `kgen` feature)
**Signing:**
- `sign(message: &[u8], signing_key: &FalconSigningKey) -> Result<FalconSignature>`
Sign a message with the specified signing key (requires `sign` feature)
**Verification:**
- `verify(message: &[u8], signature: &FalconSignature, verification_key: &FalconVerificationKey) -> Result<()>`
Verify a signature (requires `vrfy` feature)
#### `FalconSigningKey`, `FalconVerificationKey`, `FalconSignature`
Common methods for all types:
- `scheme() -> FalconScheme` - Get the scheme used by this key/signature
- `to_raw_bytes() -> Vec<u8>` - Convert to raw byte representation
- `from_raw_bytes(scheme: FalconScheme, bytes: &[u8]) -> Result<Self>` - Create from raw bytes
- `as_ref() -> &[u8]` - Get byte slice reference
#### `FalconSigningKey` (ETHFALCON-specific)
When `eth_falcon` feature is enabled:
- `into_ethereum(self) -> Result<Self>` - Convert FN-DSA-512 signing key to ETHFALCON scheme
- `into_dsa512(self) -> Result<Self>` - Convert ETHFALCON signing key to FN-DSA-512 scheme
#### ETHFALCON Conversions
When `eth_falcon` feature is enabled:
- `EthFalconVerifyingKey::try_from(FalconVerificationKey) -> Result<EthFalconVerifyingKey>`
Convert Falcon public key to ETHFALCON Solidity format (abi.encodePacked, NTT form, 1024 bytes)
- `EthFalconSignature::try_from(FalconSignature) -> Result<EthFalconSignature>`
Convert Falcon signature to ETHFALCON Solidity format (abi.encodePacked, 1024 bytes)
### KEM Methods
#### `KemScheme`
**Key Generation:**
- `keypair() -> Result<(KemEncapsulationKey, KemDecapsulationKey)>`
Generate a new encapsulation/decapsulation key pair (requires `kgen` feature)
- `keypair_from_seed(seed: &[u8]) -> Result<(KemEncapsulationKey, KemDecapsulationKey)>`
Generate a key pair from a seed (requires `kgen` feature)
**Encapsulation:**
- `encapsulate(encapsulation_key: &KemEncapsulationKey) -> Result<(KemCiphertext, KemSharedSecret)>`
Encapsulate to the provided public key (requires `encp` feature)
**Decapsulation:**
- `decapsulate(ciphertext: &KemCiphertext, decapsulation_key: &KemDecapsulationKey) -> Result<KemSharedSecret>`
Decapsulate the provided ciphertext (requires `decp` feature)
#### `KemEncapsulationKey`, `KemDecapsulationKey`, `KemCiphertext`, `KemSharedSecret`
Common methods for all types:
- `scheme() -> KemScheme` - Get the scheme used by this key/ciphertext/secret
- `to_raw_bytes() -> Vec<u8>` - Convert to raw byte representation
- `from_raw_bytes(scheme: KemScheme, bytes: &[u8]) -> Result<Self>` - Create from raw bytes
- `as_ref() -> &[u8]` - Get byte slice reference
### X-Wing Methods
#### `XwingScheme`
**Key Generation:**
- `keypair() -> Result<(EncapsulationKey, DecapsulationKey)>`
Generate a new X-Wing encapsulation/decapsulation key pair (requires `xwing` feature)
- `keypair_from_seed(seed: &[u8]) -> Result<(EncapsulationKey, DecapsulationKey)>`
Generate a key pair from a seed (requires `xwing` feature)
#### `EncapsulationKey`
- `encapsulate() -> Result<(Ciphertext, SharedSecret)>`
Create a ciphertext and shared secret for the encapsulation key holder
- `to_raw_bytes() -> Vec<u8>` - Convert to raw byte representation
- `from_raw_bytes(scheme: XwingScheme, bytes: &[u8]) -> Result<Self>` - Create from raw bytes
#### `DecapsulationKey`
- `decapsulate(ciphertext: &Ciphertext) -> Result<SharedSecret>`
Decapsulate to recover the shared secret
- `to_seed() -> Vec<u8>` - Get the seed bytes
- `from_seed(scheme: XwingScheme, bytes: &[u8]) -> Self` - Create from seed bytes
- `expand() -> Result<ExpandedDecapsulationKey>` - Expand the seed into full key material
#### `ExpandedDecapsulationKey`
- `decapsulate(ciphertext: &Ciphertext) -> Result<SharedSecret>` - Decapsulate using expanded key
- `encapsulation_key() -> EncapsulationKey` - Get the associated encapsulation key
#### `Ciphertext`
- `to_raw_bytes() -> Vec<u8>` - Convert to raw byte representation
- `from_raw_bytes(scheme: XwingScheme, bytes: &[u8]) -> Result<Self>` - Create from raw bytes
### Serialization
All key types, signatures, ciphertexts, and shared secrets implement `serde::Serialize` and `serde::Deserialize`:
- **Human-readable formats** (JSON, etc.): Serialized as hex strings and human-readable
- **Binary formats** (postcard, bincode, etc.): Serialized as compact byte arrays
Schemes implement the [`Display`] and [`FromStr`] traits for string parsing:
- `to_string()` - Convert scheme to string representation (e.g., "ML-DSA-65")
- `from_str(s: &str) -> Result<Self>` or `parse()` - Parse scheme from string
- Conversion to/from `u8` for compact storage
## Examples
### ML-DSA Digital Signatures
```rust
use bedrock::ml_dsa::MlDsaScheme;
// Generate a keypair
let scheme = MlDsaScheme::Dsa65;
let (verification_key, signing_key) = scheme.keypair()?;
// Sign a message
let message = b"Hello, world!";
let signature = scheme.sign(message, &signing_key)?;
// Verify the signature
scheme.verify(message, &signature, &verification_key)?;
// Serialize keys
let vk_json = serde_json::to_string(&verification_key)?;
let vk_binary = postcard::to_stdvec(&verification_key)?;
```
### Falcon/FN-DSA Digital Signatures
```rust
use bedrock::falcon::FalconScheme;
// Generate a keypair with deterministic seed
let scheme = FalconScheme::Dsa512;
let seed = [1u8; 48];
let (verification_key, signing_key) = scheme.keypair_from_seed(&seed)?;
// Sign and verify
let message = b"Sign this message";
let signature = scheme.sign(message, &signing_key)?;
scheme.verify(message, &signature, &verification_key)?;
```
### ETHFALCON (Ethereum-compatible)
```rust
use bedrock::falcon::{FalconScheme, EthFalconVerifyingKey, EthFalconSignature};
// Generate ETHFALCON keypair
let scheme = FalconScheme::Ethereum;
let (verification_key, signing_key) = scheme.keypair()?;
// Sign with ETHFALCON
let message = b"Transaction data";
let signature = scheme.sign(message, &signing_key)?;
// Convert to Solidity-compatible formats
let eth_vk: EthFalconVerifyingKey = verification_key.try_into()?;
let eth_sig: EthFalconSignature = signature.try_into()?;
// Verify
scheme.verify(message, &signature, &verification_key)?;
// Convert between schemes
let signing_key_512 = signing_key.into_dsa512()?;
```
### ML-KEM Key Encapsulation
```rust
use bedrock::kem::KemScheme;
// Generate a keypair
let scheme = KemScheme::MlKem768;
let (encapsulation_key, decapsulation_key) = scheme.keypair()?;
// Encapsulate to create shared secret
let (ciphertext, shared_secret_sender) = scheme.encapsulate(&encapsulation_key)?;
// Decapsulate to recover shared secret
let shared_secret_receiver = scheme.decapsulate(&ciphertext, &decapsulation_key)?;
assert_eq!(shared_secret_sender.as_ref(), shared_secret_receiver.as_ref());
```
### Classic McEliece
```rust
use bedrock::kem::KemScheme;
// Use Classic McEliece for code-based KEM
let scheme = KemScheme::ClassicMcEliece348864;
let (ek, dk) = scheme.keypair()?;
let (ct, ss) = scheme.encapsulate(&ek)?;
let ss2 = scheme.decapsulate(&ct, &dk)?;
assert_eq!(ss.as_ref(), ss2.as_ref());
```
### X-Wing Hybrid KEM
```rust
use bedrock::xwing::XwingScheme;
// Generate X-Wing keypair (combines X25519 with ML-KEM-768)
let scheme = XwingScheme::X25519MlKem768;
let (encapsulation_key, decapsulation_key) = scheme.keypair()?;
// Encapsulate to create shared secret
let (ciphertext, shared_secret_sender) = encapsulation_key.encapsulate()?;
// Decapsulate to recover shared secret
let shared_secret_receiver = decapsulation_key.decapsulate(&ciphertext)?;
assert_eq!(shared_secret_sender, shared_secret_receiver);
```
## Feature Flags
Control which algorithms and operations are enabled:
### Algorithm Features
- `ml-dsa` - Enable ML-DSA signature schemes (default)
- `falcon` - Enable Falcon/FN-DSA signature schemes (default)
- `eth_falcon` - Enable ETHFALCON Ethereum-compatible variant (default, requires `falcon`)
- `ml-kem` - Enable ML-KEM key encapsulation (default)
- `mceliece` - Enable Classic McEliece key encapsulation (default)
- `xwing` - Enable X-Wing hybrid KEM (default, requires `ml-kem` or `mceliece`)
### Operation Features
- `kgen` - Enable key generation (default)
- `sign` - Enable signing operations (default)
- `vrfy` - Enable verification operations (default)
- `encp` - Enable encapsulation operations (default)
- `decp` - Enable decapsulation operations (default)
### Features
Bedrock is designed to allow selective features to minimize the dependency list.
The default is
```toml
default = ["eth_falcon", "falcon", "mceliece", "ml-dsa", "ml-kem", "decp", "encp", "kgen", "sign", "vrfy", "hhd", "xwing"]
```
### Minimal Configuration Examples
Verification only (no key generation or signing):
```toml
tectonic-bedrock = { version = "0.1", default-features = false, features = ["ml-dsa", "vrfy"] }
```
ML-KEM only:
```toml
tectonic-bedrock = { version = "0.1", default-features = false, features = ["ml-kem", "kgen", "encp", "decp"] }
```
X-Wing hybrid KEM only:
```toml
tectonic-bedrock = { version = "0.1", default-features = false, features = ["ml-kem", "xwing", "kgen", "encp", "decp"] }
```
## Error Handling
All fallible operations return `Result<T, bedrock::error::Error>`. The `Error` enum includes:
- `McElieceError(String)` - Errors from the Classic McEliece KEM
- `InvalidScheme(u8)` / `InvalidSchemeStr(String)` - Invalid scheme identifiers
- `InvalidSeedLength(usize)` - Seed length out of valid range (32-64 bytes)
- `InvalidLength(usize)` - Invalid data length
- `FnDsaError(String)` - ETHFALCON-specific errors
## Security Considerations
- All algorithms are quantum-resistant
- ML-DSA and ML-KEM are NIST-standardized (FIPS 204, FIPS 203)
- Falcon provides smaller signatures than ML-DSA with similar security
- ETHFALCON enables post-quantum signatures in Ethereum smart contracts
- Classic McEliece offers conservative code-based security
- Use deterministic key generation (`keypair_from_seed`) only when necessary
- Protect private keys and seeds with appropriate key management practices
## License
Licensed under either of
* Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
* MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)
### Contribution
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.
## References
- [ML-DSA (FIPS 204)](https://csrc.nist.gov/pubs/fips/204/final)
- [ML-KEM (FIPS 203)](https://csrc.nist.gov/pubs/fips/203/final)
- [ETHFALCON Specification](https://github.com/zknoxhq/ETHFALCON)
- [X-Wing (IETF Draft)](https://datatracker.ietf.org/doc/draft-connolly-cfrg-xwing-kem/)
- [classic-mceliece-rust](https://github.com/Colfenor/classic-mceliece-rust)