Skip to main content

​
FNP - Cryptography - M²-ORE Order-Revealing Encryption

​
Summary (Explain Like I’m 5)

Imagine you have secret numbers [3, 7, 2, 9, 1], and you want to send them to a friend encrypted so they can’t see the actual values, but they should still be able to sort them correctly. M²-ORE does this magic: You encrypt them as [🔒A, 🔒B, 🔒C, 🔒D, 🔒E], and your friend can determine: 🔒E < 🔒C < 🔒A < 🔒B < 🔒D ✓ (correct order, 1 < 2 < 3 < 7 < 9) The trick: Add special “noise” to each number that’s small enough to not flip the ordering but big enough to hide the exact value.

​
Technical Deep Dive

M²-ORE (Module-LWE Order-Revealing Encryption) is a deterministic symmetric encryption scheme based on Learning With Errors that reveals message ordering without decryption. Parameters (Solution C - Hybrid):
ParameterValueRationale
n (LWE dimension)1536Increased from Kyber’s 1024 to tolerate encryption noise
k (Module rank)4Kyber-1024 compatibility; module structure for security
q (Modulus)2^56Must satisfy q > 2^54 for signal >> noise determinism
β (Error)±1 (CBD)Centered binomial: Pr[e=±1]=1/2, Pr[e=0]=1/2
Encryption Algorithm: 
Enc(pk, m ∈ [0, 2^54)):
  1. Scale: m' = m · (q / 2^54)
  2. Sample: r ← Z_q^k (randomness)
  3. Sample: e' ← β (noise)
  4. Compute: u = A·r mod q
  5. Compute: v = ⟨s, u⟩ + e' + m' mod q
  Output: (u, v)
Comparison Algorithm: 
Compare(c₁=(u₁,v₁), c₂=(u₂,v₂)):
  δ = v₁ - v₂ mod q
  if δ < q/2: return 1 (m₁ > m₂)
  else: return 0 (m₁ < m₂)
Security: 115-bit quantum security (230-bit classical). Sufficient for ephemeral ordering keys but should be rotated monthly. Leakage: Only reveals relative ordering m₁ > m₂, NOT exact values, NOT distances, NOT repeated messages.

​
Mermaid Diagrams

​
Key Terms

  • Order-Revealing → Enables comparison without decryption; deterministic ordering preserved
  • Module-LWE → Lattice problem with module structure; believed post-quantum hard
  • Deterministic → Same message always encrypts to same ciphertext (no semantic security)
  • Signal vs Noise → Signal = scaled message, Noise = error term; signal >> noise ensures correctness
  • IND-OCPA → Indistinguishability under Order-Correlated Plaintext Attack; best possible security model for ORE
  • Ephemeral Key → Short-lived key; M²-ORE ordering keys should be rotated monthly
  • Quantum Security → 115 bits; approximately 2^115 quantum operations to break

​
Q/A

Q: Why not just use regular encryption? A: Regular encryption is “semantic secure” - identical messages encrypt to different ciphertexts each time, preventing server-side comparison. M²-ORE is deterministic specifically to enable ordering without decryption, sacrificing semantic security for functionality. Q: Can the server recover plaintext messages from encrypted positions? A: No. The noise added (±1 centered binomial) ensures the recovered message is only accurate if you know the secret key. Without sk, the lattice problem (Learning With Errors) is computationally hard. Q: Why is 115 bits quantum security okay for ordering but not for long-term confidentiality? A: Ordering is ephemeral - it’s only needed during active document editing. M²-ORE keys rotate monthly. Kyber (128-bit quantum) handles long-term content confidentiality, which needs to resist adversaries collecting ciphertexts now and decrypting later with quantum computers. Q: How does noise prevent collision attacks where two different messages encrypt identically? A: With q=2^56 and messages scaled to 54 bits, the “gap” between consecutive messages is ≈2^2. Noise is only ±1, so signal >> noise. Collisions are astronomically unlikely for distinct messages. Q: What happens if someone replays an old encrypted position? A: LSEQ identifiers include (digit, site, counter), and operations are timestamped with Lamport clocks. Replayed operations are detected as duplicates and rejected by the CRDT merge logic.

​
Example / Analogy

Weighted Boxes Analogy: Your friend is organizing a library but you want to keep book titles secret:
  • Traditional encryption: Books in locked boxes, friend can’t sort them
  • With M²-ORE: Books in locked boxes with hidden weights:
    • Heavy box = important book (higher priority)
    • Friend can sort by weight without opening boxes
    • Weights slightly randomized so friend can’t guess exact title
    • But weights are randomized carefully: a “War & Peace” box is always heavier than a “Sonnet” box
Real-world FNP Application: You and colleague edit encrypted medical record simultaneously:
  • Your edits are encrypted (only you read them)
  • Server can still determine character positions and order (M²-ORE)
  • Server merges edits deterministically
  • Colleague sees encrypted positions, can’t read your content (maintains privacy)
  • Both of you see correct document order
Cross-References: System Overview, LSEQ CRDT, Kyber-1024, FNP Protocol Flow, Halo2 Circuits Category: Cryptography | Protocol | Post-Quantum Difficulty: Intermediate ⭐⭐⭐ Updated: 2025-11-28