Research map / Graph learning / Graph algorithms and clustering
Learning Plaintext-Ciphertext Cryptographic Problems via ANF-based SAT Instance Representation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes an ANF-based graph representation of plaintext-ciphertext SAT instances and CryptoANFNet, a message-passing graph classifier that predicts satisfiability and supports a bit-wise key-solving procedure.
Problem
Learning to predict satisfiability of plaintext-ciphertext cryptographic problems (MQ systems) is hard for neural SAT solvers because CNF encodings of XOR operations cause scale explosion and lose high-order structure.
Approach
Encode the algebraic normal form (ANF) of the instance directly as a tripartite graph (vanilla literals, second-order literals, clauses with complementary positive/negative clause nodes), so XORs are native and products are represented as second-order literal nodes; a NeuroSAT-style message-passing network with modified update rules classifies satisfiability, and a key-solving procedure compares p
Key results
- CryptoANFNet reaches 96% vs NeuroSAT 91% accuracy on SR(5) and 72% vs 55% on Speck 3-8-16.
- Key-solving algorithm raises Scipher 3-8-16 accuracy from 76.5% to 82% and Speck 3-8-16 from 72% to 75%.
- CryptoANFNet achieves roughly 50x average speedup over heuristic solvers (CryptoMiniSat, Kissat, WDSat) per the paper's claim.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ANF-based CryptoANFNet instead of NeuroSAT | Plaintext-ciphertext satisfiability prediction · SR(5) | accuracy: 91.0% -> 96.0% | Helped |
| Use ANF-based CryptoANFNet instead of NeuroSAT | Plaintext-ciphertext satisfiability prediction · SR(25) | accuracy: 57.0% -> 72.0% | Helped |
| Use ANF-based CryptoANFNet instead of NeuroSAT | Plaintext-ciphertext satisfiability prediction · Scipher-3-8-16 | accuracy: 74.0% -> 76.5% | Helped |
| Use ANF-based CryptoANFNet instead of NeuroSAT | Plaintext-ciphertext satisfiability prediction · Scipher-3-16-32 | accuracy: 72.7% -> 75.6% | Helped |
| Use ANF-based CryptoANFNet instead of NeuroSAT | Plaintext-ciphertext satisfiability prediction · Scipher-6-8-16 | accuracy: 53.0% -> 69.0% | Helped |
| Use ANF-based CryptoANFNet instead of NeuroSAT | Plaintext-ciphertext satisfiability prediction · Scipher-6-16-32 | accuracy: 51.0% -> 66.5% | Helped |
| Use ANF-based CryptoANFNet instead of NeuroSAT | Plaintext-ciphertext satisfiability prediction · Speck-3-8-16 | accuracy: 55.0% -> 72.0% | Helped |
| Use ANF-based CryptoANFNet instead of NeuroSAT | Plaintext-ciphertext satisfiability prediction · Speck-6-8-16 | accuracy: 52.5% -> 68.5% | Helped |
| Apply the key-solving algorithm | CryptoANFNet key-bit prediction · Scipher-3-8-16 | key-bit accuracy: 76.5% -> 82.0% | Helped |
| Apply the key-solving algorithm | CryptoANFNet key-bit prediction · Scipher-3-16-32 | key-bit accuracy: 75.6% -> 78.4% | Helped |
| Apply the key-solving algorithm | CryptoANFNet key-bit prediction · Scipher-6-8-16 | key-bit accuracy: 69.0% -> 70.0% | Helped |
| Apply the key-solving algorithm | CryptoANFNet key-bit prediction · Scipher-6-16-32 | key-bit accuracy: 66.5% -> 69.0% | Helped |
Surprising findings
- NeuroSAT performs near chance (about 50%) on large-scale SR(25) and Speck instances.
Limitations
- Focused only on plaintext-ciphertext MQ problems; other cryptographic problems not explored.
- No error bars or statistical significance reported.
- Key-solving gains are modest and only tested on two ciphers with a small number of rounds.
Experimental setup
Datasets: SR(n) synthetic MQ instances Scipher-r-k-n instances Speck-r-k-n instances
Benchmarks: SR(5) SR(25) Scipher 3-8-16 Scipher 3-16-32 Scipher 6-8-16 Scipher 6-16-32 Speck 3-8-16 Speck 6-8-16
Metrics: accuracy average runtime ms/instance
Baselines: NeuroSAT WDSat CryptoMiniSat Kissat WalkSAT RoundingSAT FourierSAT
Builds on: NeuroSAT LSTM Bosphorus
Closest papers by meaning
- Bridging Crypto with ML-based Solvers: the SAT Formulation and Benchmarks (NeurIPS 2025 · similarity 0.92)
- Learning with Enumeration: Neural-Guided SAT Framework for Cryptographic Key Recovery (NeurIPS 2026 · similarity 0.90)
- Learning Better Representations From Less Data For Propositional Satisfiability (NeurIPS 2024 · similarity 0.82)
- HardCore Generation: Generating Hard UNSAT Problems for Data Augmentation (NeurIPS 2024 · similarity 0.81)
- Can Transformers Reason Logically? A Study in SAT Solving (ICML 2025 · similarity 0.81)
- NeuroBack: Improving CDCL SAT Solving using Graph Neural Networks (ICLR 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.