Paper Info
Title
Generalized probabilistic satisfiability and applications to modelling attackers with side-channel capabilities
Abstract
We analyze a generalized probabilistic satisfiability problem (GenPSAT) which consists in deciding the satisfiability of linear inequalities involving probabilities of classical propositional formulas. GenPSAT is proved to be NP-complete and we present a polynomial reduction to Mixed-Integer Programming. Capitalizing on this translation, we implement and test a solver for the GenPSAT problem. As previously observed for many other NP-complete problems, we are able to detect a phase transition behaviour for GenPSAT. We also describe GGenPSAT, which generalizes GenPSAT by allowing Boolean combinations of linear inequalities involving probabilities of classical propositional formulas which we use to develop applications in information security. Namely, in the context of cryptographic protocols, we model classes of attackers with side-channel capabilities, and study the problem of deciding whether a formula is perfectly masked in the presence of such attackers.
Year
DOI
Venue
2019
10.1016/j.tcs.2019.02.021
Theoretical Computer Science
Keywords
Field
DocType
Probabilistic satisfiability,GenPSAT,GGenPSAT,Phase transition,Side-channel attacks
Discrete mathematics,Cryptographic protocol,Polynomial,Boolean satisfiability problem,Satisfiability,Theoretical computer science,Side channel attack,Probabilistic logic,Solver,Linear inequality,Mathematics
Journal
Volume
ISSN
Citations 
781
0304-3975
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Carlos Caleiro1144.23
Filipe Casal212.40
Andreia Mordido302.37