Research map / Probabilistic and scientific modeling / Variational and generative sampling
Exact Soft Analytical Side-Channel Attacks using Tractable Circuits
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 ExSASCA, an exact soft analytical side-channel attack on AES that reformulates MixColumns as a single high-dimensional factor compiled into tractable (P)SDD circuits, yielding exact key posteriors.
Problem
Soft analytical side-channel attacks (SASCA) rely on loopy belief propagation, which offers no convergence or accuracy guarantees, so inference of the AES key posterior from power leakage is approximate and unreliable.
Approach
Compile the loopy MixColumns subgraph into a single SDD/PSDD (probabilistic sentential decision diagram) so the factor graph becomes a tree and exact message passing is possible via polynomial-time circuit multiplication and marginalization, with sparse-belief and dynamic weighted-model-counting variants.
Key results
- ExSASCA + MPE reaches 67.61% top-1 success rate versus 35.84% for SASCA (100 iterations) at epsilon=0 on the validation set.
- With sparse messages, ExSASCA costs roughly the same as SASCA and about three orders of magnitude less than exhaustive enumeration.
- Even with dense beliefs, ExSASCA MPE uses about 6 times fewer operations than exhaustive inference.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace loopy SASCA inference with exact ExSASCA + MPE inference | AES-128 · AES-128 validation, ε = 0 | top-1 success rate: 35.84 % -> 67.61 % | Helped |
| Replace loopy SASCA inference with exact ExSASCA + MAR inference | AES-128 · AES-128 validation, ε = 0 | top-1 success rate: 35.84 % -> 67.37 % | Helped |
| Use MPE in the true joint key posterior instead of marginal-based MAR (ablation) | ExSASCA · AES-128 validation, ε = 0 | top-1 success rate: 67.37 % -> 67.61 % | Helped |
| Use sparse belief approximation with ε = 10^-2 instead of ε = 0 (ablation) | ExSASCA + MPE · AES-128 validation | top-1 success rate: 67.61 % -> 57.51 % | Hurt |
| Use sparse belief approximation with ε = 10^-8 instead of ε = 0 (ablation) | ExSASCA + MPE · AES-128 validation | top-1 success rate: 67.61 % -> 67.60 % | No clear effect |
| Use sparse belief approximation with ε = 10^-2 instead of ε = 0 (ablation) | ExSASCA + MAR · AES-128 validation | top-1 success rate: 67.37 % -> 57.36 % | Hurt |
| Use sparse belief approximation with ε = 10^-8 instead of ε = 0 (ablation) | ExSASCA + MAR · AES-128 validation | top-1 success rate: 67.37 % -> 67.37 % | No clear effect |
Surprising findings
- Under simulated protection (uniform noise mixing into beliefs), ExSASCA still achieves around 20% success where SASCA fails.
Limitations
- Sparse-message variant relies on low-entropy beliefs and fails to scale when countermeasures add noise, requiring the dense dynamic compilation.
- Only the first AES round is attacked; multi-round attacks are not empirically evaluated because the dataset lacks round key coverage.
- Neural network templates underperformed the hand-designed templates used.
Experimental setup
Datasets: asynchronously captured power traces from STM32F415 (ARM) running AES-128
Benchmarks: AES-128 first-round power trace attack (STM32F415)
Metrics: top-1 success rate computational cost (operations)
Baselines: SASCA Baseline (acyclic BP) exhaustive enumeration
Builds on: soft analytical side-channel attack template attacks sentential decision diagrams probabilistic sentential decision diagrams loopy belief propagation
Closest papers by meaning
- CipherPrune: Efficient and Scalable Private Transformer Inference (ICLR 2025 · similarity 0.81)
- Interpreting Emergent Features in Deep Learning-based Side-channel Analysis (NeurIPS 2025 · similarity 0.81)
- BiShield-TEE: On the (In-)Security of Unilateral Weight Obfuscation in On-Device TEE-Shielded LLM Partition (NeurIPS 2026 · similarity 0.81)
- A Reliable Cryptographic Framework for Empirical Machine Unlearning Evaluation (NeurIPS 2025 · similarity 0.79)
- Sequential Membership Inference Attacks (NeurIPS 2026 · similarity 0.79)
- Learning Plaintext-Ciphertext Cryptographic Problems via ANF-based SAT Instance Representation (NeurIPS 2024 · similarity 0.79)
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.