BIBLIOS

  Sistema de Gestão de Referências Bibliográficas de Ciências

Modo Visitante (Login)
Need help?


Voltar

Detalhes Referência

Tipo
Artigos em Revista

Tipo de Documento
Artigo Completo

Título
Generalized probabilistic satisfiability and applications to modelling attackers with side-channel capabilities

Participantes na publicação
Carlos Caleiro (Author)
Filipe Casal (Author)
Dep. Informática
LASIGE
Andreia Mordido (Author)
Dep. Informática
LASIGE

Resumo
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.

Data de Publicação
2019-03

Suporte
Theoretical Computer Science

Identificadores da Publicação
ISSN - 0304-3975

Editora
Elsevier BV

Identificadores do Documento
DOI - https://doi.org/10.1016/j.tcs.2019.02.021
URL - http://dx.doi.org/10.1016/j.tcs.2019.02.021

Identificadores de Qualidade
SCIMAGO Q1 (2018) - 0.494 - Computer Science (miscellaneous)

Keywords
Probabilistic satisfiability GenPSAT GGenPSAT Phase transition Side-channel attacks


Exportar referência

APA
Carlos Caleiro, Filipe Casal, Andreia Mordido, (2019). Generalized probabilistic satisfiability and applications to modelling attackers with side-channel capabilities. Theoretical Computer Science, ISSN 0304-3975. eISSN . http://dx.doi.org/10.1016/j.tcs.2019.02.021

IEEE
Carlos Caleiro, Filipe Casal, Andreia Mordido, "Generalized probabilistic satisfiability and applications to modelling attackers with side-channel capabilities" in Theoretical Computer Science, 2019. 10.1016/j.tcs.2019.02.021

BIBTEX
@article{35847, author = {Carlos Caleiro and Filipe Casal and Andreia Mordido}, title = {Generalized probabilistic satisfiability and applications to modelling attackers with side-channel capabilities}, journal = {Theoretical Computer Science}, year = 2019, }