Masaryk University, Czech
"PCTL formulae as a winning objective in stochastic games"
Abstract: The talk presents an overview of recent results about
finite-state stochastic games where the winning objectives are
specified by formulae of branching-time
such as PCTL (the goal of Player1/Player2 to is to satisfy/falsify a
given formula). The properties of these games are quite different from
games with linear-time winning objectives (Buchi, Rabin, Street, etc.).
In particular, these games are not determined, winning strategies may
infinite memory, and the existence of a winning strategy for a general
PCTL formula is highly undecidable even for Markov decision processes
subclass of stochastic games where Player 2 does not control any
nodes). All results will be explained as informally as possible and
LIX, Ecole Polytechnique, France
protocols as opaque channels"
Abstract: I will make a brief introduction to the problem of
information-hiding, and present some (randomized) protocols designed to
provide this property.
Then I will introduce an information-theoretic framework in which these
protocols are interpreted as channels, and I will discuss various
definitions of their degree of opacity, showing the relation with
probabilistic definitions of information-hiding in literature. Further,
I will show how
the channel matrix associated to such a protocol can be used by an
adversary to try to infer the secret information from the observables,
inference, and I will discuss how the probability of error (Bayesian
risk) depends on the matrix. Finally, I will show some examples of
using a probabilistic process calculus, and discuss how to compute the
matrix associated to the protocol using model checking techniques. This
talk is based
on joint work with Kostas Chatzikokolakis and Prakash Panangaden.