Antonin Kucera
Masaryk University, Czech
Republic
Title:
"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
logics
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
the properties
of stochastic
games with linear-time winning objectives (Buchi, Rabin, Street, etc.).
In particular, these games are not determined, winning strategies may
require
infinite memory, and the existence of a winning strategy for a general
PCTL formula is highly undecidable even for Markov decision processes
(i.e.,
for the
subclass of stochastic games where Player 2 does not control any
nodes). All results will be explained as informally as possible and
illustrated on
examples.
Catuscia
Palamidessi
LIX, Ecole Polytechnique, France
Title:
"Information-hiding
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
quantitative
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,
using Bayesian
inference, and I will discuss how the probability of error (Bayesian
risk) depends on the matrix. Finally, I will show some examples of
protocol specifications
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.