FNP M²-ORE Order-Revealing Encryption

ELI5

M²-ORE is a special type of encryption where the server can compare two encrypted numbers to see which is bigger, without knowing what the actual numbers are. It’s like two friends wrapping their favorite chocolates in boxes and asking a neutral party to sort the boxes by heaviness without opening them. The party can compare weights but never sees what’s inside.

Technical Deep Dive

Why Order-Revealing Matters

Standard encryption (Kyber) is semantically secure — encrypting the same plaintext twice gives different ciphertexts. This is great for privacy but terrible for ordering:

Encrypt("position 5") = "AWZZ..."
Encrypt("position 5") = "KXMQ..."  # Same plaintext, different ciphertext!
Server can't compare

M²-ORE is deterministic — same plaintext always encrypts to the same ciphertext, and ordering is preserved:

Encrypt("position 3") = "ABC..."
Encrypt("position 7") = "XYZ..."
Server compares: "ABC..." < "XYZ..." ✓ (just like 3 < 7)

M²-ORE Algorithm Overview

Parameters:

• n = 1536 (dimension)
• k = 4 (rank)
• q = 2^56 (modulus)
• Security: 115-bit quantum resistance for ephemeral keys

Encryption:

E(m, K) = (⌊α·m⌋ + noise₁, matrix_mult(K, secret) + noise₂)

Where:

• m = plaintext position (integer)
• α = scaling factor
• noise₁, noise₂ = small random noise
• Signal >> noise ensures comparisons stay correct

Comparison (server-side, no decryption):

if Enc(m₁) > Enc(m₂):  # lexicographic comparison of ciphertext
    assert m₁ > m₂     # holds with 2^-115 failure probability

Threat Model & Limitations

What M²-ORE reveals:

• Ordering (which position is larger)
• Frequency (repeated encryptions match, enabling inference attacks)

What M²-ORE hides:

• Exact values (attacker learns “A < B < C” but not magnitudes)
• Distances (attacker can’t compute gaps between positions)

Known vulnerabilities:

• Frequency analysis (repeated plaintext = repeated ciphertext)
• Migitated in FNP by: adding random padding to LSEQ positions

Key Terms

• Order-revealing encryption (ORE) → Encryption preserving comparison relationships without decryption
• Deterministic encryption → Same plaintext always encrypts identically (vs semantic security)
• Signal-to-noise ratio → Ratio ensuring deterministic ordering despite adding noise; must be >115-bit
• Module-LWE → Lattice problem hardness assumption; quantum-resistant

Q&A

Q: Why add noise if it might make comparisons wrong? A: The signal (value) is scaled much larger than noise magnitude. Math guarantees: with overwhelming probability, signal dominates. Failure probability: 2^-115 (essentially zero).

Q: Can the server infer exact positions from encrypted values? A: No — only ordering is revealed, not distances. Attacker learns “A < B < C” but can’t learn gap sizes. Padding further obscures patterns.

Q: Why are M²-ORE keys ephemeral (not long-term)? A: Frequency attacks accumulate with time. Fresh keys per session reset the attack surface. Rotation every 30 days limits information leakage.

Examples

M²-ORE is like a mail sorter’s scale: she weighs packages (encrypted positions) without opening them and sorts by weight. She can order the packages correctly but never learns the actual address (position). If Alice ships 10 copies of the same box daily, the sorter might infer those are the same sender (frequency analysis), so Amazon adds random padding.