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:

Removing the KEMs dropped the KemScheme::MlKem512 and XwingScheme::X25519MlKem512 variants. See the CHANGELOG 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

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

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)

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

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

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

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

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):

tectonic-bedrock = { version = "0.1", default-features = false, features = ["ml-dsa", "vrfy"] }

ML-KEM only:

tectonic-bedrock = { version = "0.1", default-features = false, features = ["ml-kem", "kgen", "encp", "decp"] }

X-Wing hybrid KEM only:

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 or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (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)
• ML-KEM (FIPS 203)
• ETHFALCON Specification
• X-Wing (IETF Draft)
• classic-mceliece-rust