Post-Quantum KEM

🔒 NTRU Prime Conservative Lattice KEM

Security Level 128-bit post-quantum
Performance ⭐⭐⭐⭐ Very Good
Quantum Resistant ✅ Yes
Design Philosophy Conservative
Public Key Size 1,158 bytes
Ciphertext Size 1,039 bytes

📋 Quick Navigation

📖 Overview 🔧 Parameters 💻 Implementation 🔒 Security ⚡ Performance 🎯 Integration

📖 Overview

NTRU Prime is a lattice-based key encapsulation mechanism designed with a focus on simplicity and security. It provides an alternative to structured lattices with careful parameter selection to avoid potential vulnerabilities, emphasizing conservative design choices and implementation simplicity.

✨ Key Features

🛡️

Conservative Design

Avoids potentially vulnerable algebraic structures

🔢

Prime Parameters

Uses prime polynomial degree (761) for extra security

⚡

Simple Implementation

Straightforward to implement correctly

⚖️

Patent-Free

No patent encumbrances for deployment

🛡️

High Security Margins

Conservative parameter choices for robustness

🔒

Constant-Time

Implementation resistant to timing attacks

🎯 Security Levels

🔒 Classical Security

  • 256-bit equivalent: Very high classical security
  • Lattice-based: Based on well-studied mathematical problems
  • Conservative estimates: Large security margins built in

🔮 Post-Quantum Security

  • NIST Level 1: 128-bit post-quantum security
  • Quantum resistance: Secure against Shor's algorithm
  • Conservative approach: Designed with large safety margins

🔧 Algorithm Parameters

📊 NTRU Prime Parameters

Polynomial Degree
761 (prime)
Prime degree for added security
Public Key Size
1,158 bytes
Encapsulation key size
Private Key Size
1,763 bytes
Decapsulation key size
Ciphertext Size
1,039 bytes
Encapsulated secret size
Shared Secret
32 bytes
Generated secret length
Security Level
NIST Level 1
128-bit post-quantum security

🛡️ Security Properties

🔢

NTRU Lattice Problem

Based on finding short vectors in NTRU lattices

🛡️

Conservative Parameters

Large security margins against known attacks

🔒

IND-CCA2 Security

Secure against adaptive chosen-ciphertext attacks

⚡

Implementation Safe

Designed to resist side-channel attacks

💻 Usage Examples

Basic Key Encapsulation

from metamui_crypto import NTRUPrime

# Key Generation
keypair = NTRUPrime.generate_keypair()

# Encapsulation (Sender)
ciphertext, shared_secret_sender = NTRUPrime.encapsulate(keypair.public_key)

# Decapsulation (Receiver)
shared_secret_receiver = NTRUPrime.decapsulate(ciphertext, keypair.private_key)

# Both parties have the same secret
assert shared_secret_sender == shared_secret_receiver

Hybrid Encryption Scheme

from metamui_crypto import NTRUPrime, ChaCha20Poly1305
import os

def hybrid_encrypt(data, recipient_public_key):
    # Generate ephemeral shared secret
    ciphertext, shared_secret = NTRUPrime.encapsulate(recipient_public_key)
    
    # Derive encryption key
    encryption_key = SHA256.hash(shared_secret + b"encryption")[:32]
    
    # Encrypt data
    cipher = ChaCha20Poly1305(encryption_key)
    nonce = os.urandom(12)
    encrypted_data, tag = cipher.encrypt(data, nonce)
    
    return {
        'kem_ciphertext': ciphertext,
        'nonce': nonce,
        'ciphertext': encrypted_data,
        'tag': tag
    }

def hybrid_decrypt(encrypted_package, private_key):
    # Recover shared secret
    shared_secret = NTRUPrime.decapsulate(
        encrypted_package['kem_ciphertext'],
        private_key
    )
    
    # Derive same encryption key
    encryption_key = SHA256.hash(shared_secret + b"encryption")[:32]
    
    # Decrypt data
    cipher = ChaCha20Poly1305(encryption_key)
    return cipher.decrypt(
        encrypted_package['ciphertext'],
        encrypted_package['tag'],
        encrypted_package['nonce']
    )

Key Serialization and Storage

from metamui_crypto import NTRUPrime
import json
import base64

class NTRUPrimeKeyManager:
    def __init__(self):
        self.keys = {}
    
    def generate_key(self, key_id):
        """Generate and store new keypair"""
        keypair = NTRUPrime.generate_keypair()
        
        self.keys[key_id] = {
            'algorithm': 'ntruprime761',
            'public': base64.b64encode(
                keypair.public_key.to_bytes()
            ).decode(),
            'private': base64.b64encode(
                keypair.private_key.to_bytes()
            ).decode(),
            'created': time.time()
        }
        
        return keypair.public_key
    
    def save_keys(self, filename):
        """Save keys to encrypted file"""
        # In practice, encrypt this file!
        with open(filename, 'w') as f:
            json.dump(self.keys, f, indent=2)
    
    def load_keys(self, filename):
        """Load keys from file"""
        with open(filename, 'r') as f:
            self.keys = json.load(f)
    
    def get_keypair(self, key_id):
        """Retrieve keypair by ID"""
        key_data = self.keys[key_id]
        
        public_key = NTRUPrime.PublicKey.from_bytes(
            base64.b64decode(key_data['public'])
        )
        private_key = NTRUPrime.PrivateKey.from_bytes(
            base64.b64decode(key_data['private'])
        )
        
        return NTRUPrime.Keypair(public_key, private_key)

Forward Secrecy Implementation

from metamui_crypto import NTRUPrime, HKDF
import time

class ForwardSecureChannel:
    def __init__(self):
        self.epoch = 0
        self.master_keypair = NTRUPrime.generate_keypair()
        self.ephemeral_keys = {}
    
    def new_epoch(self):
        """Generate new ephemeral keypair for forward secrecy"""
        self.epoch += 1
        
        # Generate ephemeral keypair
        ephemeral = NTRUPrime.generate_keypair()
        
        # Store with timestamp
        self.ephemeral_keys[self.epoch] = {
            'keypair': ephemeral,
            'timestamp': time.time(),
            'active': True
        }
        
        # Deactivate old keys after delay
        self._cleanup_old_keys()
        
        return ephemeral.public_key, self.epoch
    
    def _cleanup_old_keys(self, retention_time=3600):
        """Remove old ephemeral keys for forward secrecy"""
        current_time = time.time()
        
        for epoch, key_data in list(self.ephemeral_keys.items()):
            if current_time - key_data['timestamp'] > retention_time:
                # Securely delete old keys
                del self.ephemeral_keys[epoch]
    
    def establish_session(self, peer_public_key, peer_epoch):
        """Establish forward-secure session"""
        # Get our ephemeral key for this epoch
        our_ephemeral = self.ephemeral_keys[self.epoch]['keypair']
        
        # Encapsulate with peer's key
        ct1, ss1 = NTRUPrime.encapsulate(peer_public_key)
        
        # They will encapsulate with our ephemeral
        # Combine both shared secrets
        # (In practice, wait for their ciphertext)
        
        return {
            'our_ciphertext': ct1,
            'our_epoch': self.epoch,
            'session_established': True
        }

Implementation Details

Core Components

  1. Polynomial Arithmetic
    • Ring: Z[x]/(x^761 - x - 1)
    • Prime degree avoids some attacks
    • Coefficients in Z/q for various q
  2. Encoding/Decoding
    • Sophisticated packing algorithms
    • Minimize ciphertext size
    • Constant-time operations
  3. Error Correction
    • Built-in error tolerance
    • Ensures correct decapsulation
    • No decryption failures
  4. Parameter Selection
    • Conservative choices
    • Large security margins
    • Avoids structured vulnerabilities

Security Features

  • IND-CCA2 Security: Secure against adaptive chosen ciphertext attacks
  • Conservative Design: Avoids risky optimizations
  • Constant-Time: Implementation avoids timing leaks
  • Misuse Resistance: Hard to implement incorrectly

⚡ Performance Characteristics

Speed Benchmarks

Operation Time Notes
Key Generation 1.2 ms One-time cost
Encapsulation 1.5 ms Includes randomness
Decapsulation 1.8 ms Constant time

Comparison with Other KEMs

Algorithm KeyGen Encap Decap Total Size
NTRU Prime 1.2 ms 1.5 ms 1.8 ms 2.2 KB
ML-KEM-768 0.5 ms 0.6 ms 0.7 ms 2.3 KB
Classic McEliece 500 ms 0.1 ms 0.2 ms 261 KB
RSA-2048 100 ms 0.1 ms 2 ms 0.5 KB

Advanced Usage

Multi-Recipient Encryption

from metamui_crypto import NTRUPrime, AES256GCM
import os

class MultiRecipientEncryption:
    @staticmethod
    def encrypt_for_multiple(data, recipient_public_keys):
        """Encrypt data for multiple recipients efficiently"""
        
        # Generate random data encryption key
        dek = os.urandom(32)
        
        # Encrypt data once
        cipher = AES256GCM(dek)
        nonce = os.urandom(12)
        ciphertext, tag = cipher.encrypt(data, nonce)
        
        # Encapsulate DEK for each recipient
        recipient_blocks = []
        for i, public_key in enumerate(recipient_public_keys):
            kem_ct, shared_secret = NTRUPrime.encapsulate(public_key)
            
            # Wrap DEK with shared secret
            wrapper_key = HKDF.derive(
                shared_secret,
                salt=b"wrap",
                info=f"recipient-{i}".encode(),
                length=32
            )
            wrapped_dek = AES256GCM(wrapper_key).encrypt(
                dek, os.urandom(12)
            )
            
            recipient_blocks.append({
                'recipient_id': i,
                'kem_ciphertext': kem_ct,
                'wrapped_dek': wrapped_dek
            })
        
        return {
            'ciphertext': ciphertext,
            'tag': tag,
            'nonce': nonce,
            'recipients': recipient_blocks
        }

Threshold Decryption

from metamui_crypto import NTRUPrime
import secrets

class ThresholdNTRU:
    """Simplified threshold KEM scheme"""
    
    def __init__(self, threshold, total_shares):
        self.threshold = threshold
        self.total_shares = total_shares
        self.shares = self._generate_shares()
    
    def _generate_shares(self):
        """Generate key shares (simplified)"""
        # In practice, use proper secret sharing
        master = NTRUPrime.generate_keypair()
        
        shares = []
        for i in range(self.total_shares):
            # Each share gets a derived keypair
            share_seed = HKDF.derive(
                master.private_key.to_bytes(),
                salt=b"share",
                info=f"share-{i}".encode(),
                length=32
            )
            share_keypair = NTRUPrime.keypair_from_seed(share_seed)
            
            shares.append({
                'id': i,
                'keypair': share_keypair,
                'master_public': master.public_key
            })
        
        return shares, master.public_key
    
    def partial_decapsulate(self, ciphertext, share_id):
        """Compute partial decapsulation"""
        share = self.shares[0][share_id]
        
        # In practice, use proper threshold scheme
        # This is simplified for demonstration
        partial = NTRUPrime.decapsulate(
            ciphertext,
            share['keypair'].private_key
        )
        
        return partial

🎯 Integration Patterns

TLS 1.3 Integration

class TLSHybridKeyExchange:
    """Hybrid key exchange for TLS 1.3"""
    
    def __init__(self):
        self.classical_key = None
        self.pq_key = None
    
    def generate_key_share(self):
        """Generate hybrid key share"""
        # Classical ECDH
        from metamui_crypto import X25519
        classical = X25519.generate_keypair()
        
        # Post-quantum
        pq = NTRUPrime.generate_keypair()
        
        self.classical_key = classical
        self.pq_key = pq
        
        # Encode for TLS
        key_share = {
            'group': 'x25519_ntruprime761',
            'key_exchange': {
                'x25519': classical.public_key.to_bytes(),
                'ntruprime': pq.public_key.to_bytes()
            }
        }
        
        return key_share
    
    def process_peer_key_share(self, peer_share):
        """Process peer's hybrid key share"""
        # Extract keys
        peer_x25519 = X25519.PublicKey.from_bytes(
            peer_share['key_exchange']['x25519']
        )
        peer_ntru = NTRUPrime.PublicKey.from_bytes(
            peer_share['key_exchange']['ntruprime']
        )
        
        # Compute shared secrets
        classical_ss = X25519.compute_shared_secret(
            self.classical_key.private_key,
            peer_x25519
        )
        
        pq_ct, pq_ss = NTRUPrime.encapsulate(peer_ntru)
        
        # Combine secrets
        master_secret = HKDF.derive(
            classical_ss + pq_ss,
            salt=b"tls13 hybrid",
            info=b"master secret",
            length=48
        )
        
        return master_secret, pq_ct

Common Pitfalls

1. Assuming Deterministic Encapsulation

# Bad: Expecting same ciphertext
# ct1, ss1 = NTRUPrime.encapsulate(public_key)
# ct2, ss2 = NTRUPrime.encapsulate(public_key)
# assert ct1 == ct2  # FAILS! Randomized

# Good: Understanding randomization
ct1, ss1 = NTRUPrime.encapsulate(public_key)
ct2, ss2 = NTRUPrime.encapsulate(public_key)
# Different ciphertexts, different shared secrets

2. Not Handling Large Keys Properly

# Bad: Storing keys in database as strings
# key_str = str(public_key)  # Don't do this!

# Good: Proper serialization
key_bytes = public_key.to_bytes()
# Store as BLOB or base64 encode for text storage
key_b64 = base64.b64encode(key_bytes).decode('ascii')

3. Mixing Parameter Sets

# NTRU has multiple parameter sets
# Don't mix them!

# Bad: Using wrong parameter set
# sntrup653_key = generate_sntrup653_key()
# sntrup761.encapsulate(sntrup653_key)  # Error!

# Good: Consistent parameter set
keypair = NTRUPrime.generate_keypair()  # sntrup761
ct, ss = NTRUPrime.encapsulate(keypair.public_key)  # Same parameters

Performance Optimization

Batch Processing

def batch_encapsulate(public_keys, thread_count=4):
    """Parallel encapsulation for multiple recipients"""
    from concurrent.futures import ThreadPoolExecutor
    
    def encap_worker(public_key):
        return NTRUPrime.encapsulate(public_key)
    
    with ThreadPoolExecutor(max_workers=thread_count) as executor:
        results = list(executor.map(encap_worker, public_keys))
    
    return results

Memory-Efficient Key Generation

class KeyGenerator:
    """Generate keys on-demand to save memory"""
    
    def __init__(self, seed):
        self.seed = seed
        self.counter = 0
    
    def next_keypair(self):
        """Deterministically generate next keypair"""
        # Derive seed for this keypair
        key_seed = HKDF.derive(
            self.seed,
            salt=b"keygen",
            info=f"key-{self.counter}".encode(),
            length=32
        )
        
        self.counter += 1
        
        # Generate keypair from seed
        return NTRUPrime.keypair_from_seed(key_seed)

Resources