Communication Protocols and GAMES/Games*

Damian Niwiński, Jerzy Tyszkiewicz
Warsaw University

*Cross out inapplicable.

Main questions of the talk

How protocols can be modeled by games?
What properties of protocols can be captured by games?
Are wining strategies sufficient?
How to turn our failure into a success?

Case study 1

Communication complexity

A finite function f:X x Y >Z is given.

Player A knows x ε X, player B knows y ε Y. They want to compute f(x,y) exchanging as little information as possible.

The total length of messages exchanged in their optimal protocol is the communication complexity of f.

A protocol is a binary tree with internal nodes labelled by functions either X > {0,1} (where A sends a message) or Y > {0,1} (where B sends a message). Leaves are labelled by elements of Z (which are the values computed by the protocol). The communication complexity of f is the minimal depth of a protocol tree, computing f.

Sources: there is a short survey of communication complexity [Kushilevitz]. I also recomment the book [Kshilevitz,Nisan].

Each of the players makes a move in the game and notifies the other player about the move.

Main observations:

The process of evaluation of f(x,y) is a strategy in a very simple two-person game.
The game is cooperative --- the players help each other to achieve the success, i.e., to compute f(x,y).
There is no adversary.
The objective is to reduce the communication/time required.

Case study 2

Communication complexity over noisy channels

In scenario as in the classical communication complexity, the transmission channel is polluted by random noise: each bit sent is reversed with a fixed probability λ ε (0,1).

Simple protocols, as in the perfect transmission case, do not go through: it is impossible to design a protocol which guarantees success, i.e., always computes f(x,y) (Hint: imagine an unfortunate situation when all bits are set/left 0).

Theorem [Schulman, L.J.,Coding for interactive communication. Codes and complexity. IEEE Trans. Inform. Theory 42 (1996), 1745--1756, abstract.]
There is a transformation, which each protocol computing f in t steps over a noiseless channel, transforms into another protocol, which computes f in c(λ)·t steps over a noisy channel, with probability of failure exponentially small in t.

Communication complexity over unsecure channels

In scenario as in the classical communication complexity, k among the the transmitted bits can be reversed by a hostile intruder.

Investigated in limited form of Ulam Game with lies:

The first player chooses a number x ε {1,...,N}.
The second player must determine x by asking yes/no questions.
The first player is allowed to lie at most k times.

Many papers investigated the length of the optimal strategy for the second player. See short expositions of [Savadjiev] (contains more recent results) and [Montague] (not THAT Montague; gives better references).

Communication complexity over noisy or insecure channels

Main observations:

The protocol describes a strategy in:
- either a two-person game with imperfect information
- or a three-person game, with an adversary; two players cooperate, the adversary plays either randomly or is hostile, but with limited access to the communication.
The objective is to reduce communication/time required.

Case study 3

Bisimulation

Two computing devices are modeled as two transition systems S and T (finite or not). An infinite bisimulation game is played on S and T by two players:

The first wants to prove that S and T are observationally distinguishable.
The second (whom we support) wants to prove that S and T are observationally indistinguishable.
Used to prove properties of communication protocols.

Main observations:

The players are fully antagonistic.
Each of the players needs a strategy to win.
The game is played on two structures.
Communication/time is irrelevant.

Case study 4

Protocols against environment

There are protocols, whose actions are best modeled by games agains environment, e.g., protocols of WWW servers. Such a protocol must be

cooperative for cooperative users
and secure against attacks.

Main objective

Merge all four scenarios
into a single game(s)-oriented framework

We argue that it might be very desirable.

Multitude of adversary forms

Along the examples, we had

No adversary at all (Communication Complexity).
Random adversary (Communication Complexity with noise).
Fully antagonistic adversary (Communication Complexity over insecure channels, Bisimulation and Environment).

Make the form of the adversary a parameter in the model.

Bisimulation + Communication Complexity

Suppose that the shortest winning strategy for the first (bad) player has 2¹⁰⁰⁰ moves. It means that within the lifespan of the hardware on which the systems run, no difference between them will be detected.

Give the problem

given two transition systems and number k, decide if the systems are bisimilar within k steps a meaningful interpretation.

Hopefully it has a lower complexity than the general problem.

Games against environment + Communication Complexity

Suppose that the shortest finite winning strategy for the good player exists, but is exponential in the size of the transition system and the winning condition [Marcinkowski]. It means that the system, while sucure, is susceptible to Denial of Service attacks.

Attack outline:

The users of the system are queued for service.
The hostile users, when granted access, start the exponential game against the system.
Eventually, the system plays with hostile users only and is inaccessible for normal service.

The following problems seem relevant and deserve proper formulation and investigation:

Given a finite game and a number k, does the good player have a winning strategy in at most k moves?
Given a parity game and a number k, does the good player have a winning strategy in which after each odd-coloured vertex a greater even-coloured vertex occurs in at most k moves?

Search for a strategy in communication complexity

In communication complexity, one assumes that the parties agreed upon the optimal protocol beforehand.

One can consider a universal protocol, which always succeeds and achieves the minimal communication, provided that f is finite and is a part of the input.

Enumerate all protocols for f
Choose the ones with minimal communication
Use the lexicographically first one.

The same strategy works for infinite f at the expense of arbitrary small amount of extra communication.

The players send each other the values log^*|x| and log^*|y|
Subsequently they can proceed with a finite fragment of f as before.

Questions:

What is the complexity of universal protocols?
What are complexity/communication tradeoffs?
Can universal protocols be seen as winning strategies? In what game?

On a general level

Main issues:

A single framework for communication complexity, bisimilarity, games against environment.
Form of the adversary.
Length of winning strategies.
Communication and complexity aspects of security.
Protocols with low communication as strategies.

Turning failure into a success?

If in a game the good player has no efficiently computable winning strategy
- then the game with reversed roles is ``cryptographically'' secure.

By analogy:

If in a game the good player has no short winning strategy
- then in the game with reversed roles the bad player has no short strategy to break down the system (even if one exists).

Question

Is there a method to design systems with reversed roles of the players?

Case study 5

Attack on the Needham--Schroeder protocol

Discovered by formal methods, Lowe 1996. [Note: Javier Esparza pointed out that, according to the Lowe's talk on TACAS'96, the attack was discovered by insight, and actually confirmed by formal methods (FDR).]
n_X is a unique "nounce" originating from X.
K_X is the private key of X.
{...}_{K_X} is a message encoded by K_X.

Normal run of the protocol

Communication

Message sent

X ---> Y

From: X	{n_X X}_{K_Y}
To: Y

Y ---> X

From: Y	{n_X n_Y}_{K_X}
To: X

X ---> Y

From: X	{n_Y}_{K_Y}
To: Y

Attack

Red A indicates either the intruder (I) impersonating A, or I thought by B to be A. Yellow messages constitute an attack, in the course of which B communicates with I, but is sure he has communicated with A.

Communication Message sent
A ---> I
From: A {n_A A}_{K_I}
To: I

I ---> B
From: A {n_AA}_{K_B}
To: B

B ---> I
From: B {n_A n_B}_{K_A}
To: A

I ---> A
From: I {n_A n_B}_{K_A}
To: A

A ---> I
From: A {n_B}_{K_I}
To: I

I ---> B
From: A {n_B}_{K_B}
To: B