# Exact Soft Analytical Side-Channel Attacks using Tractable Circuits

arXiv: https://arxiv.org/abs/2501.13748 · HTML: https://mlsanity.com/paper/2501.13748/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 31 references that are in the map.
- First posted on arXiv 23 Jan 2025.

## Builds on (most cited first, 4 of 4)

- [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022)
- [A Differential Approach to Inference in Bayesian Networks](https://mlsanity.com/paper/1301.3847/) (2013)
- [Systematic Classification of Side-Channel Attacks: A Case Study for Mobile Devices](https://mlsanity.com/paper/1611.03748/) (2016)
- [Understanding the Behavior of Belief Propagation](https://mlsanity.com/paper/2209.05464/) (2022)

## Built on by (most cited first, 1 of 1)

- [The Limits of Tractable Marginalization](https://mlsanity.com/paper/2506.12020/) (2025)

## Abstract (arXiv)

Detecting weaknesses in cryptographic algorithms is of utmost importance for designing secure information systems. The state-of-the-art soft analytical side-channel attack (SASCA) uses physical leakage information to make probabilistic predictions about intermediate computations and combines these "guesses" with the known algorithmic logic to compute the posterior distribution over the key. This attack is commonly performed via loopy belief propagation, which, however, lacks guarantees in terms of convergence and inference quality. In this paper, we develop a fast and exact inference method for SASCA, denoted as ExSASCA, by leveraging knowledge compilation and tractable probabilistic circuits. When attacking the Advanced Encryption Standard (AES), the most widely used encryption algorithm to date, ExSASCA outperforms SASCA by more than 31% top-1 success rate absolute. By leveraging sparse belief messages, this performance is achieved with little more computational cost than SASCA, and about 3 orders of magnitude less than exact inference via exhaustive enumeration. Even with dense belief messages, ExSASCA still uses 6 times less computations than exhaustive inference.