| name | cim-lwe-qubo-cryptanalysis |
| description | CIM-BDD methodology for LWE cryptanalysis via penalty-free QUBO reduction on Coherent Ising Machines. Use when: analyzing Learning With Errors (LWE) problem security, reducing lattice problems to QUBO for quantum annealing/Ising machines, performing penalty-free mapping of cryptanalytic problems, designing hybrid quantum-classical cryptanalysis workflows, evaluating post-quantum cryptography parameter security. Core insight: algebraic elimination of the secret + nearest-plane decomposition yields compact QUBO without penalty terms. |
CIM-BDD: LWE Cryptanalysis via Penalty-Free QUBO
Overview (arXiv:2606.22843)
CIM-BDD is a hybrid Bounded-Distance-Decoding solver for the LWE problem:
- LWE is the mathematical foundation of post-quantum cryptography (NIST standards)
- Reduces LWE to QUBO via strictly penalty-free mapping
- Uses Coherent Ising Machine (CIM) hardware for solving
Key Innovation: Penalty-Free Mapping
Traditional QUBO reductions use penalty terms to enforce constraints:
- Penalties increase energy landscape complexity
- Require careful parameter tuning
- Often dominate the objective function
CIM-BDD avoids this through:
- Algebraic elimination of the secret: embeds LWE into q-ary lattice directly
- Nearest-plane decomposition (Babai): yields compact binary representation
- No penalty terms needed: constraints are structurally satisfied
Pipeline
Step 1: LWE Instance → BDD Problem
LWE: A·s + e = b (mod q)
→ Find closest lattice point in q-ary lattice Λ_q(A)
→ This is a Bounded-Distance-Decoding (BDD) problem
Step 2: BDD → QUBO (Penalty-Free)
BDD instance → Nearest-plane algorithm (Babai rounding)
→ Binary expansion of coefficients
→ Direct QUBO formulation: min x^T Q x
Step 3: QUBO → CIM
QUBO matrix Q → Ising Hamiltonian H = Σ J_ij σ_i^z σ_j^z
→ Run on Coherent Ising Machine
→ Read optimal binary solution → Decode lattice point
Applications
Post-Quantum Security Analysis
- Evaluate NIST PQC parameter choices (Kyber, Dilithium)
- Find weakest parameter sets for CIM-based attacks
- Compare classical vs quantum-classical hybrid attack complexity
Cryptographic Parameter Selection
- Use CIM-BDD as oracle during parameter selection
- Ensure q-ary lattice instances resist BDD at target security level
Hybrid Attack Design
- Combine with lattice reduction (BKZ) as preprocessing
- Use CIM-BDD for the final SVP/BDD step
- Classical-quantum division of labor
Implementation Notes
- QUBO size scales with lattice dimension and basis quality
- Preprocessing with BKZ reduction significantly improves results
- CIM hardware availability limits practical attack scale
- Penalty-free structure is critical: penalties would make QUBO landscape too rugged for CIM convergence
Activation
cim, coherent ising machine, LWE cryptanalysis, QUBO reduction, penalty-free mapping, post-quantum security, bounded distance decoding, lattice attacks, q-ary lattice
