Version: 1.0
Date: December, 2025
Authors: Rolando Santamaria Maso kyberneees@gmail.com
This white paper presents an experimental cryptographic construction that has NOT been:
- Formally verified by academic peer review
- Analyzed by the broader cryptographic research community
- Submitted to any standards organization (NIST, IETF, ISO)
- Tested against real-world adversarial conditions
DO NOT use this algorithm in production systems protecting sensitive data until it has undergone rigorous cryptanalysis. For production applications, use established, standardized post-quantum algorithms such as ML-KEM (Kyber) and ML-DSA (Dilithium).
This document describes a novel theoretical approach that we believe warrants further academic investigation.
- Primer for Non-Experts
- Executive Summary
- The Problem: Single Points of Failure in Cryptography
- The kMOSAIC Innovation: Cryptographic Entanglement
- The Three Hard Problems
- How It Works: A Visual Guide
- Key Encapsulation Mechanism (KEM)
- Digital Signatures
- Security Analysis
- Performance Characteristics
- Code Examples
- Comparison with Existing Schemes
- Future Work and Research Directions
- Conclusion
- References
Before diving into the technical details, we introduce key concepts used in this paper.
Modern encryption (like RSA) relies on math problems that are hard for traditional computers but easy for large quantum computers. Post-Quantum Cryptography involves designing new encryption methods that are hard for both classical and quantum computers to break.
In cryptography, a "hard problem" is a mathematical puzzle that is easy to create but extremely difficult to solve without a specific "key." For example, multiplying two large prime numbers is easy, but finding those original numbers given only the result (factoring) is very hard.
Instead of relying on a single lock to protect a secret, Defense-in-Depth uses multiple, different types of locks. If a thief picks one lock, the door remains shut. In kMOSAIC, we use three different mathematical "locks" simultaneously.
This is a technique where we bind multiple mathematical problems together so they cannot be separated. An attacker cannot attack the problems one by one; they must solve all of them at the same time to recover the secret.
kMOSAIC (Multi-Oracle Structured Algebraic Intractability Composition) is a novel post-quantum cryptographic construction that achieves defense-in-depth security by cryptographically entangling three independent mathematical hard problems from different domains.
Unlike traditional cryptographic schemes that rely on a single mathematical assumption, kMOSAIC fragments secrets across three fundamentally different computational problems:
| Component | Mathematical Domain | Problem Type |
|---|---|---|
| SLSS | Lattice Cryptography | Sparse Lattice Subset Sum |
| TDD | Multilinear Algebra | Tensor Decomposition Distinguishing |
| EGRW | Graph Theory | Expander Graph Random Walk |
To break kMOSAIC, an attacker must simultaneously solve all three problems. Breaking any one (or even two) reveals zero information about the secret due to the information-theoretic properties of the secret sharing scheme.
Security = SLSS × TDD × EGRW
(not SLSS + TDD + EGRW)
- Quantum Resistance Diversity: Different quantum algorithms would be needed for each component
- Graceful Degradation: If one problem is broken, the others still protect the secret
- Future-Proof Design: Hedges against unexpected cryptanalytic breakthroughs
- Defense-in-Depth: Multiple independent layers of security
All widely-deployed post-quantum cryptographic schemes rely on a single hardness assumption:
| Scheme | Single Point of Failure |
|---|---|
| ML-KEM (Kyber) | Module-LWE is hard |
| ML-DSA (Dilithium) | Module-SIS is hard |
| McEliece | Syndrome decoding is hard |
| SPHINCS+ | Hash functions are one-way |
History has shown that "impossible" problems can suddenly become tractable:
- RSA was considered secure → Shor's algorithm (1994) breaks it on quantum computers
- SIKE/SIDH was a NIST PQC finalist → Broken in 2022 using classical computers (e.g., SIKEp434 key recovery in ~1 hour on a single-core computer).
- MD5 was the standard hash → Collision attacks made it obsolete
When a single assumption fails, the entire cryptographic scheme collapses instantly.
The current post-quantum standardization landscape is heavily skewed towards a single mathematical family: lattices (especially for KEMs).
- FIPS 203 (ML-KEM/Kyber): Module-Lattice based
- FIPS 204 (ML-DSA/Dilithium): Module-Lattice based
- FIPS 205 (SLH-DSA / SPHINCS+): Hash-based digital signatures
- Falcon: Selected by NIST for standardization (FIPS publication forthcoming) (Selected Algorithms)
This creates a systemic risk concentration: a major breakthrough affecting lattice-based assumptions could have outsized impact on widely deployed lattice-based schemes.
Current hybrid approaches simply concatenate two schemes:
Ciphertext = Encrypt_Kyber(message) || Encrypt_ClassicDH(message)
Problem: This reveals the same message through different channels. If either is broken, the message is exposed.
The ideal solution would be a Robust Combiner that:
- Split the secret so that each fragment reveals nothing
- Require all components to reconstruct the secret
- Use mathematically unrelated problems
- Make the components inseparable (cryptographically bound)
This is exactly what kMOSAIC provides.
kMOSAIC introduces cryptographic entanglement—a construction where three hard problems become inseparable, and the secret is distributed across all three in a way that:
- Any single problem reveals zero bits of information
- Any two problems reveal zero bits of information
- Only solving all three recovers the secret
┌─────────────────────────────────────────────────────────────────┐
│ TRADITIONAL HYBRID │
├─────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────┐ ┌─────────┐ │
│ │ Kyber │ │ Classic │ │
│ │ Encrypt │ │ Encrypt │ │
│ └────┬────┘ └────┬────┘ │
│ │ │ │
│ ▼ ▼ │
│ [C1: message] [C2: message] ← Same message! │
│ │ │ │
│ └────────┬─────────┘ │
│ │ │
│ [C1 || C2] │
│ │
│ ⚠️ Break ONE = Get message │
└─────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────┐
│ kMOSAIC ENTANGLEMENT │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Secret: K │
│ │ │
│ ┌──────────┼──────────┐ │
│ ▼ ▼ ▼ │
│ K = [Fragment₁] ⊕ [Fragment₂] ⊕ [Fragment₃] │
│ │ │ │ │
│ ▼ ▼ ▼ │
│ ┌────────────┐ ┌────────────┐ ┌────────────┐ │
│ │ SLSS │ │ TDD │ │ EGRW │ │
│ │ (Lattice) │ │ (Tensor) │ │ (Graph) │ │
│ └─────┬──────┘ └─────┬──────┘ └─────┬──────┘ │
│ │ │ │ │
│ └──────────────┼──────────────┘ │
│ │ │
│ ╔══════════╧══════════╗ │
│ ║ BINDING COMMITMENT ║ ← Cryptographically │
│ ║ H(SLSS||TDD||EGRW)║ binds all three │
│ ╚═════════════════════╝ │
│ │
│ ✓ Break ONE = Zero information │
│ ✓ Break TWO = Zero information │
│ ✓ Break ALL THREE = Recover secret │
└─────────────────────────────────────────────────────────────────┘
kMOSAIC uses XOR-based 3-of-3 secret sharing:
Secret K = 256 random bits
Fragment₁ = random 256 bits
Fragment₂ = random 256 bits
Fragment₃ = K ⊕ Fragment₁ ⊕ Fragment₂
Mathematical Property: Any two fragments are statistically independent of K. This is information-theoretic security—not computational. Even with infinite computing power, two fragments reveal nothing.
To prevent an attacker from substituting components, kMOSAIC binds all three using a hash commitment:
Binding = SHA3-256(SLSS_PublicKey || TDD_PublicKey || EGRW_PublicKey)
This binding value is incorporated into the parameters of all three problems, creating a circular dependency that makes them inseparable.
┌─────────────────────────────────────────────────────────────────────────────┐
│ KEM KEY GENERATION │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ INPUT: Security Level (MOS-128 or MOS-256) │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 1: Generate Master Seed │ │
│ │ ───────────────────────────── │ │
│ │ seed ← 32 bytes from cryptographic RNG │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 2: Derive Component Seeds (Domain Separation) │ │
│ │ ────────────────────────────────────────────────── │ │
│ │ slss_seed ← SHAKE256("kmosaic-kem-slss-v1" || seed) │ │
│ │ tdd_seed ← SHAKE256("kmosaic-kem-tdd-v1" || seed) │ │
│ │ egrw_seed ← SHAKE256("kmosaic-kem-egrw-v1" || seed) │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ┌────────────────────┼────────────────────┐ │
│ ▼ ▼ ▼ │
│ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │
│ │ SLSS KeyGen │ │ TDD KeyGen │ │ EGRW KeyGen │ │
│ │ ─────────── │ │ ─────────── │ │ ─────────── │ │
│ │ Generate: │ │ Generate: │ │ Generate: │ │
│ │ • Matrix A │ │ • Tensor T │ │ • Graph │ │
│ │ • Vector s │ │ • Factors │ │ • Walk path │ │
│ │ • Target t │ │ a,b,c │ │ • Start/End │ │
│ └──────┬──────┘ └──────┬──────┘ └──────┬──────┘ │
│ │ │ │ │
│ └────────────────────┼────────────────────┘ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 3: Compute Binding Commitment │ │
│ │ ────────────────────────────────── │ │
│ │ binding ← SHA3-256(slss_pk || tdd_pk || egrw_pk) │ │
│ │ │ │
│ │ Purpose: Cryptographically binds all three components together │ │
│ │ so they cannot be separated or substituted │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ┌────────────────────┴────────────────────┐ │
│ ▼ ▼ │
│ ┌─────────────────────┐ ┌─────────────────────┐ │
│ │ PUBLIC KEY │ │ SECRET KEY │ │
│ │ ─────────────────── │ │ ─────────────────── │ │
│ │ • SLSS public key │ │ • SLSS secret (s) │ │
│ │ • TDD tensor (T) │ │ • TDD factors │ │
│ │ • EGRW endpoints │ │ • EGRW walk path │ │
│ │ • Binding hash │ │ • Master seed │ │
│ │ • Parameters │ │ • Public key hash │ │
│ └─────────────────────┘ └─────────────────────┘ │
│ │
│ OUTPUT: (publicKey, secretKey) │
│ SIZES: publicKey ~824KB (MOS-128), secretKey ~9KB │
└─────────────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────────────┐
│ KEM ENCAPSULATION │
│ (Bob creates shared secret for Alice) │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ INPUT: Alice's publicKey │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 1: Generate Ephemeral Secret │ │
│ │ ───────────────────────────────── │ │
│ │ m ← 32 bytes from cryptographic RNG │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 2: Derive Randomness │ │
│ │ ───────────────────────── │ │
│ │ randomness ← SHAKE256(m || binding) │ │
│ │ │ │
│ │ Purpose: Ties randomness to this specific public key │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 3: Secret Sharing (XOR-based 3-of-3) │ │
│ │ ───────────────────────────────────────── │ │
│ │ share1 ← SHAKE256("share-0" || randomness, 32) [random] │ │
│ │ share2 ← SHAKE256("share-1" || randomness, 32) [random] │ │
│ │ share3 ← m ⊕ share1 ⊕ share2 [computed] │ │
│ │ │ │
│ │ Property: Any 1 or 2 shares reveal ZERO information about m │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ┌────────────────────┼────────────────────┐ │
│ ▼ ▼ ▼ │
│ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │
│ │SLSS Encrypt │ │ TDD Encrypt │ │EGRW Encrypt │ │
│ │ ─────────── │ │ ─────────── │ │ ─────────── │ │
│ │ Input: │ │ Input: │ │ Input: │ │
│ │ • share1 │ │ • share2 │ │ • share3 │ │
│ │ • SLSS pk │ │ • TDD pk │ │ • EGRW pk │ │
│ │ │ │ │ │ │ │
│ │ Output: c1 │ │ Output: c2 │ │ Output: c3 │ │
│ └──────┬──────┘ └──────┬──────┘ └──────┬──────┘ │
│ │ │ │ │
│ └────────────────────┼────────────────────┘ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 4: Generate NIZK Proof │ │
│ │ ─────────────────────────── │ │
│ │ proof ← NIZKProve(m, [share1, share2, share3], [H(c1), H(c2), H(c3)])│ │
│ │ │ │
│ │ Purpose: Proves ciphertext was constructed correctly │ │
│ │ without revealing the secret m │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 5: Derive Shared Secret │ │
│ │ ──────────────────────────── │ │
│ │ ciphertext_hash ← SHA3-256(c1 || c2 || c3 || proof) │ │
│ │ sharedSecret ← SHAKE256("kmosaic-kem-ss-v1" || m || ciphertext_hash)│ │
│ │ │ │
│ │ Purpose: Binds shared secret to the specific ciphertext │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ┌────────────────────┴────────────────────┐ │
│ ▼ ▼ │
│ ┌─────────────────────┐ ┌─────────────────────┐ │
│ │ CIPHERTEXT │ │ SHARED SECRET │ │
│ │ ─────────────────── │ │ ─────────────────── │ │
│ │ • c1 (SLSS) │ │ 32 bytes │ │
│ │ • c2 (TDD) │ │ │ │
│ │ • c3 (EGRW) │ │ Used for symmetric │ │
│ │ • NIZK proof │ │ encryption (AES) │ │
│ └─────────────────────┘ └─────────────────────┘ │
│ │
│ OUTPUT: (ciphertext, sharedSecret) │
│ Bob sends ciphertext to Alice, keeps sharedSecret │
└─────────────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────────────┐
│ KEM DECAPSULATION │
│ (Alice recovers shared secret) │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ INPUT: ciphertext, secretKey, publicKey │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 1: Compute Implicit Rejection Value (Defense) │ │
│ │ ────────────────────────────────────────────────── │ │
│ │ reject_secret ← SHAKE256("reject" || seed || ciphertext) │ │
│ │ │ │
│ │ Purpose: If decryption fails, return this instead of error │ │
│ │ Prevents timing attacks and chosen-ciphertext attacks │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 2: Decrypt All Three Fragments │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ┌────────────────────┼────────────────────┐ │
│ ▼ ▼ ▼ │
│ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │
│ │SLSS Decrypt │ │ TDD Decrypt │ │EGRW Decrypt │ │
│ │ ─────────── │ │ ─────────── │ │ ─────────── │ │
│ │ Input: │ │ Input: │ │ Input: │ │
│ │ • c1 │ │ • c2 │ │ • c3 │ │
│ │ • SLSS sk │ │ • TDD sk │ │ • EGRW sk │ │
│ │ │ │ │ │ │ │
│ │ Output: │ │ Output: │ │ Output: │ │
│ │ share1' │ │ share2' │ │ share3' │ │
│ └──────┬──────┘ └──────┬──────┘ └──────┬──────┘ │
│ │ │ │ │
│ └────────────────────┼────────────────────┘ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 3: Reconstruct Ephemeral Secret │ │
│ │ ──────────────────────────────────── │ │
│ │ m' ← share1' ⊕ share2' ⊕ share3' │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 4: Fujisaki-Okamoto Re-encryption Check │ │
│ │ ──────────────────────────────────────────── │ │
│ │ (ciphertext', _) ← Encapsulate(publicKey, m') │ │
│ │ │ │
│ │ Check: Does ciphertext' match the original ciphertext? │ │
│ │ │ │
│ │ Purpose: Detects tampering or malformed ciphertext │ │
│ │ Required for IND-CCA2 security │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 5: Verify NIZK Proof │ │
│ │ ───────────────────────── │ │
│ │ valid ← NIZKVerify(proof, [H(c1), H(c2), H(c3)], m') │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 6: Constant-Time Selection │ │
│ │ ─────────────────────────────── │ │
│ │ IF (ciphertext' == ciphertext) AND (NIZK valid): │ │
│ │ sharedSecret ← SHAKE256("ss" || m' || H(ciphertext)) │ │
│ │ ELSE: │ │
│ │ sharedSecret ← reject_secret (implicit rejection) │ │
│ │ │ │
│ │ Note: Selection is constant-time to prevent timing attacks │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────┐ │
│ │ SHARED SECRET │ │
│ │ ─────────────────── │ │
│ │ 32 bytes │ │
│ │ │ │
│ │ Matches Bob's if │ │
│ │ ciphertext valid │ │
│ └─────────────────────┘ │
│ │
│ OUTPUT: sharedSecret │
│ Alice and Bob now share the same 32-byte secret │
└─────────────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────────────┐
│ SIGNATURE GENERATION │
│ (Multi-Witness Fiat-Shamir Protocol) │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ INPUT: message, secretKey, publicKey │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 1: Compute Message Hash │ │
│ │ ──────────────────────────── │ │
│ │ μ ← SHA3-256(public_key_hash || message) │ │
│ │ │ │
│ │ Purpose: Binds signature to both message and public key │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ╔═════════════════════════════════════════════════════════════════════╗ │
│ ║ REJECTION SAMPLING LOOP (repeat until valid signature found) ║ │
│ ╠═════════════════════════════════════════════════════════════════════╣ │
│ ║ ║ │
│ ║ ┌───────────────────────────────────────────────────────────────┐ ║ │
│ ║ │ PHASE 1: Generate Masks (Commitments) │ ║ │
│ ║ │ ───────────────────────────────────── │ ║ │
│ ║ │ y1 ← random vector in [-γ₁, γ₁]ⁿ (SLSS mask) │ ║ │
│ ║ │ y2 ← random vector in [-γ₂, γ₂]ʳ (TDD mask) │ ║ │
│ ║ │ y3 ← random walk of length k (EGRW mask) │ ║ │
│ ║ │ │ ║ │
│ ║ │ w1 ← A · y1 mod q (SLSS commitment) │ ║ │
│ ║ │ w2 ← Hash(y2 || T) (TDD commitment) │ ║ │
│ ║ │ w3 ← Serialize(vStart) (EGRW commitment) │ ║ │
│ ║ └───────────────────────────────────────────────────────────────┘ ║ │
│ ║ │ ║ │
│ ║ ▼ ║ │
│ ║ ┌───────────────────────────────────────────────────────────────┐ ║ │
│ ║ │ PHASE 2: Compute Unified Challenge │ ║ │
│ ║ │ ───────────────────────────────── │ ║ │
│ ║ │ c ← SHA3-256(w1 || w2 || w3 || μ) │ ║ │
│ ║ │ │ ║ │
│ ║ │ Key: All three witnesses bound to SAME challenge │ ║ │
│ ║ │ Attacker must solve ALL THREE to forge │ ║ │
│ ║ └───────────────────────────────────────────────────────────────┘ ║ │
│ ║ │ ║ │
│ ║ ▼ ║ │
│ ║ ┌───────────────────────────────────────────────────────────────┐ ║ │
│ ║ │ PHASE 3: Compute Responses │ ║ │
│ ║ │ ───────────────────────── │ ║ │
│ ║ │ z1 ← y1 + c · s1 mod q (SLSS response) │ ║ │
│ ║ │ z2 ← y2 + c · factors (TDD response) │ ║ │
│ ║ │ z3 ← Combine(y3, walk, c) (EGRW response) │ ║ │
│ ║ └───────────────────────────────────────────────────────────────┘ ║ │
│ ║ │ ║ │
│ ║ ▼ ║ │
│ ║ ┌───────────────────────────────────────────────────────────────┐ ║ │
│ ║ │ PHASE 4: Check Rejection Bounds │ ║ │
│ ║ │ ─────────────────────────────── │ ║ │
│ ║ │ IF ||z1|| > γ₁ - β → REJECT, try again │ ║ │
│ ║ │ IF ||z2|| > γ₂ - β → REJECT, try again │ ║ │
│ ║ │ │ ║ │
│ ║ │ Purpose: Ensures signature distribution is independent │ ║ │
│ ║ │ of secret key (prevents key leakage) │ ║ │
│ ║ └───────────────────────────────────────────────────────────────┘ ║ │
│ ║ │ ║ │
│ ║ (bounds OK) ▼ ║ │
│ ╚═════════════════════════════════════════════════════════════════════╝ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 2: Assemble Signature │ │
│ │ ────────────────────────── │ │
│ │ signature = { │ │
│ │ challenge: c (32 bytes) │ │
│ │ z1: {z, w1} (SLSS response + commitment) │ │
│ │ z2: {z, w2} (TDD response + commitment) │ │
│ │ z3: {walk, hints} (EGRW response) │ │
│ │ } │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────┐ │
│ │ SIGNATURE │ │
│ │ ─────────────────── │ │
│ │ ~6 KB (MOS-128) │ │
│ │ ~12 KB (MOS-256) │ │
│ └─────────────────────┘ │
│ │
│ OUTPUT: signature │
│ Signing time: ~25ms (MOS-128), includes rejection sampling │
└─────────────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────────────┐
│ SIGNATURE VERIFICATION │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ INPUT: message, signature, publicKey │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 1: Check Response Bounds │ │
│ │ ───────────────────────────── │ │
│ │ IF ||z1|| > γ₁ - β → RETURN false │ │
│ │ IF ||z2|| > γ₂ - β → RETURN false │ │
│ │ │ │
│ │ Purpose: Valid signatures must have small responses │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 2: Recompute Message Hash │ │
│ │ ────────────────────────────── │ │
│ │ pk_hash ← SHA3-256(slss_pk || tdd_pk || egrw_pk) │ │
│ │ μ ← SHA3-256(pk_hash || message) │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 3: Extract Challenge from Signature │ │
│ │ ───────────────────────────────────── │ │
│ │ c ← signature.challenge │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 4: Retrieve Commitments │ │
│ │ ──────────────────────────── │ │
│ │ │ │
│ │ w1 ← signature.z1.commitment (SLSS commitment from signature) │ │
│ │ w2 ← signature.z2.commitment (TDD commitment from signature) │ │
│ │ w3 ← Serialize(egrw_pk.vStart)(EGRW commitment from public key) │ │
│ │ │ │
│ │ Note: Commitments are stored in signature because they cannot │ │
│ │ be recomputed from responses (due to LWE error terms) │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 5: Recompute and Compare Challenge │ │
│ │ ─────────────────────────────────────── │ │
│ │ expected_c ← SHA3-256(w1 || w2 || w3 || μ) │ │
│ │ │ │
│ │ IF c == expected_c (constant-time comparison): │ │
│ │ RETURN true ✓ Signature is valid │ │
│ │ ELSE: │ │
│ │ RETURN false ✗ Signature is invalid │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────┐ │
│ │ VERIFICATION │ │
│ │ RESULT │ │
│ │ ─────────────────── │ │
│ │ true = Valid │ │
│ │ false = Invalid │ │
│ └─────────────────────┘ │
│ │
│ OUTPUT: boolean (true if signature is valid) │
│ Verification time: ~3-4ms (MOS-128) │
└─────────────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────────────┐
│ HYBRID ENCRYPTION │
│ (KEM-DEM: Key Encapsulation + Symmetric Encryption) │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ INPUT: plaintext (arbitrary length), recipient's publicKey │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 1: Key Encapsulation │ │
│ │ ───────────────────────── │ │
│ │ (ciphertext_kem, sharedSecret) ← Encapsulate(publicKey) │ │
│ │ │ │
│ │ sharedSecret is 32 bytes of shared entropy │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 2: Derive Symmetric Keys │ │
│ │ ───────────────────────────── │ │
│ │ enc_key ← SHAKE256("kmosaic-enc-key-v1" || sharedSecret, 32) │ │
│ │ nonce ← SHAKE256("kmosaic-nonce-v1" || sharedSecret, 12) │ │
│ │ │ │
│ │ enc_key = 256-bit AES key │ │
│ │ nonce = 96-bit unique value for AES-GCM │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 3: Symmetric Encryption (AES-256-GCM) │ │
│ │ ────────────────────────────────────────── │ │
│ │ ciphertext_aes ← AES-256-GCM.Encrypt(enc_key, nonce, plaintext) │ │
│ │ │ │
│ │ Provides: Confidentiality + Integrity (authenticated encryption) │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STEP 4: Combine Ciphertexts │ │
│ │ ─────────────────────────── │ │
│ │ output ← [kem_length (4 bytes)] || ciphertext_kem || ciphertext_aes│ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────┐ │
│ │ ENCRYPTED OUTPUT │ │
│ │ ─────────────────── │ │
│ │ KEM ciphertext + │ │
│ │ AES ciphertext + │ │
│ │ Auth tag (16 bytes) │ │
│ └─────────────────────┘ │
│ │
│ ═══════════════════════════════════════════════════════════════════════ │
│ │
│ DECRYPTION FLOW │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ 1. Parse: Extract ciphertext_kem and ciphertext_aes │ │
│ │ 2. KEM Decapsulate: sharedSecret ← Decapsulate(ciphertext_kem, sk)│ │
│ │ 3. Derive keys: enc_key, nonce ← SHAKE256(sharedSecret, ...) │ │
│ │ 4. Decrypt: plaintext ← AES-256-GCM.Decrypt(enc_key, nonce, ct) │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ OUTPUT: Encrypted message (can be decrypted only by secret key holder) │
└─────────────────────────────────────────────────────────────────────────────┘
kMOSAIC strategically combines three problems from different mathematical domains:
Domain: Lattice-based cryptography with sparsity constraints
The Problem:
Given:
- Matrix A ∈ ℤq^{m×n} (public)
- Target vector t ∈ ℤq^m (public)
Find:
- Sparse vector s ∈ {-1, 0, 1}^n
- With exactly w non-zero entries
- Such that: A·s ≡ t (mod q)
Why It's Hard:
- Combines the NP-hardness of subset sum with lattice structure
- Quantum algorithms for lattices don't exploit sparsity
- Algorithms for subset sum don't exploit lattice structure
- Related to Learning With Errors (LWE) with sparse secrets
Visual Intuition:
A (public matrix) s (secret) t (target)
┌─────────────────────┐ ┌─────┐ ┌─────┐
│ 3 7 2 9 1 5 │ │ 0 │ │ │
│ 8 4 6 2 7 3 │ × │ 1 │ = │ ? │
│ 1 9 5 8 4 6 │ │ 0 │ │ │
│ 5 2 8 1 6 9 │ │ -1 │ │ │
└─────────────────────┘ │ 0 │ └─────┘
│ 1 │
└─────┘
(sparse: only 3 non-zeros)
Finding which columns of A sum to t (with signs) is computationally infeasible.
Domain: Multilinear algebra / Tensor computation
The Problem:
Given:
- A 3-dimensional tensor T ∈ ℤq^{n×n×n}
Distinguish:
- Is T a low-rank tensor? T = Σᵢ aᵢ ⊗ bᵢ ⊗ cᵢ (rank r)
- Or is T random noise?
Why It's Hard:
- Tensor rank computation is NP-hard over finite fields
- No known quantum speedup for tensor decomposition
- Mathematically unrelated to lattice problems
- Requires finding the hidden low-rank structure
Visual Intuition:
A 3D tensor (imagine a Rubik's cube of numbers):
┌─────────────────┐
/│ /│
/ │ n / │
/ │ / │
┌───┼─────────────┐ │
│ │ │ │
n │ │ │ │
│ └─────────────┼───┘
│ / n │ /
│ / │ /
│/ │/
└─────────────────┘
Secret: This tensor = a₁⊗b₁⊗c₁ + a₂⊗b₂⊗c₂ + ... + aᵣ⊗bᵣ⊗cᵣ
(Finding the vectors a, b, c is the hard problem)
Domain: Graph theory / Group theory
The Problem:
Given:
- Cayley graph G of SL(2, ℤp) with 4 generators
- Starting vertex v_start (2×2 matrix)
- Ending vertex v_end (2×2 matrix)
- Walk length k
Find:
- The sequence of k generator moves from v_start to v_end
Why It's Hard:
- The graph has approximately p³ vertices (enormous)
- There are 4^k possible paths of length k
- Related to discrete logarithm in matrix groups
- No efficient quantum algorithm known
- Graph structure provides optimal expansion (Ramanujan property)
Visual Intuition:
The Cayley Graph (massively simplified):
[Start]
│
┌────┼────┬────┐
│ │ │ │
▼ ▼ ▼ ▼
( ) ( ) ( ) ( ) ← 4 possible first moves
│ │ │ │
┌──┴─┐ ... ... ... ← 16 possible after 2 moves
│ │
... ... ← 4^k possible paths!
│
▼
[End]
Secret: Which sequence of moves (S, S⁻¹, T, T⁻¹) was taken?
| Property | SLSS | TDD | EGRW |
|---|---|---|---|
| Mathematical Domain | Lattices | Tensors | Graphs |
| NP-Hard | ✓ (subset sum) | ✓ (rank decomposition) | Related |
| Quantum Speedup | Partial | None known | None known |
| Structure Exploited | Sparsity + Lattice | Multilinearity | Expansion |
| Relationship to Others | Independent | Independent | Independent |
The key insight: No known algorithm solves all three efficiently, and there's no theoretical reason to believe such an algorithm exists.
┌─────────────────────────────────────────────────────────────────────┐
│ KEY GENERATION │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ Seed (256 bits) │
│ │ │
│ ├──────────────┬──────────────┬──────────────┐ │
│ ▼ ▼ ▼ ▼ │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ Expand │ │ SLSS │ │ TDD │ │ EGRW │ │
│ │ Seeds │───▶│ KeyGen │───▶│ KeyGen │───▶│ KeyGen │ │
│ └─────────┘ └────┬────┘ └────┬────┘ └────┬────┘ │
│ │ │ │ │
│ ▼ ▼ ▼ │
│ [SLSS Keys] [TDD Keys] [EGRW Keys] │
│ │ │ │ │
│ └──────────────┼──────────────┘ │
│ ▼ │
│ ┌──────────────┐ │
│ │ BINDING │ │
│ │ COMMITMENT │ │
│ └──────────────┘ │
│ │ │
│ ┌───────────┴───────────┐ │
│ ▼ ▼ │
│ PUBLIC KEY SECRET KEY │
│ (~0.8-3.2 MB) (~9-18 KB) │
└─────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────┐
│ ENCAPSULATION │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ Generate random ephemeral secret: m │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────┐ │
│ │ SECRET SHARING (XOR-based) │ │
│ │ m = m₁ ⊕ m₂ ⊕ m₃ │ │
│ │ (Each fragment reveals NOTHING about m) │ │
│ └───────────────────┬─────────────────────────────┘ │
│ │ │
│ ┌──────────────┼──────────────┐ │
│ ▼ ▼ ▼ │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ SLSS │ │ TDD │ │ EGRW │ │
│ │ Encrypt │ │ Encrypt │ │ Encrypt │ │
│ │ m₁ │ │ m₂ │ │ m₃ │ │
│ └────┬────┘ └────┬────┘ └────┬────┘ │
│ │ │ │ │
│ ▼ ▼ ▼ │
│ [c₁] [c₂] [c₃] │
│ │ │ │ │
│ └──────────────┼──────────────┘ │
│ ▼ │
│ ┌──────────────────────┐ │
│ │ NIZK PROOF │ │
│ │ (proves correct │ │
│ │ construction) │ │
│ └──────────────────────┘ │
│ │ │
│ ┌──────────────┴──────────────┐ │
│ ▼ ▼ │
│ CIPHERTEXT SHARED SECRET │
│ (c₁, c₂, c₃, proof) = SHAKE256(m || ...) │
└─────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────┐
│ DECAPSULATION │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ CIPHERTEXT (c₁, c₂, c₃, proof) │
│ │ │
│ ▼ │
│ ┌─────────────────────┐ │
│ │ VERIFY NIZK │ ← Ensures ciphertext is well-formed │
│ │ PROOF │ │
│ └──────────┬──────────┘ │
│ │ │
│ ┌─────┴─────┬─────────────┐ │
│ ▼ ▼ ▼ │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ SLSS │ │ TDD │ │ EGRW │ │
│ │ Decrypt │ │ Decrypt │ │ Decrypt │ ← Requires SECRET KEY │
│ │ c₁ │ │ c₂ │ │ c₃ │ │
│ └────┬────┘ └────┬────┘ └────┬────┘ │
│ │ │ │ │
│ ▼ ▼ ▼ │
│ [m₁'] [m₂'] [m₃'] │
│ │ │ │ │
│ └───────────┼────────────┘ │
│ ▼ │
│ ┌─────────────────────────────────────────────────┐ │
│ │ RECONSTRUCT: m' = m₁' ⊕ m₂' ⊕ m₃' │ │
│ └─────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────┐ │
│ │ RE-ENCAPSULATE & VERIFY │ │
│ │ (Fujisaki-Okamoto transform for IND-CCA2) │ │
│ └─────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ SHARED SECRET │
│ = SHAKE256(m' || ...) │
└─────────────────────────────────────────────────────────────────────┘
A Key Encapsulation Mechanism (KEM) is a cryptographic primitive that establishes a shared secret between two parties:
- Alice generates a key pair (public key, secret key)
- Alice shares her public key with Bob
- Bob uses Alice's public key to create a ciphertext and shared secret
- Alice uses her secret key to recover the same shared secret
The shared secret is then used with symmetric encryption (e.g., AES-256-GCM) for actual message encryption.
// Key Generation
const { publicKey, secretKey } = await kemGenerateKeyPair(SecurityLevel.MOS_128)
// Encapsulation (Bob's side)
const { ciphertext, sharedSecret } = await encapsulate(publicKey)
// Decapsulation (Alice's side)
const recovered = await decapsulate(ciphertext, secretKey, publicKey)
// sharedSecret === recovered (32 bytes of shared entropy)| Property | Description | How kMOSAIC Achieves It |
|---|---|---|
| IND-CPA | Ciphertexts are indistinguishable | Three independent encryption schemes |
| IND-CCA2 | Secure against chosen-ciphertext attacks | Fujisaki-Okamoto transform with implicit rejection |
| Key Indistinguishability | Shared secrets look random | SHAKE256 key derivation |
| Parameter | MOS-128 | MOS-256 | Description |
|---|---|---|---|
| Security Target | 128-bit | 256-bit | Post-quantum security level |
| SLSS n | 512 | 1024 | Lattice dimension |
| SLSS m | 384 | 768 | Number of equations |
| SLSS w | 64 | 128 | Sparsity weight |
| TDD n | 24 | 36 | Tensor dimension |
| TDD r | 6 | 9 | Tensor rank |
| EGRW p | 1021 | 2039 | Prime (graph size ≈ p³) |
| EGRW k | 128 | 256 | Walk length |
| Public Key | ~824 KB | ~3.2 MB | Dominated by TDD tensor ( |
| Secret Key | ~9 KB | ~18 KB | - |
| Ciphertext | ~5.9 KB | ~10.7 KB | - |
| Shared Secret | 32 bytes | 32 bytes | - |
Traditional digital signatures prove knowledge of one witness (the secret key). kMOSAIC-SIGN proves knowledge of three entangled witnesses simultaneously.
Traditional Fiat-Shamir: kMOSAIC Multi-Witness:
Commit(witness) → c Commit(w₁) → c₁
Commit(w₂) → c₂
Commit(w₃) → c₃
Challenge = H(c || msg) Challenge = H(c₁||c₂||c₃||msg)
↑
└── Binds ALL THREE together
Response(witness, ch) Response(w₁, ch) → z₁
Response(w₂, ch) → z₂
Response(w₃, ch) → z₃
An attacker forging a signature must:
- Know the SLSS secret (sparse lattice vector)
- Know the TDD secret (tensor decomposition factors)
- Know the EGRW secret (random walk path)
All three responses must be consistent with the same unified challenge.
| Property | MOS-128 | MOS-256 | Notes |
|---|---|---|---|
| Public Key | ~2.7 MB | ~11 MB | Three component keys |
| Secret Key | ~9 KB | ~18 KB | Three witnesses |
| Signature | ~6 KB | ~12 KB | Three responses + hints |
| Sign Time | ~26 ms | ~51 ms | Parallelizable |
| Verify Time | ~4 ms | ~14 ms | Parallelizable |
To recover a kMOSAIC-protected secret, an attacker must break all three problems:
┌─────────────────────────────────────────────────────────────────┐
│ ATTACK SCENARIOS │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Scenario 1: Break SLSS only │
│ ───────────────────────────── │
│ Recovers: m₁ (first fragment) │
│ Information about secret K: ZERO (information-theoretic) │
│ Result: Attack fails ✗ │
│ │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Scenario 2: Break TDD only │
│ ───────────────────────────── │
│ Recovers: m₂ (second fragment) │
│ Information about secret K: ZERO │
│ Result: Attack fails ✗ │
│ │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Scenario 3: Break EGRW only │
│ ───────────────────────────── │
│ Recovers: m₃ (third fragment) │
│ Information about secret K: ZERO │
│ Result: Attack fails ✗ │
│ │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Scenario 4: Break any TWO problems │
│ ───────────────────────────────── │
│ Recovers: Two fragments (e.g., m₁ and m₂) │
│ Information about K: Still ZERO! │
│ Why: XOR sharing requires ALL shares │
│ Result: Attack fails ✗ │
│ │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Scenario 5: Break ALL THREE problems │
│ ──────────────────────────────────── │
│ Recovers: m₁, m₂, m₃ │
│ Can compute: K = m₁ ⊕ m₂ ⊕ m₃ │
│ Result: Attack succeeds ✓ │
│ │
└─────────────────────────────────────────────────────────────────┘
| Attack Type | Affects | Impact on kMOSAIC |
|---|---|---|
| Shor's Algorithm | Factoring, Discrete Log | ✗ Not applicable |
| Grover's Algorithm | Brute force search | Quadratic speedup on each component (accounted for in parameters) |
| BKZ/LLL for Lattices | SLSS only | Breaks only 1/3 of the construction |
| Tensor Quantum Algorithms | TDD | None known |
| Graph Quantum Algorithms | EGRW | None efficient known |
Key Insight: There's no known quantum algorithm that simultaneously attacks all three problem types.
Claim: kMOSAIC-KEM is IND-CCA2 secure under the following assumptions:
- The SLSS problem is hard (related to LWE + subset sum)
- The TDD problem is hard (tensor decomposition is NP-hard)
- The EGRW problem is hard (navigation in Cayley graphs)
- SHAKE256 behaves as a random oracle
- The NIZK proof system is sound and zero-knowledge
The probability of breaking kMOSAIC is:
P(break kMOSAIC) ≈ P(break SLSS) × P(break TDD) × P(break EGRW)
The security of the combined construction relies on all three problems remaining hard. The heterogeneous nature provides defense-in-depth: breaking any single problem family does not compromise the system.
| Limitation | Severity | Notes |
|---|---|---|
| No formal security proof | High | Requires academic cryptanalysis |
| Novel construction | High | May have unforeseen weaknesses |
| Larger key sizes | Medium | Trade-off for defense-in-depth |
| JavaScript timing | Implementation | Use native implementations for production |
An internal security audit identified and addressed the following issues:
| Issue | Severity | Status | Resolution |
|---|---|---|---|
| TDD plaintext storage | 🔴 Critical | ✅ Fixed | XOR encryption with masked-matrix keystream |
| EGRW randomness exposure | 🔴 Critical | ✅ Fixed | Ephemeral walk vertex derivation |
| TDD modular bias | 🟠 High | ✅ Fixed | Rejection sampling for uniform distribution |
JavaScript Runtime Limitations (Acknowledged):
- Constant-time operations cannot be guaranteed due to JIT optimization and garbage collection
- Memory zeroization is best-effort due to GC behavior
- These are fundamental to the JavaScript runtime; native implementations are recommended for high-security deployments
For complete audit details, see SECURITY_REPORT.md.
Tested on Apple M2 Pro Mac, Bun runtime, single-threaded (MOS-128, December 2025):
| Operation | Time (ms) | Ops/Sec | Comparison vs Classical |
|---|---|---|---|
| KEM KeyGen | 19.289 ms | 51.8 | ~1223.7x slower than X25519 |
| KEM Encapsulate | 0.538 ms | 1860.0 | ~12.7x slower than X25519 |
| KEM Decapsulate | 4.220 ms | 237.0 | ~138.5x slower than X25519 |
| Sign KeyGen | 19.204 ms | 52.1 | ~1555.0x slower than Ed25519 |
| Sign | 0.040 ms | 25049.6 | ~3.5x slower than Ed25519 |
| Verify | 1.417 ms | 705.9 | ~43.4x slower than Ed25519 |
| Scheme | Public Key | Ciphertext | Security |
|---|---|---|---|
| kMOSAIC MOS-128 | ~824 KB | ~5.9 KB | Target ~128-bit |
| kMOSAIC MOS-256 | ~3.2 MB | ~10.7 KB | Target ~256-bit |
| ML-KEM-768 (Kyber) | 1.2 KB | 1.1 KB | NIST level 3 (~AES-192) |
| ML-KEM-1024 (Kyber) | 1.6 KB | 1.6 KB | NIST level 5 (~AES-256) |
| Classic McEliece | 261 KB | 128 B | Varies by parameter set |
Trade-off: kMOSAIC has significantly larger public keys than Kyber (due to the
Good fit for:
- High-security applications where defense-in-depth is valuable
- Long-term secrets (decades) where future cryptanalysis is a concern
- Systems that can tolerate larger key sizes
- Hybrid approaches combined with established algorithms
Not ideal for:
- Constrained embedded devices
- High-throughput scenarios
- Applications requiring minimal bandwidth
import { kemGenerateKeyPair, encapsulate, decapsulate, MOS_128 } from 'k-mosaic'
async function basicKEM() {
// Step 1: Alice generates a key pair
console.log('Generating kMOSAIC key pair...')
const { publicKey, secretKey } = await kemGenerateKeyPair(MOS_128)
// Step 2: Alice shares publicKey with Bob (over any channel)
// Step 3: Bob encapsulates a shared secret
const { ciphertext, sharedSecret } = await encapsulate(publicKey)
console.log(
"Bob's shared secret:",
Buffer.from(sharedSecret).toString('hex').slice(0, 32) + '...',
)
// Step 4: Bob sends ciphertext to Alice
// Step 5: Alice decapsulates to get the same shared secret
const aliceSecret = await decapsulate(ciphertext, secretKey, publicKey)
console.log(
"Alice's shared secret:",
Buffer.from(aliceSecret).toString('hex').slice(0, 32) + '...',
)
// Step 6: Verify they match
const match = Buffer.from(sharedSecret).equals(Buffer.from(aliceSecret))
console.log('Secrets match:', match) // true
// Now both parties can use the 32-byte shared secret for symmetric encryption
}import { kemGenerateKeyPair, encrypt, decrypt, MOS_128 } from 'k-mosaic'
async function hybridEncryption() {
// Generate key pair
const { publicKey, secretKey } = await kemGenerateKeyPair(MOS_128)
// Encrypt a message (uses KEM + AES-256-GCM internally)
const message = new TextEncoder().encode('Hello, post-quantum world!')
const encrypted = await encrypt(message, publicKey)
console.log('Encrypted size:', encrypted.length, 'bytes')
// Decrypt
const decrypted = await decrypt(encrypted, secretKey, publicKey)
const plaintext = new TextDecoder().decode(decrypted)
console.log('Decrypted:', plaintext)
// "Hello, post-quantum world!"
}import { signGenerateKeyPair, sign, verify, MOS_128 } from 'k-mosaic'
async function digitalSignature() {
// Generate signing key pair
const { publicKey, secretKey } = await signGenerateKeyPair(MOS_128)
// Sign a document
const document = new TextEncoder().encode('Important contract terms...')
const signature = await sign(document, secretKey, publicKey)
console.log('Signature size:', signature.length, 'bytes')
// Anyone can verify with the public key
const isValid = await verify(document, signature, publicKey)
console.log('Signature valid:', isValid) // true
// Tampering detection
const tamperedDoc = new TextEncoder().encode('MODIFIED contract terms...')
const isValidTampered = await verify(tamperedDoc, signature, publicKey)
console.log('Tampered signature valid:', isValidTampered) // false
}import { kemGenerateKeyPair, analyzePublicKey, MOS_128 } from 'k-mosaic'
async function securityAnalysis() {
const { publicKey } = await kemGenerateKeyPair(MOS_128)
// Analyze the security of each component
const analysis = analyzePublicKey(publicKey)
console.log('Security Analysis:')
console.log('─'.repeat(50))
console.log(`SLSS Component:`)
console.log(` Lattice dimension: ${analysis.slss.dimension}`)
console.log(` Sparsity weight: ${analysis.slss.sparsity}`)
console.log(` Estimated security: ~${analysis.slss.estimatedSecurity} bits`)
console.log()
console.log(`TDD Component:`)
console.log(
` Tensor dimension: ${analysis.tdd.tensorDim}×${analysis.tdd.tensorDim}×${analysis.tdd.tensorDim}`,
)
console.log(` Tensor rank: ${analysis.tdd.rank}`)
console.log(` Estimated security: ~${analysis.tdd.estimatedSecurity} bits`)
console.log()
console.log(`EGRW Component:`)
console.log(` Graph size: ~${analysis.egrw.graphSize} vertices`)
console.log(` Walk length: ${analysis.egrw.walkLength}`)
console.log(` Estimated security: ~${analysis.egrw.estimatedSecurity} bits`)
console.log()
console.log(`Combined Security:`)
console.log(` Classical: ~${analysis.combined.estimatedSecurity} bits`)
console.log(` Post-Quantum: ~${analysis.combined.quantumSecurity} bits`)
}| Feature | ML-KEM (Kyber) | kMOSAIC | McEliece |
|---|---|---|---|
| Hardness Assumptions | 1 (M-LWE) | 3 (SLSS+TDD+EGRW) | 1 (Syndrome decoding) |
| Defense-in-Depth | ✗ Single Point of Failure | ✓ Triple Redundancy | ✗ Single Point of Failure |
| Public Key Size | 1.2 KB (Kyber-768) | ~824 KB (MOS-128) | 261 KB (mceliece348864) |
| Ciphertext Size | 1.1 KB (Kyber-768) | ~5.9 KB (MOS-128) | 128 B (mceliece348864) |
| Standardized | NIST (2024) | ✗ Experimental | NIST (2024) |
| Security Proof | Formal (ROM) | Informal (Heuristic) | Formal |
| Quantum Maturity | High | Low | High |
Choose ML-KEM (Kyber) when:
- You need a standardized, proven algorithm
- Bandwidth and key size are critical
- You trust the M-LWE assumption
Choose kMOSAIC when:
- Defense-in-depth is a priority
- You want to hedge against future cryptanalysis
- Key size is not a constraint
- Experimental/research context
Choose McEliece when:
- You prioritize code-based security
- Small ciphertext is important
- Large public keys are acceptable
The history of cryptography shows that assumptions can fail unexpectedly:
| Year | Event | Impact |
|---|---|---|
| 1994 | Shor's algorithm published | RSA, DH, ECC become quantum-vulnerable |
| 2004 | MD5 collisions announced | MD5 no longer suitable for collision resistance |
| 2022 | SIKE broken | NIST PQC finalist eliminated (e.g., ~1 hour for SIKEp434 key recovery) |
kMOSAIC's heterogeneous approach means that even if one problem class is broken, the secret remains protected by the other two. This is particularly critical given the concentration of deployment around lattice-based KEMs and signatures. A major breakthrough in lattice cryptanalysis could undermine lattice-based schemes (e.g., ML-KEM/ML-DSA, and other lattice-based proposals), while kMOSAIC's TDD and EGRW components are designed to be unrelated to lattice assumptions.
- Formal Security Proofs: Develop rigorous security reductions for the combined construction
- Cryptanalysis Invitation: Submit to academic review and cryptographic competitions
- Parameter Optimization: Fine-tune parameters based on latest attack complexity estimates
- Native Implementations: Develop Rust/Go implementations with proper constant-time guarantees
- Hardware Acceleration: Explore SIMD optimizations for matrix/tensor operations
- Threshold Variants: Extend to threshold signatures and distributed key generation
- Submit to academic conferences (CRYPTO, EUROCRYPT, ASIACRYPT)
- Invite public cryptanalysis
- If validated, propose to IETF/NIST for consideration
The current Node.js/TypeScript implementation is for validation and research purposes.
Codebase Statistics:
- Language: TypeScript (Strict Mode)
- Size: ~4,500 lines of code
- Test Coverage: Comprehensive unit tests for all three components
- Dependencies: Minimal (only Node.js built-ins)
A production-quality implementation should be:
- Written in a memory-safe systems language (Rust, Go)
- Formally verified for constant-time execution
- Reviewed by professional cryptographers
- Tested against known attack vectors
kMOSAIC introduces a novel approach to post-quantum cryptography through cryptographic entanglement of three heterogeneous hard problems:
- SLSS: Sparse Lattice Subset Sum (lattice-based)
- TDD: Tensor Decomposition Distinguishing (tensor-based)
- EGRW: Expander Graph Random Walk (graph-based)
The key innovation is that an attacker must break all three independent problems to compromise the system, while breaking any subset reveals zero information about the secret.
- Defense-in-Depth: Multiple independent security layers
- Quantum Diversity: No single quantum algorithm threatens all components
- Information-Theoretic Sharing: Secret fragmentation with perfect security
- Binding Commitment: Components are cryptographically inseparable
We invite the cryptographic community to:
- Analyze the security of this construction
- Attack the reference implementation
- Improve the parameter selection
- Collaborate on formal security proofs
This is an experimental proposal intended to spark discussion about defense-in-depth approaches in post-quantum cryptography.
- Regev, O. (2005). "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography". STOC '05 (DOI)
- Kiltz, E., et al. (2018). "A Modular Analysis of the Fujisaki-Okamoto Transformation". TCC 2017
- Håstad, J. (1990). "Tensor Rank is NP-Complete". J. Algorithms 11(4): 644-654
- Lubotzky, A., et al. (1988). "Ramanujan Graphs". Combinatorica 8, 261–277
- Shamir, A. (1979). "How to Share a Secret". CACM 22(11): 612-613
- Fiat, A., Shamir, A. (1986). "How to Prove Yourself: Practical Solutions to Identification and Signature Problems". CRYPTO 1986
- NIST Post-Quantum Cryptography Standardization (2024). NIST PQC Project
- Bernstein, D.J., Lange, T. (2017). "Post-Quantum Cryptography". Nature 549, 188–194
- Ajtai, M. (1996). "Generating Hard Instances of Lattice Problems". STOC '96
- kMOSAIC TypeScript Implementation: https://github.com/BackendStack21/k-mosaic
function kemGenerateKeyPair(level):
seed ← random(256 bits)
// Generate component keys
(slss_pk, slss_sk) ← SLSS.KeyGen(seed, level.slss_params)
(tdd_pk, tdd_sk) ← TDD.KeyGen(seed, level.tdd_params)
(egrw_pk, egrw_sk) ← EGRW.KeyGen(seed, level.egrw_params)
// Create binding commitment
binding ← SHA3-256(slss_pk || tdd_pk || egrw_pk)
publicKey ← {slss_pk, tdd_pk, egrw_pk, binding, level}
secretKey ← {slss_sk, tdd_sk, egrw_sk, seed}
return (publicKey, secretKey)
function encapsulate(publicKey):
m ← random(256 bits) // Ephemeral secret
// Split secret into three shares
(m₁, m₂, m₃) ← SecretShare(m, 3)
// Encrypt each share with different problem
c₁ ← SLSS.Encrypt(m₁, publicKey.slss)
c₂ ← TDD.Encrypt(m₂, publicKey.tdd)
c₃ ← EGRW.Encrypt(m₃, publicKey.egrw)
// Generate NIZK proof of correct construction
proof ← NIZK.Prove(m, m₁, m₂, m₃, c₁, c₂, c₃)
ciphertext ← {c₁, c₂, c₃, proof}
sharedSecret ← SHAKE256(m || Hash(ciphertext), 32)
return (ciphertext, sharedSecret)
function decapsulate(ciphertext, secretKey, publicKey):
// Verify NIZK proof
if not NIZK.Verify(ciphertext.proof, ciphertext):
return ⊥
// Decrypt each component
m₁' ← SLSS.Decrypt(ciphertext.c₁, secretKey.slss)
m₂' ← TDD.Decrypt(ciphertext.c₂, secretKey.tdd)
m₃' ← EGRW.Decrypt(ciphertext.c₃, secretKey.egrw)
// Reconstruct secret
m' ← m₁' ⊕ m₂' ⊕ m₃'
// Re-encapsulate to verify (Fujisaki-Okamoto)
(ciphertext', _) ← encapsulate_deterministic(publicKey, m')
if ciphertext' ≠ ciphertext:
// Implicit rejection
return SHAKE256(secretKey.seed || Hash(ciphertext), 32)
else:
return SHAKE256(m' || Hash(ciphertext), 32)
For SLSS with parameters (n, m, q, w):
- Lattice dimension: n
- Sparsity: w non-zero entries in {-1, 0, 1}
- Security ≈ 2^(0.292 × n) for lattice attacks
- Additional hardness from sparsity constraint
For TDD with parameters (n, r, q):
- Tensor dimension: n × n × n
- Rank: r
- Best known attacks: O(n^(r/2)) operations
- Security ≈ r × log₂(n) bits
For EGRW with parameters (p, k):
- Graph size: |SL(2, ℤp)| ≈ p³
- Walk length: k
- Possible paths: 4^k
- Security ≈ min(k × log₂(4), 3 × log₂(p))
Document Version: 1.0
Last Updated: December 26, 2025
Status: Experimental - Not for Production Use