Françoise Forges
email: fran-coise.forges@gmail.com

Ulrich Horst
email: horst@math.hu-berlin.de

Antoine Salomon
email: antoine.salomon@dauphine.fr

Gorkem Celik

Marie Laclau

Antoine Loeper

Jérôme Renault

Rann Smorodinsky

Bernhard Von Stengel

Roland Strausz

Feasibility and individual rationality in two-person Bayesian games

We de…ne feasible, posterior individually rational solutions for twoperson Bayesian games with a single informed player. Such a solution can be achieved by direct signalling from the informed player and requires approval of both players after the signal has been sent. Without further assumptions on the Bayesian game, a solution does not necessarily exist. We show that, if the uninformed player has a "uniform punishment strategy"against the informed one, the existence of a solution follows from the existence of Nash equilibrium in in…nitely repeated games with lack of information on one side. We consider the extension of the result when both players have private information.

Introduction

The classical folk theorem states that the set of Nash equilibrium payo¤s of an undiscounted in…nitely repeated game with complete information coincides with the set of feasible and individually rational payo¤s of the one-shot game. As emphasized in [START_REF] Myerson | Game theory: analysis of con ‡ict[END_REF], [START_REF] Kalai | A commitment folk theorem[END_REF] and [START_REF] Tennenholtz | Program equilibrium[END_REF], the latter set describes meaningful solutions for one-shot games with commitment, namely, cooperative solutions of the one-shot game. In this paper, we investigate the possible relationship between noncooperative solutions of the in…nitely repeated game and cooperative solutions of the one-shot game when information is incomplete.

We mostly consider a two-person Bayesian game with a single informed player. In such a model, feasibility and individual rationality can take various forms. We introduce feasible, posterior individually rational solutions, which can be achieved by direct signalling from the informed player (i.e., by cheap talk, without the help of a mediator) and are approved by both players after the informed player has sent his signal (i.e., given the posterior belief of the uninformed player). This set is smaller than the set of mediated, incentive compatible, interim individually rational solutions of [START_REF] Myerson | Game theory: analysis of con ‡ict[END_REF], which is always nonempty.

Without further assumptions on the Bayesian game, we show that a feasible, posterior individually rational solution (which will just be referred to as a "solution"when there is no confusion) does not necessarily exist. If the informed player has no decision to make, the problem reduces to a senderreceiver game and there always exists a nonrevealing solution. If the uninformed player knows his own payo¤ (private values), then there always exists a completely revealing solution. We propose another, more interesting, assumption that guarantees the existence of a solution: the uninformed player has a "uniform punishment strategy"(UPS) against the informed one, namely, the uninformed player has a strategy that keeps the informed player at his type-dependent individually rational level, whatever his type. In this case, we show on an example that there may be only partially revealing solutions.

The existence of a feasible, posterior individually rational solution under UPS can be deduced from the existence of a Nash equilibrium in every twoperson undiscounted in…nitely repeated game with lack of information on one side. This class of games was introduced by Aumann, Maschler and Stearns (1968,1995) who identi…ed a particular kind of Nash equilibrium, the joint plan equilibrium, in which there is a single phase of information transmission from the informed player to the uninformed one. [START_REF] Simon | The existence of equilibria in certain games, separation for families of convex functions and a theorem of Borsuk-Ulam type[END_REF] established the existence of a joint plan equilibrium by making use of sophisticated mathematical tools. [START_REF] Sorin | Some results on the existence of Nash equilibria for non-zero sum games with incomplete information[END_REF] …rst proved the result under the assumption that the informed player has two possible types. In the case of private values, the existence of a completely revealing Nash equilibrium is straightforward, as shown by [START_REF] Shalev | Nonzero-sum two-person repeated games with incomplete information and known-own payo¤s[END_REF] (see [START_REF] Forges | Repeated games of incomplete information : nonzero-sum[END_REF], [START_REF] Hart | Nonzero-sum two-person repeated games with incomplete information[END_REF], [START_REF] Renault | On two-player repeated games with lack of information on one side and state-dependent signalling[END_REF], [START_REF] Simon | Separation of joint plan equilibrium payo¤s from the min-max functions[END_REF] and [START_REF] Simon | Equilibria in a class of games and topological results implying their existence[END_REF] for further results on nonzero sum repeated games with incomplete information).

We can interpret our result as an extension of the folk theorem to twoperson games with a single informed player: under UPS, a set of noncooperative solutions of the in…nitely repeated game (i.e., the joint plan equilibrium payo¤s) coincides with a set of feasible, individually rational solutions of the one-shot game (feasibility being understood without a mediator and individual rationality being understood a posteriori). However, when the UPS assumption does not hold, such solutions may not exist in the one-shot game, while joint plan equilibria always exist in the in…nitely repeated one.

There is a large literature on cooperative solutions to Bayesian games and we will not try to survey it here. The main di¤erences between the present paper and others is that we consider situations in which (i) the informed player(s) can only transmit information by cheap talk (ii) both players can decline participation at the very last stage of the contracting process, i.e., after information has been transmitted.

In [START_REF] Myerson | Game theory: analysis of con ‡ict[END_REF]'s approach, individual rationality is formulated at the interim stage, i.e., before mediated information transmission, but further properties are imposed, e.g., appropriate forms of Pareto e¢ ciency. Peters and Celik (2011) and Peters and Szentes (2012) extend Bayesian games by means of speci…c (noncooperative) negotiation schemes, in which the players simultaneously exchange information and partially commit; posterior individual rationality need not hold. A. Kalai and E. [START_REF] Kalai | Cooperation in two-person games, revisited[END_REF] propose the cooperative "coco" solution, which, under suitable assumptions, can be implemented by direct information transmission, with participation constraints at the ex ante or interim stage. The paper is organized as follows: in section 2, we de…ne feasible, posterior individually rational solutions; in section 3, we address the question of the existence of posterior individually rational solutions in two-person Bayesian games and we show that UPS guarantees it by making the connection with in…nitely repeated games; in section 4, we propose further elements of comparison between the one-shot game and the repeated game and we consider the possible extension of our results to two-person Bayesian games in which both players have private information.

2 Individually rational solutions in Bayesian games with a single informed player

Basic framework and feasible solutions

Our basic framework is a two-person Bayesian game in which only player 1 has private (nonveri…able) information. Let K be a …nite set. A type k is chosen in K according to p 2 (K) at a virtual initial stage of the game and only player 1 is informed of k. 1 Unless speci…ed otherwise, we assume that p k > 0 for every k 2 K. Player 1 and player 2 choose simultaneously an action in …nite sets A 1 and A 2 respectively. If the pair of actions a 2 A = A 1 A 2 is chosen, they get the respective payo¤s U k (a) and V k (a). We refer to this game as B(p).

We are going to de…ne a solution for B(p), which will be cooperative in the sense that it speci…es a binding agreement between the players. 2 A solution is described by a …nite set S of signals, a signalling strategy : K ! (S) for the informed player and a joint decision function : S ! (A), which associates a correlated strategy (s) = x s 2 (A) with every signal s 2 S. The interpretation is that after player 1 has sent the signal s, actions are chosen in A on behalf of the players, according to the lottery x s .

The description of a solution in terms of mappings and incorporates basic feasibility conditions. Meaningful feasibility also requires that the informed player's signalling strategy be incentive compatible. For every k 2 K, let (k) = ( j k) be the probability distribution over S associated with the signalling strategy . Together with the prior probability p over K, induces the probability distribution (p )(s) = P k2K p k (s j k) over K S. Let p s = (p k s ) k2K be the posterior probability induced by p and over K; p s is well-de…ned as soon as (p )(s) > 0, i.e., given our assumption that p k > 0 for every k 2 K, as soon as 9k : (s j k) > 0. By restricting S, we can assume that (p )(s) > 0 for every s 2 S. We still use the notation U k and V k to denote the extension of the payo¤ functions to (A).

The signalling strategy : K ! S is incentive compatible (given ) i¤ i) 8k 2 K, 8s; s 0 2 S such that (s j k) > 0 and (s 0 j k) > 0,

U k (x s ) = U k (x s 0 )
ii) 8k 2 K, 8s; s 0 2 S such that (s j k) > 0 and (s 0 j k) = 0,

U k (x s ) U k (x s 0 )
Conditions i) and ii) take into account that player 1 sends a random signal by himself, without the help of a mediator; hence he randomizes over signals s; s 0 2 S if and only if he is indi¤erent between s and s 0 .

Incentive compatibility implies in particular that for all types k, all signals s sent by type k (i.e., such that (s j k) > 0) lead to the same payo¤. Let us set u k U k (x s ) 8s 2 S such that (s j k) > 0.

(

) 1
The payo¤ u k is the …nal interim expected payo¤ of player 1 when his type is k and it coincides with his posterior payo¤, given s, for every relevant s.

Individual rationality

We will require that, in addition to being feasible, a solution be acceptable, namely, individually rational, for both parties. This means that each player should get at least what he can guarantee to himself by playing the original one-shot Bayesian game without cooperating. This motivates the following de…nitions of individual rationality. For player 1, the vector payo¤ matters so that the de…nition does not depend on the underlying probability distribution over K.

De…nition 1 A payo¤ vector u = (u k ) k2K is (interim) individually rational for player 1 in B( ) if player 2 has a strategy in B( ) that prevents player 1 from getting more than u k when his type is k, namely

9 2 (A 2 )8k 2 K8 2 (A 1 ) : U k ( ; ) u k (2)
This de…nition reduces to u min

2 (A 2 ) max 2 (A 1 ) U ( ; )
in the case of complete information, namely, when j K j= 1.

In a similar way, De…nition 2 Let q 2 (K). A payo¤ v is individually rational for player 2 in B(q) if player 1 has a strategy in B(q) that prevents player 2 from getting more than v, namely

9e = (e k ) k2K 2 (A 1 ) K 8 2 (A 2 ) : X k q k V k (e k ; ) v (3)
Individual rationality can be de…ned in an equivalent but more tractable way. 3 Let, for every q 2 (K),

f 1 (q) = max e 2 (A 1 ) K min 2 (A 2 ) X k q k U k (e k ; ) = min 2 (A 2 ) X k q k max 2 (A 1 ) U k ( ; ) = min 2 (A 2 ) X k q k max a 1 2A 1 U k (a 1 ; ) (4)
f 1 (q) is the value of the one-shot zero-sum Bayesian game 1 (q) in which player 1's type k is chosen according to q and payo¤s are de…ned by U k for player 1 and U k for player 2. 4 Of course, player 1 can make use of his private information in 1 (q). As a minimum of linear functions (of q), f 1 is concave over (K).

Lemma 3 A payo¤ vector u = (u k ) k2K is (interim) individually rational for player 1 in B( ) if and only if 8q 2 (K) q u f 1 (q) (5)
where f 1 de…ned by (4).

Proof: We …rst observe that (2) is equivalent to

9 2 (A 2 )8q 2 (K) : X k q k ' k ( ) X k q k u k (6)
where ' k ( ) is de…ned as

' k ( ) = max 2 (A 1 ) U k ( ; ), k 2 K.
On the other hand, from the de…nition of f 1 ,

f 1 (q) = min 2 (A 2 ) X k q k ' k ( ) so that (5) is equivalent to 8q 2 (K)9 2 (A 2 ) : X k q k ' k ( ) X k q k u k (7)
Using that ' k ( ) is convex for every k, one shows that ( 6), [START_REF] Forges | A folk theorem for Bayesian games with commitment[END_REF], either by using a separation argument (see [START_REF] Sorin | A …rst course on zero-sum repeated games[END_REF], proposition 2.7) or by using Sion's minmax theorem on an auxiliary game:

(7) , max q min X k q k ' k ( ) u k 0 (6) , min max q X k q k ' k ( ) u k 0
According to the new formulation (5), a vector payo¤ u is individually rational for player 1 if the hyperplane de…ned by u, namely q u, is above f 1 over the whole simplex (K). This property is much stronger than individual rationality at every type. Let us denote as k the k th extreme point of (K) (i.e., k k = 1, k = 0 for `6 = k) and let us set

u k = f 1 ( k ), namely, u k = min 2 (A 2 ) max 2 (A 1 ) U k ( ; ) = max 2 (A 1 ) min 2 (A 2 ) U k ( ; ) (8)
A payo¤ u k is individually rational for every type k if u k u k (i.e., assuming complete information of type k). If u is individually rational for player 1, then for every k 2 K, u k u k . But the reverse is not true: the hyperplane de…ned by the vector u = (u k ) k2K might not be above f 1 , although u k f 1 ( k ) for every k (see the example in section 3.1 below).

Let us proceed in a similar way for player 2. Let g 1 (q) be the value of the one-shot 5 zero-sum Bayesian game 2 (q) in which player 1's type k is chosen according to q, player 1 can make use of his information and payo¤s are de…ned by V k for player 1 and V k for player 2, namely, for every q 2 (K),

g 1 (q) = min e 2 (A 1 ) K max 2 (A 2 ) X k q k V k (e k ; ) = max 2 (A 2 ) X k q k min 2 (A 1 ) V k ( ; ) = max 2 (A 2 ) X k q k min a 1 2A 1 V k (a 1 ; ) (9)
As a maximum of linear functions (of q), g 1 is convex over (K). The next result is immediate:

Lemma 4 A payo¤ v is individually rational for player 2 in B(q) i¤ v g 1 (q)
, where g 1 is de…ned by (9).

Feasible, posterior individually rational solutions

We are now ready to de…ne a solution for B(p). Henceforth, we refer to a triple (S; ; ) satisfying de…nition 5 as a "feasible, posterior individually rational solution"or simply as a "solution". For player 2, individual rationality is indeed readily stated in terms of the posterior probability distribution given every signal. This participation condition is appropriate if player 2 does not fully commit himself before observing the type dependent signal of player 1. For the latter player, standard interim individually rational is required but, given the strong incentive compatibility conditions, the interim expected payo¤ u k and the posterior payo¤ U k (x s ) coincide as soon as the latter payo¤ is relevant (namely, as soon as (s j k) > 0).

The next lemma states that every solution can be implemented as a Nash equilibrium of a noncooperative game, in which player 1 sends a signal and then both players agree on a joint decision, conditionally on the signal. This implementation procedure o¤ers a justi…cation for the previous formulation of feasibility (involving incentive compatibility) and individual rationality.

Given the basic game B(p), a set of signals S and a joint decision function : S ! (A), let G(p; S; ) be the noncooperative game described as follows:

-Player 1's type k is chosen in K according to p, only player 1 is informed of k.

-Player 1 sends a signal s 2 S to player 2.

-The correlated strategy (s) = x s 2 (A) is proposed to both players.

-The players simultaneously accept or reject the correlated strategy x s .

-If both players accept x s , player 1 gets U k (x s ) and player 2 gets V k (x s ).

-If at least one of the players rejects x s , player 1 chooses a 1 , player 2 chooses a 2 , player 1 gets U k (a 1 ; a 2 ) and player 2 gets V k (a 1 ; a 2 ).

Lemma 6 Let B(p) be a two-person Bayesian game with a single informed player. (S; ; ) de…nes a solution for B(p) if and only if G(p; S; ) has an equilibrium in which player 1 sends his signal according to and both players always accept the correlated strategy that is proposed to them.

Proof: To complete the description of strategies in G(p; S; ) in which player 1's signalling strategy is and both players always accept the correlated strategy, let player 1's decision strategy be : K S ! (A 1 ) in case of rejection and let player 2's decision strategy : S ! (A 2 ) in case of rejection.

Let us set

y k s = max a 1 U k (a 1 ; (s)) b s = max a 2 X k p k s V k ( k (s); a 2 )
Player 1's equilibrium conditions are, for every type k: 8s 2 S such that (s j k) > 0, 8s 0 2 S (even such that (s 0 j k) = 0): U k (x s ) U k (x s 0 ) and U k (x s ) y k s 0 . Indeed, player 1 can consider any signal s 0 , and, having sent s 0 , can accept or reject x s 0 ; in the latter case, player 1 cannot do better than best replying to (s 0 ). Player 1's equilibrium conditions are thus equivalent to incentive compatibility (as de…ned by i) and ii)) together with

u k y k s for every k 2 K, s 2 S ( 10
)
where u = (u k ) k2K is de…ned by [START_REF] Aumann | Repeated Games of Incomplete Information[END_REF]. Let us check that u satis…es [START_REF] Kalai | Cooperation in two-person games, revisited[END_REF] if and only if u is individually rational in the sense of de…nition 1.

Assume that u satis…es (10). For every s, y s = (y k s ) s2S is individually rational in the sense of de…nition 1 (which is satis…ed with = (s)). Hence, u y s is also individually rational in the sense of de…nition 1.

Conversely, if u is individually rational in the sense of de…nition 1, there is a strategy of player 2 for which this de…nition is satis…ed. Let (s) = for every s; then 6Let us come to player 2's equilibrium conditions. Given the signal s, he updates his probability distribution over K to (p k s ) k2K . By rejecting x s and best replying to (s) : K ! (A 1 ), he gets b s . Hence player 2 accepts x s if and only if

y k s = y k = max a 1 U k (a 1 ; ) u k .
X k p k s V k (x s ) b s .
This is equivalent to

P k p k s V k (x s ) is individually rational for player 2 in B(p s ), in the sense of de…nition 2.
Even if every solution can be seen as a Nash equilibrium of some game, this equilibrium is a quite demanding one and we should not expect standard existence theorems to apply. We will turn to the existence issue in the next section. Before that, we recall a standard approach to feasibility and individual rationality, which is quite di¤erent from the previous one.

Mediated interim individually rational solutions

In the game G(p; S; ), the players only rely on a device (namely, ) to perform the lottery over joint actions conditionally on the informed player's signal but do not use any device to communicate. In other words, player 1 has to send his signal by himself (by means of ). Moreover, player 1 can only make use of his private information in the …nal decision by sharing it with player 2.

Myerson (1991, chapter 6, specially section 6.6) considers mediated solutions, in which player 1 is invited to report his information k to a mediator, who directly chooses a joint decision in (A) on behalf of the players. 7 The mediator's strategy can thus be described as a device : K ! (A). Incentive compatibility just says that player 1 cannot bene…t from lying to the mediator, namely

U k ( (k)) U k ( (k 0 )) for every k; k 0 2 K
At a mediated solution, both players accept the help of the mediator at the interim stage, namely, before the mediator implements the device . [START_REF] Myerson | Game theory: analysis of con ‡ict[END_REF] thus requires that player 1's interim expected payo¤ U k ( (k)) k2K be individually rational according to de…nition 1 (namely, satis…es (5)) and player 2's expected payo¤ be individually rational according to de…nition 2.

De…nition 7 Let B(p) be a two-person Bayesian game with a single informed player. A mediated solution for B(p) consists of a device : K ! (A) such that is incentive compatible, player 1's interim expected payo¤ is individually rational and player 2's expected payo¤

P k p k V k ( (k)) is indi- vidually rational in B(p). M [B(p)] R K R
denotes the set of all interim expected payo¤s that can be achieved by a mediated solution in B(p).

M [B(p)] contains the set of Nash interim expected equilibrium payo¤s of B(p) and is thus not empty. 8 By proceeding as in the revelation principle (see [START_REF] Myerson | Game theory: analysis of con ‡ict[END_REF]), one can show that C [B(p)] M [B(p)], i.e., payo¤s to unmediated posterior individually rational solutions can be achieved with the help of a mediator. [START_REF] Forges | A folk theorem for Bayesian games with commitment[END_REF] shows that M [B(p)] can be interpreted as the set all Nash equilibrium payo¤s that the players can achieve by making conditional commitments at the interim stage, a result that was established by [START_REF] Kalai | A commitment folk theorem[END_REF] in the case of complete information.

3 Existence of feasible, posterior individually rational solutions

A counter-example

Let us illustrate the properties de…ned above and let us show that without further assumptions on the Bayesian game, incentive compatibility (in the strong sense of section 2.1) and posterior individual rationality may contradict each other.

Example 1: Let B(p) be de…ned by K = f1; 2g, A 1 = fT; Bg, A 2 = fL; Rg and the following payo¤ matrices:

k = 1 L R T 1; 1 2; 0 B 0; 1 0; 0 k = 2 L R T 0; 0 0; 1 B 2; 0 1; 1
Let us …rst show that, even without taking account of player 2's payo¤s, there cannot be any nonrevealing joint decision that is individually rational for player 1. Indeed, any distribution over A = fT; Bg fL; Rg gives a sum of expected payo¤s u 1 + u 2 2 to player 1. If the original Bayesian game is played noncooperatively, player 2 plays L with some probability . By playing T when k = 1 and B when k = 2, player 1 gets + 2( 1) when k = 1 and 2 + ( 1) when k = 2 and the sum of his expected payo¤s is 3. Similarly, if player 1 sends a signal s that leads to an interior posterior probability distribution, by incentive compatibility, we must have u k = U k (x s ), k = 1; 2, where x s is a distribution over fT; Bg fL; Rg, and again u cannot be individually rational for player 1.

The only way to possibly get an individually rational payo¤ vector for player 1 is thus a completely revealing solution. Such a solution is individually rational for player 2 i¤ L has probability 1 when type 1 is reported, and R has probability 1 when type 2 is reported. This can e.g. be seen from de…nition 2 and lemma 4: an expected payo¤ v is individually rational for player 2 in B(q) i¤ v max fq; 1 qg. This implies that player 1 gets at most 1, whatever his type is. But (1; 1) is not an individually rational vector payo¤ for player 1, since we have seen above that player 1 could guarantee 3 as a sum of expected payo¤s. Actually, according to (4), f 1 (q) = min fq + 2(1 q); 2q + (1 q)g; a vector payo¤ (u 1 ; u 2 ) is thus individually rational for player 1 i¤ u 1 + u 2 3 but taking account of feasibility, this reduces to u 1 + u 2 = 3.

Observe that, according to (8), u 1 = u 2 = 1 in this example, which illustrates well that u 1 1 and u 2 1 is not enough for (u 1 ; u 2 ) to be individually rational for player 1. Playing (T; L) if k = 1 and (B; R) if k = 2 is incentive compatible and naïvely individually rational for player 1. But player 1 will not accept such a contract if he has the possibility of just playing the original game by himself.

3.2 Particular cases where a solution is easily shown to exist

Sender-receiver games

Let us assume that the informed player has no decision to make in the basic Bayesian game B(p), namely, that A 1 is a singleton (equivalently, the informed player has several actions but they have no impact on the payo¤s).

In this case, we can set A 2 = A and (A) can be interpreted as the set of mixed strategies of player 2 in B(p).

In this particular framework, a solution consists of a signalling strategy : K ! (S) for the informed player and a strategy : S ! (A) of the uninformed player. Furthermore,

f 1 (q) = min 2 (A) X k2K q k U k ( ) = min a2A X k2K q k U k (a)
so that every feasible vector payo¤ is individually rational for player 1. For the uninformed player, we have that

g 1 (q) = max 2 (A) X k2K q k V k ( ) = max a2A X k2K q k V k (a)
and the individual rationality condition for this player reduces to

X k p k s V k ( (s)) X k2K p k s V k (a) for every s 2 S, a 2 A
where p s is player 2's posterior probability distribution on K given s. It just says that given player 1's signal, player 2 chooses an action that maximizes his expected payo¤.

It thus appears that (S; ; ) de…nes a solution for B(p) if and only if ( ; ) is a Nash equilibrium of the following, noncooperative, sender-receiver game: player 1 is privately informed of his type k, then player 1 sends a signal s 2 S to player 2 and …nally, player 2 makes a decision a 2 A; player 1 gets U k (a) and player 2 gets V k (a). The uninformed player does not commit at all.

It is well-known (and easy to check) that every sender-receiver game has a nonrevealing equilibrium, namely, an equilibrium in which (s j k) does not depend on k. Hence, there always exists a nonrevealing solution in this case.

"Known own" payo¤s (private values)

Being fully informed in B(p), player 1 obviously knows his own payo¤. In this section, we further assume that player 2's payo¤ does not depend on player 1's type and is just described by a mapping V , independent of k 2 K.

Let us de…ne

v = min 2 (A 1 ) max 2 (A 2 ) V ( ; ) = max 2 (A 2 ) min 2 (A 1 ) V ( ; )
In this simple framework, a joint decision x 2 (A) induces an individually rational payo¤ for the uninformed player in B(p) if and only if V (x) v .

A completely revealing solution in B(p) is easily constructed. Let us take S K, (k j k) = 1 for every k 2 K (so that the posteriors correspond to the extreme points k of (K)) and

(k) = x k 2 arg max U k (x) : x 2 (A); V (x) v 8k 2 K
It is immediate that any (S; ; ) de…ned in this way satis…es incentive compatibility and individual rationality for player 2 (V (x k ) v for every k). To show that it satis…es individual rationality for player 1, recalling (4), let e (q) = k (q) k2K 2 (A 1 ) K be a strategy of player 1 in the game 1 (q) that guarantees him f 1 (q), let 2 (A 2 ) be a strategy of player 2 that guarantees him v in the one-shot game V and let y k (q) = k (q)

. By construction, V (y k (q)) v for every k 2 K. Hence,

U k (x k ) U k (y k (q)) 8k 2 K and q u = P k q k U k (x k ) P k q k U k (y k (q)) f 1 (q).

Uniform punishment strategy

Let us come back to the basic game B(p) and introduce a property of player 1's one-shot game payo¤s U k (:), k 2 K. Recall that for every k 2 K, u k is de…ned as the individually rational level of player 1 of type k, when k is complete information (see ( 8)).

De…nition 8 2 (A 2 ) is a uniform punishment strategy (UPS) of the uninformed player i¤

8k 2 K 8 2 (A 1 ) : U k ( ; ) u k
The property means that the uninformed player can punish the informed one in the harshest way, namely, as if he knew the informed player's type, even without knowing it (see [START_REF] Forges | Bayesian repeated games and reputation[END_REF]). UPS is satis…ed in many games derived from economic applications: auctions, duopoly, contribution to a public good, etc. We will show that under UPS, there always exists a solution. 9As observed before, if a payo¤ vector u = (u k ) k2K is individually rational for player 1 in B( ) (see de…nition 1), it is always true that u k u k 8k 2 K. If player 2 has a uniform strategy, the converse also holds, so that Lemma 9 If the uninformed player has a uniform punishment strategy, a payo¤ vector u = (u k ) k2K is individually rational for player 1 in B( ) i¤ u k u k 8k 2 K. This characterization of player 1's individual rationality is familiar in principal-agent problems. Example 1 above shows that the existence of a uniform punishment strategy is crucial for the "if"part of the lemma.

Let u = (u k ) k2K be player 1's interim expected payo¤ at a solution (namely, (1)): u is individually rational for player 1 i¤ U k (x s ) u k for every k 2 K and for every s 2 S such that (s j k) > 0, namely, if, at every signal s, the joint decision x s is posterior individually rational for player 1. Individual rationality for player 1 can still be written equivalently by making use of the mapping f 1 de…ned in (4), which, under UPS, takes the simple form

f 1 (q) = X k2K q k u k 8q 2 (K)
Indeed, by ( 4) and ( 8), f 1 (q) P k2K q k u k . Conversely, player 1 can guarantee himself P k2K q k u k by playing an optimal strategy in the (one-shot, zero-sum) game with payo¤s U k ( ) when he is of type k, for every k.

We are now ready to state our main result (which holds without any restriction on player 2's payo¤s):

Proposition 10 Let B(p) be a two-person Bayesian game with a single informed player in which the uninformed player has a uniform punishment strategy. For every p 2 (K), B(p) has a feasible, posterior individually rational solution.

We show below that one way to establish proposition 10 is to see that it can be deduced from the existence of special Nash equilibria (namely, Aumann and Maschler (1968, 1995)'s joint plan equilibria) in the undiscounted in…nitely repeated version B 1 (p) of the basic Bayesian game (see [START_REF] Simon | The existence of equilibria in certain games, separation for families of convex functions and a theorem of Borsuk-Ulam type[END_REF]).

A proof of proposition 10 relying on Simon et al. (1995)

Let B 1 (p) be the following in…nitely repeated game: at stage 0, player 1's type k is chosen once and for all according to p; at every stage t = 1; 2; :::, player 1 and player 2 choose simultaneously an action in A 1 and A 2 respectively; the actions chosen at every stage are revealed to both players stage after stage; the stage payo¤s are evaluated by U k (:) and V k (:) and only known to player 1. Payo¤s in B 1 (p) are evaluated through (Banach) limits of means (see [START_REF] Hart | Nonzero-sum two-person repeated games with incomplete information[END_REF] and [START_REF] Forges | Repeated games of incomplete information : nonzero-sum[END_REF]).

In B 1 (p), player 1 can reveal his information through his actions. A simple signalling strategy for player 1 in B 1 (p) can thus be described as in section 2.1, with S = (A 1 ) t for some stage t. According to Aumann, Maschler andStearns (1968, 1995) (see also [START_REF] Forges | Repeated games of incomplete information : nonzero-sum[END_REF]) a joint plan equilibrium in B 1 (p) consists of a signalling strategy for player 1 and for every signal s, of a nonrevealing equilibrium of B 1 (p s ) to be played from stage t + 1 on, given the posterior probability distribution p s that is achieved through signalling. The nonrevealing equilibrium of B 1 (p s ) is described by a correlated strategy10 x s (s) 2 (A) which induces individually rational payo¤s for both players in B 1 (p s ).

To formally de…ne individual rationality in B 1 (q), q 2 (K), let 1;N R (q) (resp., 2;N R (q)) be the one-shot expected game based on player 1 (resp., 2)'s payo¤ and let f N R (q) (resp., g N R (q)) be the value of 1;N R (q) (resp., 2;N R (q)), namely,

f N R (q) = min 2 (A 2 ) max 2 (A 1 ) X k2K q k U k ( ; ) ! (11) = max 2 (A 1 ) min 2 (A 2 ) X k2K q k U k ( ; ) ! g N R (q) = min 2 (A 1 ) max 2 (A 2 ) X k2K q k V k ( ; ) ! (12) = max 2 (A 2 ) min 2 (A 1 ) X k2K q k V k ( ; )

!

In both f N R and g N R , it is understood that player 1 does not make use of his information, i.e., chooses his strategy independently of his type.

Let p be any prior in the interior of (K); following Blackwell (1956) and Aumann andMaschler (1968, 1995), a vector payo¤ u = (u k ) k2K is individually rational for player 1 in B 1 (p) if and only if

8q 2 (K) q u f N R (q) (13)
where f N R is de…ned by [START_REF] Kalai | A commitment folk theorem[END_REF]. In other words, the latter condition is necessary and su¢ cient for player 2 to have a strategy 1 in B 1 (p) which guarantees that player 1's payo¤ in B 1 (p) does not exceed u k when his type is k, whatever the type k is. Similarly, a payo¤ v is individually rational for player 2 in

B 1 (p) if and only if v vexg N R (p) (14)
where vexg N R is the convexi…cation of g, i.e., the largest convex mapping that is below g N R over the simplex. In other words, ( 14) is necessary and su¢ cient for player 1 to have a (type dependent) strategy 1 in 1 (p) which guarantees that player 2's payo¤ in B 1 (p) does not exceed v.

Using the previous notions of individual rationality, we can give a fully precise de…nition: (S; ; ) is a joint plan equilibrium in B 1 (p) i¤ (S; ; ) satis…es the incentive compatibility conditions i) and ii) of section 2.1, with U k (x s ) U k ( (s)) for every k, s such that (s j k) > 0.

Player 1's interim expected payo¤ (u k ) k2K , which can be de…ned as in (1), namely, by u k = U k (x s ) for every k, s such that (s j k) > 0, is individually rational in the sense of (13).

Player 2's conditional expected payo¤ given s, namely, v s = P k p k s V k (x s ), where p s is the posterior probability distribution over K at s (computed from p and ), is individually rational in B 1 (p s ), in the sense of [START_REF] Peters | De…nable and contractible contracts[END_REF].

According to [START_REF] Simon | The existence of equilibria in certain games, separation for families of convex functions and a theorem of Borsuk-Ulam type[END_REF], for every p, there exists a joint plan equilibrium (S; ; ) in the in…nitely repeated game B 1 (p), which, by de…nition, is feasible (in particular, incentive compatible) in the one-shot game B(p). To complete the proof of the proposition, we still have to check that (S; ; ) is individually rational for both players in B(p).

For player 2, the result is immediate. By lemma 4, individidual rationality for player 2 in B(p) can be formulated in terms of the mapping g 1 (see [START_REF] Hart | Nonzero-sum two-person repeated games with incomplete information[END_REF]). By the de…nitions of g 1 and g N R , g 1 g N R and g 1 is convex. Hence, for player 2, individidual rationality in B 1 (p s ) implies individidual rationality in B(p s ), at every s.

Let us show that, thanks to UPS, (S; ; ) is also individually rational for player 1 in B(p). To see this, let be a uniform strategy of player 2; by the de…nition of f N R (namely, (11)),

f N R (q) max 2 (A 1 ) X k2K q k U k ( ; ) ! X k2K q k max 2 (A 1 ) U k ( ; ) X k2K q k u k .
This implies that under UPS, cavf N R (q) P k2K q k u k , where cavf N R is the concavi…cation of f N R , i.e., the smallest concave mapping that is above f N R over the simplex. On the other hand, recalling that k denotes the kth extreme point of (K),

cavf N R (q) = cavf N R X k2K q k k ! X k2K q k cavf N R ( k ) = X k2K q k f N R ( k ) = X k2K q k u k .
Hence, under UPS,

cavf N R (q) = X k2K q k u k 8q 2 (K)
and, using ( 13), u = (u k ) k2K is individually rational for player 1 in B 1 (p) i¤

u k u k 8k 2 K:
From lemma 9, under UPS, individual rationality for player 1 in the one-shot game B(p) reduces to the same condition.

The previous proof shows that when UPS holds, cavf N R is linear. 11 The latter property greatly simpli…es the study of in…nitely repeated games with lack of information on one side since it allows to dispense with Blackwell's approachability theorem in the de…nition of individual rationality for the informed player. However, another look at example 1 shows that the linearity of cavf N R is weaker than UPS and does not guarantee the existence of a solution in B(p).

Example 1 (continued): Recall that, in this example, f 1 (q) = min fq + 2(1 q); 2q + (1 q)g so that a vector payo¤ (u 1 ; u 2 ) is individually rational for player 1 in B( ) i¤ u 1 + u 2 3. Given player 2's payo¤s, there is no cooperative solution in B(p), 0 < p < 1. One computes that

f N R (p) = 1 p if p 1 3 = 3p(1 p) if 1 3 p 2 3 = p if p 2 3
Hence, cavf N R (p) = 1 for every p. In particular, cavf N R is linear, even if UPS is not satis…ed. For every p, B 1 (p) has a completely revealing equilibrium achieving the vector payo¤ (1; 1) for player 1. This example illustrates that when UPS does not hold, individual rationality for player 1 is weaker in B 1 ( ) than in B( ).

In the next example, UPS is veri…ed and a cooperative solution exists. However, for some values of the prior probability distribution over states, there does not exist any nonrevealing solution and there does not exist any completely revealing solution either. In particular, the revelation principle does not hold in our framework. In the partially revealing constructed solution, the informed player of type k just gets his individually rational level u k .

Example 2: Let K = f1; 2g, A 1 = fT; Bg, A 2 = fF L, L, C, R, F Rg. Player 1's payo¤ matrices are:

U 1 ( ) = F L L C R F R T 4 3 4 3 4 B 0 3 0 3 8 U 2 ( ) = F L L C R F R T 8 3 0 3 0 B 4 3 4 3 4
We check that u 1 = u 2 = 3 and that L and R are uniform punishment strategies of player 2. Player 2's payo¤s are exactly as in [START_REF] Forges | Equilibria with communication in a job market example[END_REF]; in particular, they depend on player 1's type but they do not depend on player 1's action:

V 1 ( ) = F L L C R F R T 10 9 7 4 0 B 10 9 7 4 0 V 2 ( ) = F L L C R F R T 0 4 7 9 10 B 0 4 7 9 10
Let us denote as p 2 [0; 1] the probability that k = 1. It is immediate that F R is optimal for 0 p so that cavf N R (p) = 3 for every p.

As another reference, the one-shot (noncooperative) Bayesian game has a Nash equilibrium in which player 1 chooses T when k = 1 and B when k = 2, while player 2 chooses C, which gives the payo¤s (4; 4) to player 1 and 7 to player 2. These payo¤s can be achieved by a centralized mechanism à la [START_REF] Myerson | Game theory: analysis of con ‡ict[END_REF], i.e., they are in M B( 12 ) (see section 2.4) but are not in C B( 12 ) because player 1 makes use of his private information without sharing it with player 2. We have seen that when UPS does not hold, C [B(p)] can be empty, while N JP [B 1 (p)] is still nonempty. The partial folk theorem property N JP [B 1 (p)] M [B(p)] can also fail when UPS is not satis…ed. This is illustrated in section 3.3: in example 1 (continued), B 1 (p) has a completely revealing equilibrium which is obviously individually rational for player 1 in B 1 (p) (namely, sat-is…es ( 13)) but is not interim individually rational for player 1 in B(p), in spite of the fact that player 2's approachability strategy is straightforward, cavf N R being linear.

Solutions when both players are privately informed

Let us extend the basic Bayesian game so that both player 1 and player 2 have private information. Let K and L be …nite sets. At a virtual initial stage of the game, player 1's type k is chosen in K according to p and, independently, player 2's type `is chosen in L according to q. Only player 1 (resp., 2) is informed of k (resp., `). Unless speci…ed otherwise, we assume that p k > 0 and that q `> 0 for every k 2 K, `2 L.

Player 1 and player 2 choose simultaneously an action in …nite sets A 1 and A 2 respectively. If the pair of actions a 2 A = A 1 A 2 is chosen, they get the respective payo¤s U k (a) and V `(a). Each player thus knows his own payo¤ (according to another terminology, "values are private"). We refer to this game as B(p; q). We will also assume that UPS holds for both players. Given the private values assumption, we can still de…ne player 1's type k individually rational level by u k , exactly as in [START_REF] Forges | Bayesian repeated games and reputation[END_REF], for every k 2 K, and we can de…ne player 2's type `individually rational level in the same way, by v `, for every `2 L.

Let S and T be sets of signals and let : S T ! (A). As in section 2.3, we can introduce a noncooperative game G(p; q; S; T; ) to be played as follows:

-Player 1's type k is chosen in K according to p, player 2's type `is chosen in L according to q, only player 1 (resp., 2) is informed of k (resp., `).

-Player 1 sends a signal s 2 S to player 2, and simultaneously, player 2 sends a signal t 2 T to player 1.

-The correlated strategy (s; t) = x st 2 (A) is proposed to both players.

and asks them whether they accept x or not; if they both accept, x is implemented; otherwise, they choose their actions themselves. By proceeding in the same way as to establish the revelation principle, it is a Nash equilibrium for both players to reveal their type and to accept the outcome proposed by the mediator. 12 We thus have, for player 1, X `2L q `X x (x j k; `)U k (x) X `2L q `X x (x j k 0 ; `) max U k (x); u k 8k; k 0 2 K (16) Let us set

x k`= X

x (x j k; `)x E (e x j k; `)

Then, recalling that U k is linear, the left hand side of ( 16) is P `2L q `U k (x k`) . By using that max is convex, and then again that U k is linear, the right hand side is larger than P `2L q `max U k ( P x (x j k 0 ; `)x); u k , hence ( 16) implies [START_REF] Renault | On two-player repeated games with lack of information on one side and state-dependent signalling[END_REF]. One can proceed similarly for player 2.

Equipped with the previous simple characterization of C [B(p; q)], we are going to check whether an analog of corollary 11 holds in the current model. [START_REF] Koren | Two-person repeated games where players know their own payo¤s[END_REF] already proposed a characterization like lemma 12 for the undiscounted in…nitely repeated version of B(p; q), which we denote as B 1 (p; q) and which can be de…ned in the same way as B 1 (p). Assuming private values but not UPS, [START_REF] Koren | Two-person repeated games where players know their own payo¤s[END_REF] showed that every Nash equilibrium of B 1 (p; q) is payo¤ equivalent to a completely revealing Nash equilibrium, so that it can in particular be achieved as a joint plan equilibrium.

Let N [B 1 (p; q)] be the set of all interim expected Nash equilibrium pay-o¤s of B 1 (p; q). De…ning N JP [B 1 (p; q)] in the same way as N JP [B 1 (p)] in section 3.3, we have here N [B 1 (p; q)] = N JP [B 1 (p; q)]. Forges and Salomon (2014) further show that, when UPS holds, N [B 1 (p; q)] is characterized by inequalities [START_REF] Renault | On two-player repeated games with lack of information on one side and state-dependent signalling[END_REF], i.e., that N [B 1 (p; q)] = C [B(p; q)]. 13The set M [B(p; q)] of all mediated interim indivually rational payo¤s when both players are informed can be de…ned as in section 2.4. A partial analog of corollary 11 is as follows:

Proposition 13 Let B(p; q) be a two-person Bayesian game with private values in which both players have a uniform punishment strategy. N [B 1 (p; q)] = C [B(p; q)] M [B(p; q)].

As corollary 11, the previous result can be interpreted as a folk theorem. However, there is an important di¤erence with the case of a single informed player: N [B 1 (p; q)] -and thus also C [B(p; q)] -can be empty. Koren (1992) provides a counter-example, which turns out to satisfy UPS (see [START_REF] Forges | Bayesian repeated games and reputation[END_REF] for further illustration).

Observe that the model in proposition 13 is both more general and more restrictive than the one of corollary 11. In proposition 13, there is lack of information on both sides but values are private, which was not necessarily true (for player 2) above, except in section 3.2.2. The next example illustrates that even if player 1 is the only one to have private information and player 2 knows his own payo¤ (as in section 3.2.2) the partial folk theorem N [B 1 (p; q)] M [B(p; q)] is not true without UPS. 14

Example 3

Let jA 1 j = jA 2 j = 2 and the utility functions be described by

U 1 ( ) = 1 0 0 0 U 2 ( ) = 0 0 0 1 V ( ) = 0 2 0 0
The assumption of uniform punishments is clearly not satis…ed: player 2 must play right in order to hold player 1 of type 1 at his value level u 1 = 0 and must play left to hold him at u 2 = 0. Recalling [START_REF] Kalai | A commitment folk theorem[END_REF], the value of player 1's expected one-shot game is

f N R (p) = val 1 p 0 0 1 p = p(1 p)

De…nition 5

 5 Let B(p) be a two-person Bayesian game with a single informed player. A (cooperative) solution (S; ; ) for B(p) consists of a set of signals S, a signalling strategy : K ! (S) for the informed player and of a joint decision function : S ! (A) such that is incentive compatible given , player 1's interim expected payo¤ is individually rational and for every signal s 2 S, player 2's payo¤ from (s) = x s is individually rational in B(p s ), where p s denotes player 2's posterior computed from p and . C [B(p)] R K R denotes the set of all interim expected payo¤s that can be achieved by a solution of B(p).

5 , L is optimal for 3 5 p 4 5 ,

 555 F L is optimal for4

1

 1 Further insights when a single player is informed Let us …rst summarize some properties that do not rely on UPS. In section 2, we have de…ned two sets of cooperative payo¤s in the Bayesian game B(p): the set C [B(p)] of unmediated, posterior individually rational pay-o¤s (de…nition 5) and the set M [B(p)] of mediated, interim individually rational payo¤s (de…nition 7). We have seen that C [B(p)] M [B(p)] and that this inclusion may be strict. Recalling the proof of proposition 10, let N JP [B 1 (p)] R K R be the set of all interim expected payo¤ that can be achieved in a joint plan equilibrium of B 1 (p). Simon et al. (1995)'s result can be stated as N JP [B 1 (p)] 6 = ;. When UPS is satis…ed, the …ndings of section 3.3 can be rephrased as follows: Corollary 11 Let B(p) be a two-person Bayesian game with a single informed player in which the uninformed player has a uniform punishment strategy. N JP [B 1 (p)] = C [B(p)] M [B(p)]. Furthermore, C [B(p)] is nonempty and may be strictly included in M [B(p)]. The strict inclusion of C [B(p)] in M [B(p)] under UPS is illustrated on example 2. Viewed as a result on N JP [B 1 (p)], the previous corollary can be interpreted as an extension of the folk theorem to games with incomplete information, since it makes a precise connection between a set of (noncooperative) equilibrium payo¤s of the in…nitely repeated game and sets of feasible individually rational payo¤s of the one-shot game. For the set C [B(p)] of unmediated feasible, posterior individually rational payo¤s, we have a full folk theorem, in the sense that N JP [B 1 (p)] coincides with C [B(p)]. For the set M [B(p)] of mediated feasible, interim individually rational payo¤s, we just have a partial folk theorem.

For any …nite set E, (E) denotes the set of probability distributions over E.

The word "solution" may look too strong and is just used for convenience. As will become clear below, we do not make a list of all properties that a solution should satisfy but concentrate on two of them.

The properties detailed below are well identi…ed in[START_REF] Sorin | A …rst course on zero-sum repeated games[END_REF].

The index 1 in f 1 ( ) is for "one-shot".

As for the informed player, the index 1 in g 1 ( ) is for "one-shot".

This just shows that player 2's decision strategy in case of rejection does not have to depend on the signal s.

As soon as there is a mediator, the revelation principle applies and without loss of generality, player 1's possible signals are just his possible types.

Nonemptiness of M [B(p)] can also be checked directly, since a mediated solution is de…ned by linear inequalities. Myerson starts by de…ning M [B(p)] but goes on by imposing further requirements on cooperative solutions.

UPS guarantees the existence of an equilibrium of the form described in lemma 6 but does not ensure that this equilibrium be Bayesian perfect. To see this, it su¢ ces to modify example 1 by giving player 2 an additional action whose payo¤ is always negative for both players. Player 2 has then a strictly dominated uniform punishment strategy. Eliminating it recreates the non-existence problem.

In the context of B 1 (p), a correlated strategy in (A) is interpreted as a limit frequency of moves.

More precisely, recalling the de…nition of the concave mapping f 1 (i.e., (4)) and lemma 9, under UPS, cavf N R (q) = f 1 (q) = P k2K q k u k .

p 1.

Since values are private and utility functions are linear, a player only cares about his own type and the expected distribution over actions.

[START_REF] Koren | Two-person repeated games where players know their own payo¤s[END_REF]'s characterization is more complex in that it makes use of Blackwell's approachability, i.e., individual rationality is de…ned as in[START_REF] Myerson | Game theory: analysis of con ‡ict[END_REF].

The undiscounted in…nitely repeated version of the model of section 3.2.2. (namely, lack of information on one side and private values) was studied by[START_REF] Shalev | Nonzero-sum two-person repeated games with incomplete information and known-own payo¤s[END_REF]. He showed that all Nash equilibria are payo¤ equivalent to completely revealing ones (the result that was extended by[START_REF] Koren | Two-person repeated games where players know their own payo¤s[END_REF]) and that Nash equilibria always exist (the reasoning in section 3.2.2 is similar to Shalev (1994)'s one).

Let p = 1 2 . Let us …rst show that there is no nonrevealing solution. A nonrevealing solution consists of x 2 (A) such that U 1 (x) 3, U 2 (x) 3

2 ) = 7. The latter condition implies that player 2 must take the action C, namely that x = 0 0 0 0 0 0 1 0 0 for some 0 1

3 ) 1 4 so that there is indeed no nonrevealing solution.

Let us show next that there is no completely revealing solution at p = 1 2 . A completely revealing solution is described by x k 2 (A), k = 1; 2, x k being interpreted as the joint decision when player 1 reports type k. Individual rationality for player 2 means that V 1 (x 1 ) g 1 (1), i.e., player 2 chooses F L when he gets signal 1 and similarly, V 2 (x 2 ) g 1 (0), i.e., player 2 chooses F R when he gets signal 2.

x 1 = 0 0 0 0 1 0 0 0 0 for some 0 1

x 2 = 0 0 0 0 1 0 0 0 0 for some 0 1

Individual rationality for player 1 means that U k (x k ) 3, k = 1; 2, i.e., U 1 (x 1 ) = 4 with . Incentive compatibility for player 1 means that U 1 (x 1 ) U 1 (x 2 ) and U 2 (x 2 ) U 2 (x 1 ) , 4 4( 1) + 8 and 4 8 + 4(1 ) , 1 + and 1 + , which is of course impossible.

Let us show that there exists a partially revealing solution at p = 1 2 . Let player 1 send signals r and s so as to reach the posteriors p r = 1 4 and p s = 3 4 . In order to satisfy player 2's individual rationality condition, we must have that x r gives probability 1 to R and that x s gives probability 1 to L. Incentive compatibility is trivially satis…ed since player 1 gets 3 no matter what. The payo¤s at this partially revealing solution are (3; 3) for player 1 (i.e., just his individual rationality level) and 31 4 for player 2. To complete the analysis,

-The players simultaneously accept or reject the correlated strategy x st .

-If both players accept x st , player 1 gets U k (x st ) and player 2 gets V `(x st ).

-If at least one of the players rejects x st , player 1 chooses a 1 , player 2 chooses a 2 , player 1 gets U k (a 1 ; a 2 ) and player 2 gets V `(a 1 ; a 2 ).

Let

: K ! (S) be a signalling strategy for player 1 and let : L ! (T ) be a signalling strategy for player 2. By proceeding as in section 2.3, we say that (S; T; ; ; ) de…nes a solution for B(p; q) if and only if G(p; q; S; T; ) has an equilibrium in which player 1 sends his signal according to , player 2 sends his signal according to and both players always accept the correlated strategy that is proposed to them.

Let us further say that (S; T; ; ; ) de…nes a completely revealing (cooperative) solution if S = K, T = L, (resp., ) is the identity over K (resp., L). A completely revealing solution is thus just described by x k`2 (A) for every (k; `) 2 K L. It can be checked that (x k`)(k;`)2K L de…nes a completely revealing solution if and only if the following inequalities hold

Let C [B(p; q)] R K R L be the set of all interim payo¤s that can be achieved at a solution of B(p; q). The next lemma states that all payo¤s

for some (x k`)(k;`)2K L satisfying inequalities [START_REF] Renault | On two-player repeated games with lack of information on one side and state-dependent signalling[END_REF].

Lemma 12 Let B(p; q) be a two-person Bayesian game with private values in which both players have a uniform punishment strategy. Every solution for B(p; q) is payo¤ equivalent to a completely revealing solution.

Proof: Let (S; T; ; ; ) be a solution for B(p; q). Let us consider the variant of G(p; q; S; T; ) in which both players are invited to reveal their types to a mediator who selects x 2 (A) according to the probability distribution

The probability distribution

de…nes a nonrevealing equilibrium of B 1 (q), for every p 2 (0; 1). Indeed, player 1's associated vector payo¤ (u 1 ; u 2 ) = ( 1 4 ; 1 4 ) satis…es the individual rationality condition (13) and player 2's payo¤ v = 1 is individually rational since the value of player 2's game is v = 0. Hence (( The example also allows us to recall that conditions [START_REF] Renault | On two-player repeated games with lack of information on one side and state-dependent signalling[END_REF] are not meaningful when UPS does not hold. The probability distribution x 1 = x 2 = x = 0 1 0 0 satis…es (15) but the vector payo¤ of player 1 is (0; 0) and is not individually rational for player 1 (not only in the interim sense but even in B 1 (p)).


Diego F Aranha
email: dfaranha@ic.unicamp.br

Pierre-Alain Fouque
email: fouque@irisa.fr

Chen Qian
email: chen.qian@ens-rennes.fr

Mehdi Tibouchi
email: tibouchi.mehdi@lab.ntt.co.jp

Jean-Christophe Zapalowicz
email: jean-christophe.zapalowicz@inria.fr

Binary Elligator Squared

Keywords: Elligator, Binary Elliptic Curves, Efficient Implementation, PCLMULQDQ, Anonymity & Privacy

Applications of elliptic curve cryptography to anonymity, privacy and censorship circumvention call for methods to represent uniformly random points on elliptic curves as uniformly random bit strings, so that, for example, ECC network traffic can masquerade as random traffic.

At ACM CCS 2013, Bernstein et al. proposed an efficient approach, called "Elligator," to solving this problem for arbitrary elliptic curve-based cryptographic protocols, based on the use of efficiently invertible maps to elliptic curves. Unfortunately, such invertible maps are only known to exist for certain classes of curves, excluding in particular curves of prime order and curves over binary fields. A variant of this approach, "Elligator Squared," was later proposed by Tibouchi (FC 2014) supporting not necessarily injective encodings to elliptic curves (and hence a much larger class of curves), but, although some rough efficiency estimates were provided, it was not clear how an actual implementation of that approach would perform in practice.

In this paper, we show that Elligator Squared can indeed be implemented very efficiently with a suitable choice of curve encodings. More precisely, we consider the binary curve setting (which was not discussed in Tibouchi's paper), and implement the Elligator Squared bit string representation algorithm based on a suitably optimized version of the Shallue-van de Woestijne characteristic 2 encoding, which we show can be computed using only multiplications, trace and half-trace computations, and a few inversions.

On the fast binary curve of Oliveira et al. (CHES 2013), our implementation runs in an average of only 22850 Haswell cycles, making uniform bit string representations possible for a very reasonable overhead-much smaller even than Elligator on Edwards curves.

As a side contribution, we also compare implementations of Elligator and Elligator Squared on a curve supported by Elligator, namely Curve25519. We find that generating a random point and its uniform bitstring representation is around 35-40% faster with Elligator for protocols using a fixed base point (such as static ECDH), but 30-35% faster with Elligator Squared in the case of a variable base point (such as ElGamal encryption). Both are significantly slower than our binary curve implementation.

Introduction

Elliptic curves offer many advantages for public-key cryptography compared to more traditional settings like RSA and finite field discrete logarithms, including higher efficiency, a much smaller key size that scales gracefully with security requirements, and a rich geometric structure that enables the construction of additional primitives like bilinear pairings. On the Internet, adoption of elliptic curve cryptography is growing in generalpurpose protocols like TLS, SSH and S/MIME, as well as anonymity and privacy-enhancing tools like Tor (which favors ECDH key exchange in recent versions) and Bitcoin (which is based on ECDSA).

For circumvention applications, however, ECC presents a weakness: points on a given elliptic curve, when represented in a usual way (even in compressed form) are easy to distinguish from random bit strings. For example, the usual compressed bit string representation of an elliptic curve point is essentially the x-coordinate of the point, and only about half of all possible x-coordinates correspond to valid points (the other half being x-coordinates of points of the quadratic twist). This makes it relatively easy for an attacker to distinguish ECC traffic (the transcripts of multiple ECDH key exchanges, say) from random traffic, and then proceed to intercept, block or otherwise tamper with such traffic.

To alleviate that problem, one possible approach is to modify protocols so that transmitted points randomly lie either on the given elliptic curve or on its quadratic twist (and the curve parameters must therefore be chosen to be twist-secure). This is the approach taken by Möller [START_REF] Möller | A public-key encryption scheme with pseudo-random ciphertexts[END_REF], who constructed a CCA-secure KEM with uniformly random ciphertexts using an elliptic curve and its twist. This approach has also been used in the context of kleptography, as considered by Young and Yung [START_REF] Young | Space-efficient kleptography without random oracles[END_REF][START_REF] Young | Kleptography from standard assumptions and applications[END_REF], and has already been deployed in circumvention tools, including StegoTorus [START_REF] Weinberg | StegoTorus: a camouflage proxy for the Tor anonymity system[END_REF], a camouflage proxy for Tor, and Telex [START_REF] Wustrow | Telex: Anticensorship in the network infrastructure[END_REF], an anticensorship technology that uses a covert channel in TLS handshakes to securely communicate with friendly proxy servers. However, since protocols and security proofs have to be adapted to work on both a curve and its twist, this approach is not particularly versatile, and it imposes additional security requirements (twist-security) on the choice of curve parameters.

A different approach, called "Elligator," was presented at ACM CCS 2013 by Bernstein, Hamburg, Krasnova and Lange [START_REF] Daniel | Elligator: Elliptic-curve points indistinguishable from uniform random strings[END_REF]. Their idea is to leverage an efficiently computable, efficiently invertible algebraic function that maps the integer interval S = {0, . . . , (p -1)/2}, p prime, injectively to the group E(F p ) where E is an elliptic curve over F p . Bernstein et al. observe that, since ι is injective, a uniformly random point P in ι(S) ⊂ E(F p ) has a uniformly random preimage ι -1 (P ) in S, and use that observation to represent an elliptic curve point P as the bit string representation of the unique integer ι -1 (P ) if it exists. If the prime p is close to a power of 2, a uniform point in ι(S) will have a close to uniform bit string representation.

This method has numerous advantages over Möller's twisted curve method: it is easier to adapt to existing protocols using elliptic curves, since there is no need to modify them to also deal with the quadratic twist; it avoids the need to publish a twisted curve counterpart of each public key element, hence allowing a more compact public key; and it doesn't impose additional security requirements like twist-security. But it crucially relies on the existence of an injective encoding ι, only a few examples of which are known [START_REF] Rezaeian | Hashing into Hessian curves[END_REF][START_REF] Fouque | Injective encodings to elliptic curves[END_REF][START_REF] Daniel | Elligator: Elliptic-curve points indistinguishable from uniform random strings[END_REF], all of them for elliptic curves of non-prime order over large characteristic fields. This makes the method inapplicable to implementations based on curves of prime order or on binary fields, which rules out most standardized ECC parameters [15,[START_REF]SEC 2: Recommended elliptic curve domain parameters[END_REF][START_REF] Lochter | Elliptic curve cryptography (ECC) Brainpool standard curves and curve generation[END_REF][START_REF] Anssi | Publication d'un paramétrage de courbe elliptique visant des applications de passeport électronique et de l'administration électronique franc ¸aise[END_REF], in particular. Moreover, the rejection sampling involved (when a point P is picked outside ι(S), the protocol has to start over) can impose a significant performance penalty.

To overcome these limitations, Tibouchi [START_REF] Tibouchi | Elligator Squared: Uniform points on elliptic curves of prime order as uniform random strings[END_REF] recently proposed a variant of Elligator, called "Elligator Squared," in which a point P ∈ E(F q ) is represented not by a preimage under an injective encoding ι, but by a randomly sampled preimage under an essentially surjective map F 2 q → E(F q ) with good statistical properties, known as an admissible encoding following a terminology introduced by Brier et al. [START_REF] Brier | Efficient indifferentiable hashing into ordinary elliptic curves[END_REF]. By results due to Farashahi et al. [START_REF] Rezaeian Farashahi | Indifferentiable deterministic hashing to elliptic and hyperelliptic curves[END_REF], such admissible encodings are known to exist for all isomorphism classes of elliptic curves, including curves of prime order and binary curves. Since admissible encodings are essentially surjective, the approach also eliminates the need for rejection sampling at the protocol level.

Our contributions. While the Elligator Squared approach is quite versatile, its efficiency is highly dependent on how fast the underlying admissible encoding can be computed and sampled, and the same can be said of Elligator in the settings were it can be used. Since, to the best of our knowledge, no detailed implementation results or concrete performance numbers have been published so far for the underlying encodings, one only has some rough estimates to go by. For Elligator, Bernstein et al. give ballpark Westmere cycle count figures based on earlier implementation results [START_REF] Daniel | Elligator: Software[END_REF], and for Elligator Squared, Tibouchi provides some average operation counts in [START_REF] Tibouchi | Elligator Squared: Uniform points on elliptic curves of prime order as uniform random strings[END_REF] for a few selected encoding functions. No performance-oriented implementation is available for either approach.

In this paper, we provide the first such implementation for Elligator Squared, and do so in the binary curve setting, which had not been considered by Tibouchi. Binary curves provide a major advantage for algorithms like Elligator Squared due to the existence of a point encoding function, the binary Shallue-van de Woestijne encoding [START_REF] Shallue | Construction of rational points on elliptic curves over finite fields[END_REF], that can be computed without base field exponentiations. Using the framework of Farashahi et al. [START_REF] Rezaeian Farashahi | Indifferentiable deterministic hashing to elliptic and hyperelliptic curves[END_REF], one can obtain an admissible encoding from that function, and hence use it to implement Elligator Squared.

We propose various algorithmic improvements and computation tricks to obtain a fast evaluation of the binary Shallue-van de Woestijne encoding and of the associated Elligator Squared sampling algorithm. In particular, our description is much more efficient than the one given in [START_REF] Brier | Efficient indifferentiable hashing into ordinary elliptic curves[END_REF]Appendix E].

Based on these algorithmic improvements, we performed software implementations of Elligator Squared on the record-setting binary GLS curve of Oliveira et al. , defined over F 2 254 [START_REF] Oliveira | Two is the fastest prime: lambda coordinates for binary elliptic curves[END_REF]. We dedicate special attention to optimizing the performance-critical operations and introduce corresponding novel techniques, namely a new point addition formula in λ-affine coordinates and a faster approach for constant-time half-trace computation over quadratic extensions of F 2 m . Moreover, timings are presented for both variable-time and constant-time field arithmetic. 6 The resulting timings compare very favorably to previously suggested estimates.

Finally, as a side contribution, we also propose concrete cycle counts on Ivy Bridge and Haswell for both Elligator and Elligator Squared on the Edwards curve Curve25519 [START_REF] Daniel | Curve25519: New Diffie-Hellman speed records[END_REF] based on the publicly available implementation of Ed25519 [START_REF] Daniel | High-speed high-security signatures[END_REF]. We find that, on this curve, the Elligator approach is roughly 35-40% faster than Elligator Squared for protocols that rely on fixed-base scalar multiplication, such as ECDH, but conversely, for protocols that rely on variable-base scalar multiplication like ElGamal encryption, Elligator Squared is 30-35% faster. Both approaches are significantly slower than what we achieve on the same CPU with our binary curve implementation.

Preliminaries

Let E be an elliptic curve over a finite field F q .

2.1 Well-bounded encodings Definition 1. A function f : F q → E(F q ) is said to be B-well-distributed encoding for a certain constant B > 0 if for any nontrivial character χ of E(F q ), the following holds:

u∈Fq χ(f (u)) ≤ B √ q.
Definition 2. We call a function f : F q → E(F q ) a (d, B)-well-bounded encoding, for positive constants d, B, when f is B-well-distributed and all points in E(F q ) have at most d preimages under f .

Elligator Squared

Let f : F q → E(F q ) be a (d, B)-well-bounded encoding and let f ⊗2 the tensor square defined by:

f ⊗2 : F 2 q → E(F q ) (u, v) → f (u) + f (v).
Tibouchi shows in [START_REF] Tibouchi | Elligator Squared: Uniform points on elliptic curves of prime order as uniform random strings[END_REF] that if we sample a uniformly random preimage under f ⊗2 of a uniformly random point P on the curve, we get a pair (u, v) ∈ F 2 q which is statistically close to uniform. Moreover he proves that sampling uniformly random preimages under f ⊗2 can be done efficiently for all points P ∈ E(F q ) except possibly a negligible fraction of them [START_REF] Tibouchi | Elligator Squared: Uniform points on elliptic curves of prime order as uniform random strings[END_REF]Theorem 1]. The sampling algorithm Tibouchi proposed is described as Algorithm 1. The idea is to randomly pick a random u and then to compute a correct candidate v such that P = f (u) + f (v). The last steps of the algorithm (step 5 to 7) are also needed in order to ensure the uniform distribution of the output (u, v).

Algorithm 1 Preimage sampling algorithm for f ⊗2 . 1: function SAMPLEPREIMAGE(P ) 2: repeat

3: u $ ← Fq 4: Q ← P -f (u) 5: i ← #f -1 (Q) 6: j $ ← {1, • • • , d} 7: until j ≤ i 8: {v1, • • • , vt} ← f -1 (Q) 9:
return (u, vj) 10: end function

Shallue-van de Woestijne in Characteristic 2

In this section, we recall the Shallue-van de Woestijne algorithm in characteristic 2 [START_REF] Shallue | Construction of rational points on elliptic curves over finite fields[END_REF], following the more explicit presentation given in [START_REF] Brier | Efficient indifferentiable hashing into ordinary elliptic curves[END_REF]Appendix E]. An elliptic curve over a field F 2 n is a set of points (x, y) ∈ (F 2 n ) 2 verifying the equation:

E a,b : Y 2 + X • Y = X 3 + a • X 2 + b where a, b ∈ (F 2 n ) 2 . Let g be the rational function x → x -2 • (x 3 + a • x 2 + b). Letting Z = Y /X, the equation for E a,b can be rewritten as Z 2 + Z = g(X). Theorem 1. Let g(x) = x -2 • (x 3 + a • x 2 + b) where a, b ∈ (F 2 n ) 2 . Let X 1 (t, w) = t • c 1 + t + t 2 X 2 (t, w) = t • X 1 (t, w) + c X 3 (t, w) = X 1 (t, w) • X 2 (t, w) X 1 (t, w) + X 2 (t, w) where c = a + w + w 2 . Then g(X 1 (t, w)) + g(X 2 (t, w)) + g(X 3 (t, w)) ∈ h(F 2 n ) where h is the map h : z → z 2 + z.
From Theorem 1, we have that at least one of the g(X i (t, w)) must be in h(

F 2 n ), which leads to a point in E a,b (F 2 n ). Indeed, we have that h(F 2 n ) = {z ∈ F 2 n | Tr(z) = 0}
, where Tr is the trace operator Tr : F 2 n → F 2 with:

Tr = n-1 i=0 z 2 i
(one inclusion is obvious and the other one follows from the fact that the kernel of the F 2 -linear map h is {0, 1}, hence its image is a hyperplane). As a result, 3 i=1 Tr(g(X i )) = 0 and therefore at least one of the X i must satisfy Tr(g

(X i )) = 0 since Tr is F 2 -valued. Such an X i is indeed the abscissa of a point in E a,b (F 2 n
), and we can find its y-coordinate by solving the quadratic equation Z 2 + Z = g(X i ). That equation is F 2 -linear, so finding Z amounts to solving a linear system over F 2 . This yields the point-encoding function described in Algorithm 2.

In the description of that algorithm, the solution of the quadratic equation is expressed in terms of the map QS : F 2 n → F 2 n ("quadratic solver"), which is the well-defined linear map such that, for all x, QS(x) is the trace zero solution of the quadratic equation z 2 + z = x + Tr(x). When n is odd, QS is straightforward to compute: it is the half-trace map HTr defined as:

HTr : z → (n-1)/2 i=0 z 2 2i .
Algorithm 2 Shallue-van de Woestijne algorithm in characteristic 2.

Require: a, b ∈ F2n and t, w ∈ F2n Ensure:

(x, y) ∈ E a,b 1: c ← a + w + w 2 2: X1 ← t • c/(1 + t + t 2 ) 3: X2 ← t • X1 + c 4: X3 ← X1 • X2/(X1 + X2) 5: for j = 1 to 3 do 6: hj ← (X 3 j + a • X 2 j + b)/X 2 j 7:
if Tr(hj) = 0 then return (Xj, QS(hj) • Xj) 8:

end if 9: end for We discuss the efficient computation of QS in even degree extensions in §4.

Algorithm 2 actually maps two parameters t, w to a rational point on the curve E a,b . One can obtain a map f : F q → E a,b (F q ) by picking one of the two parameters as a suitable constant and letting the other one vary. In what follows, for efficiency reasons, we fix t and use w as the variable parameter.

One can check that the resulting function is well-bounded in the sense of §2.1. Indeed, the framework of Farashahi et al. [START_REF] Rezaeian Farashahi | Indifferentiable deterministic hashing to elliptic and hyperelliptic curves[END_REF] can be used to establish that it is a well-distributed encoding: the proof is easily adapted from the one given in [START_REF] Fouque | Indifferentiable hashing to Barreto-Naehrig curves[END_REF] for the positive characteristic version of the Shallue-van de Woestijne algorithm. Moreover, each curve point has at most 6 preimages under the corresponding function: there are at most two values of w that yield a given value of X 1 , and similarly for X 2 , X 3 . Thus, we obtain a (d, B)-well-bounded encoding for an explicitly computable constant B and d = 6.

Lambda affine coordinates

In order to have more efficient binary elliptic curve arithmetic, we will use lambda coordinates [START_REF] Oliveira | Two is the fastest prime: lambda coordinates for binary elliptic curves[END_REF]. Given a point P = (x, y) ∈ E a,b (F 2 n ), with x = 0, its λ-affine representation of P is defined as (x, λ) where λ = x + y/x. The λ-affine equation of the Weierstrass Equation of the curve y 2 + xy = x 3 + ax 2 + b is (λ 2 + λ + a)x 2 = x 4 + b. Note that the condition x = 0 is not restrictive in practice since the only point x = 0 satisfying Weierstrass equation is (0, √ b).

Algorithmic aspects

We focus on Algorithm 1 proposed by Tibouchi in [START_REF] Tibouchi | Elligator Squared: Uniform points on elliptic curves of prime order as uniform random strings[END_REF], which we adapt for the specific characteristic 2 finite field. More precisely, we consider an elliptic curve over a field F 2 n that satisfies the equation in λ-coordinates:

E a,b : (λ 2 + λ + a)X 2 = X 4 + b where a, b ∈ (F 2 n ) 2 .
The (6, B)-well-bounded encoding we consider for our efficient Elligator Squared implementation is the binary Shallue-van de Woestijne algorithm recalled in §2.3.

One of its properties is that among three candidates denoted X 1 , X 2 , X 3 , either exactly one of them or all three are x-coordinate of a rational point over the binary elliptic curve E a,b , and the algorithm outputs the first correct one. Owing to this property, some additionnal verifications during preimage computation, since it is not always true that SWCHAR2 X (SWCHAR2 -1 X (X i )) = X i for i = 2, 3, where we denote by SWCHAR2 X the x-coordinate of the binary Shallue-van de Woestijne algorithm, and by SWCHAR2 -1 X an arbitrary preimage thereof (see the discussion on the subroutine PREIMAGESSW in §3.3 for more details). We also have to consider another property of this algorithm, concerning the output. Indeed the y-coordinate has a specific form and thus, before searching for some preimages of the point Q, one has to test whether this property is verified (see the discussion on the overall complexity in §3.3 for more details).

The details of our preimage sampling algorithm in characteristic 2 are described in Algorithm 3 with t fixed to a constant such that t(t + 1)(t 2 + t + 1) = 0, i.e. t ∈ F 4 . Note that we make the choice to use the λ-coordinates for efficiency reasons justified in §3.2. The rest of the section consists in describing the two subroutines SWCHAR2 and PREIMAGESSW, as well as in evaluating the overall complexity of Algorithm 3.

The subroutine SWCHAR2

The first subroutine represents the binary Shallue-van de Woestijne algorithm and its pseudocode for our case is given as Algorithm 4. Given a value u ∈ F 2 n , it outputs the lambda coordinates of a point over the binary elliptic curve E a,b .

Since the field inversion is by far the most expensive field operation (see [START_REF] Oliveira | Two is the fastest prime: lambda coordinates for binary elliptic curves[END_REF] for experimental timings and Table 2 below), we have modified Algorithm 2 so that we have a single inversion of c to perform. Indeed Algorithm 2 requires at most 4 field inversions: the first one at step 4 and the three others at step 6. However the parameters X i and 1/X i for j = 1, 2, 3 can be expressed using c, 1/c and some constants depending on t which can be precomputed (see Table 1). Note that X 3 can be computed as c • t 3 , or more efficiently as X 1 + X 2 + c but this requires to keep in memory X 1 and X 2 . Finally this algorithm requires a single field inversion, a QS computation and some negligible field operations (multiplications, squarings and trace computations).

X1 ← t1 • c 1/X1 ← 1/t1 • 1/c X2 ← t2 • c 1/X2 ← 1/t2 • 1/c X3 ← X1 + X2 + c 1/X3 ← 1/t3 • 1/c Table 1. Efficient computation of values Xi and 1/Xi for i = 1, • • • 3. The values t1 = t 1+t+t 2 , 1/t1, t2 = 1+t
1+t+t 2 , 1/t2 and 1/t3 = 1+t+t 2 t(1+t) can be precomputed, with t a constant such that t ∈ F4.

The subroutine PREIMAGESSW

The second subroutine is useful to compute the number of preimages of the point Q = (x Q , λ Q ) by Algorithm 4. Its pseudocode is detailed as Algorithm 5 and refers to the steps 5 and 8 of Algorithm 1. This subroutine is more complex due to the properties of the binary Shallue-van de Woestijne algorithm. More precisely, there is an order relation in Algorithm 4: if X 1 corresponds to a x-coordinate of a point over R ← SWCHAR2(E a,b , u, t1, t2, t3) 7:

Algorithm 3 Preimage Sampling Algorithm in Characteristic 2 1: Precomputed: t1 = t 1+t+t 2 , t2 = 1+t 1+t+t 2 , t3 = t(1+t)
Q ← P -R 8: until Tr(λQ -xQ) = 0 9: k, S = {v1, • • • , v k } ← PREIMAGESSW(E a,b , Q, t1, t2, t3) 10: j $ ← {1, • • • , 6} 11: until j ≤ k 12:
return (u, vj) 13: end function Algorithm 4 Efficient Binary Shallue-van de Woestijne Algorithm

1: function SWCHAR2(E a,b , u, t1, t2, t3) 2: c ← u 2 + u + a 3: c-1 ← 1/c 4:
for j = 1 to 3 do ⊲ Compute hj and perform a trace test 5:

Xj ← tj • c ⊲ or X3 ← X1 + X2 + c 6:
X-j ← 1/tj • c-1 ⊲ 1/tj can also be precomputed 7:

hj ← (X-j) 2 • b + Xj + a 8:

if Tr(hj) = 0 then ⊲ At least one of the three potential tests will succeed 9:

x ← Xj 10:

λ ← QS(hj) + x 11:

break ⊲ Only take into account the first correct solution 12:

end if 13:

end for 14:

return (x, λ) ⊲ Lambda coordinates of a point over E a,b 15: end function the elliptic curve, then it will output this point, even if X 2 and X 3 also correspond to a possible x-coordinate. Thus, the equality SWCHAR2(SWCHAR2 -1 (X j )) = X j is true for j = 1 but not necessarly for j = 2, 3. In others words, for j = 2, 3 a solution of SWCHAR2 -1 (X j ) is not necessarily a preimage of X j by SWCHAR2.

Starting from the equations x Q = X j (t, w) = c(w) • t j for j = 1, 2, 3, with c(w) = w 2 + w + a, the main idea of Algorithm 5 consists in testing if there exists some values of w which satisfy these equations. If one founds some candidates for w, one also has to verify if they really correspond to preimages by Algorithm 4. From an equation x Q = X j (t, w) we can obtain an equation w + w 2 = x Q /t j -a = α j (a, t) which has 2 solutions if Tr(α j (a, t)) = 0 and no solution otherwise. As an example α 1 (a, t) is equal to

x Q • (1 + t + t 2 )/t -a.
The solutions are then w 1 0 = QS(α j (a, t)) and w 1 1 = w 1 0 + 1. There are thus at most 6 possible solutions for all values of j. Now for the cases x Q = X 2 (t, w) and x Q = X 3 (t, w), it remains to perform a verification. Actually, denoting w 2 0 one of both solutions of the equation x Q = X 2 (t, w) if it exists, the computation of SWCHAR2(w 2 0 ) can result in X 1 (t, w 2 0 ) instead of X 2 (t, w 2 0 ), and this happens with probability 1/2 which is the probability that Tr(h 1 ) = 0. The same result holds for x Q = X 3 (t, w), however note that if X 3 is solution but not X 1 then X 2 cannot be a solution since 3 i=1 Tr(g(X i )) = 0 according to Theorem 1. Thus the verification can focus only on X 1 .

Naive implementation of the verification.

A simple way for implementing the verification would consist in computing QS(α j (a, t)) for j = 2, 3 and then calling twice the subroutine SWCHAR2 (without the steps referring to X 2 and X 3 ) for testing if the test on the trace is true or not. However this would require an additional inversion per call to compute SWCHAR2. Moreover, with this naive implementation we have to compute the half trace before testing if the result will be a preimage.

Efficient implementation of the verification.

Since the verification focus only on X 1 as explained above, we propose an efficient way to compute b/X 2 1 , which is required in order to performing the test Tr(h 1 ) = Tr(X 1 + a + b/X 2 1 ), without any field inversion. This trick is valuable when we are working in lambda coordinates. Our proposal has another advantage: we do not need to compute the solutions, i.e. w 0 = QS(α j (a, t)) and w 1 = w 0 + 1, before to be sure that we will get two preimages. We thus save some quite expensive half trace computations.

Consider the equation:

x Q = X 2 = t 2 • c = t 2 • X 1 /t 1 with c = QS(α 2 (a, t)) 2 + QS(α 2 (a, t)) + a.
X 1 can be expressed as t 1 /t 2 • x Q , whose computation is negligible for t 1 /t 2 a precomputed value. Now starting from the equation of the elliptic curve in affine coordinates, i.e E a,b : for j = 1 to 3 do ⊲ From xQ = Xj(t, w)...

Y 2 + X • Y = X 3 + a • X 2 + b,
5: αj ← xQ • 1/tj -a 6:
if Tr(αj) = 0 then ⊲ ...Test if there are some solutions 7:

if j = 1 then ⊲ For X1, a solution is a preimage 8:

w0 ← QS(αj) 9:

w1 ← w0 + 1 10:

k ← 2 11:

S ← {w0, w1} 12:

else ⊲ For X2, X3, a solution is not necessarly a preimage 13: end for 25:

X1 ← t1/tj • xQ 14: tmp ← [(λQ -xQ) 2 + (λQ -xQ) -xQ -a] • (tj/t1) 2 ⊲ tmp = b/X
return k, S ⊲ k: number of preimages, S: set of preimages 26: end function we divide each term by X 2 and we evaluate the equation in the point Q. We then obtain:

y Q x Q 2 + y Q x Q = x Q + a + b x 2 Q , and finally: b X 2 1 = t 2 t 1 2 • y Q x Q 2 + y Q x Q -x Q -a .
Assuming that (t 2 /t 1 ) 2 is a precomputed constant, the computation of b/X 2 1 is not costly if y Q /x Q does not require an expensive operation. That is the case when we are working in λ-coordinates since λ Q = y Q /x Q + x Q . The same result obviously holds for the equation x Q = X 3 by replacing t 2 with t 3 .

To conclude, Algorithm 5 requires at most 3 QS computations and some negligible field operations (multiplications, squarings and trace computations).

Operation counts

We conclude this section by evaluating the average number of operations needed to evaluate Algorithm 3. Proposition 1. An evaluation of Algorithm 3 on a uniformly random curve points requires, on average and up to O(2 -n/2 ) variations, 6 field inversions, 6 point additions, 9 quadratic solver computations and some negligible operations such as field multiplications, field squares and trace computations.

Proof. The proof consists in evaluating the probability for exiting the two loops. First note that the output (x, λ) of Algorithm 4 has a specific property, namely λ -x is in the image of QS. Since we want to retrieve the preimages of a point Q, we have to be sure that λ Q -x Q is indeed in that image, which we test for by verifying whether Tr(λ Q -x Q ) = 0. Indeed, all elements of the form QS(z) have zero trace by definition, and the converse is true for reasons of dimensions. The success probability of this test is exactly 1/2 since Q is a uniformly random curve point. We thus have on average 2 field inversions, 2 point additions and 2 quadratic solver computations for the internal loop (steps 4 to 8).

The complexity of the external loop demands to evaluate the probabilities for having 0, 2, 4 or 6 preimages of Q. Since all tests on the trace in Algorithm 5 succeed, independently, with probability 1/2 up to O(2 -n/2 ) variations 7 , these probabilities are then, again up to O(2 -n/2 ) variations, 9/32 for 0 preimage, 15/32 for 2 preimages, 7/32 for 4 preimages, and 1/32 for 6 preimages. the probability for exiting the external loop is equal to 0 • 9/32 + 1/3 • 15/32 + 2/3 • 7/32 + 1 • 1/32 = 1/3. These probabilities also hold for evaluating the average cost of an iteration of PREIMAGESSW in term of quadratic computations. With probability 15/32 one such computation will be performed and so on. As a consequence, one iteration of PREIMAGESSW cost on average 15•1+7•2+1•3 32 = 1 quadratic solver computation. To sum up, Algorithm 3 requires on average 3 • 2 field inversions, 3 • 2 additions of points and 3 • (2 + 1) quadratic solver computations, up to O(2 -n/2 variations.

⊓ ⊔

Note that the efficiency of this algorithm can be improved further by choosing a sparse value of b and a value of t that yields sparse precomputed constants. Many of the field multiplications will then be computed faster.

Implementation aspects

Our software implementation targets modern Intel Desktop-based processors, making extensive use of the recently introduced AVX instruction set [START_REF] Firasta | Intel AVX: New frontiers in performance improvement and energy efficiency[END_REF] accessible through compiler intrinsics. The curve choice is the GLS binary curve (λ 2 + λ + a)x 2 = x 4 + b represented in λ-coordinates and defined over the quadratic extension F 2 254 . The extension is built by choosing the irreducible trinomial g(u) = u 2 + u + 1 over the base field F 2 127 defined with the irreducible trinomial f (z) = z 127 + z 63 + 1. In this set of parameters, a field element a is represented as a = a 0 + a 1 u, with a 0 , a 1 ∈ F 2 127 . For simplicity, parameter t is chosen to be a random subfield element, allowing the computational savings by sparse multiplications described in the previous section.

Squaring and multiplication. Field squaring closely mirrors the vector formulation proposed in [START_REF] Aranha | Efficient software implementation of binary field arithmetic using vector instruction sets[END_REF], with coefficient expansion implemented by table lookups performed through byte-shuffling instructions. The table lookups operate on registers only, allowing a very efficient constant-time implementation. Field multiplication is natively supported by the carry-less multiplier (PCLMULQDQ instruction), with the number of word multiplications reduced through application of Karatsuba formulae, as described in [START_REF] Taverne | Speeding scalar multiplication over binary elliptic curves using the new carry-less multiplication instruction[END_REF]. Modular reduction is implemented with a shift-and-add approach, with careful choice of aligning vector word shifts on multiples of 8, to explore the faster memory alignment instructions available in the target platform.

Half-trace computation. For an odd extension degree m, the half-trace function HTr : F 2 m → F 2 m is defined by HTr(c) = (m-1)/2 i=0 c 2 2i and computes a solution c ∈ F 2 m to the quadratic equation λ 2 + λ = c + Tr(c). In a quadratic extension, the equation λ 2 + λ = c + Tr(c) can be solved for c = c 0 + c 1 u ∈ F 2 2 m by computing two half-traces in F 2 m , as described in [START_REF] Hankerson | Analyzing the Galbraith-Lin-Scott point multiplication method for elliptic curves over binary fields[END_REF]. First, solve λ 2 1 + λ 1 = c 1 to obtain λ 1 , and then solve λ 2 0 + λ 0 = c 0 + c 1 + λ 1 + Tr(c 0 + c 1 + λ 1 ) to obtain the solution λ = λ 0 + (λ 1 + Tr(c 0 + c 1 + λ 1 ))u. This approach is very efficient for variable-time implementations and only requires two half-trace computations in the base field, where each half-trace computation employs a large precomputed table of 2 8 • ⌈ m 8 ⌉ field elements [START_REF] Oliveira | Two is the fastest prime: lambda coordinates for binary elliptic curves[END_REF].

A more naive approach evaluates the function by alternating m -1 consecutive squarings and (m -1)/2 additions, with the advantage of taking constant-time (if squaring and addition are also constant-time, as in the case here). We derive a faster way to compute the half-trace function in constant-time over quadratic extension fields. Applying the naive approach to a quadratic extension allows a significant speedup due to the linear property of half-trace, by reducing the cost to essentially one constant-time half-trace computation over the base field. By considering that λ 2 1 + λ 1 = c 1 has a solution λ 1 ∈ F 2 m , we always have Tr(λ 1 ) = Tr(c 1 ) = 0. This simplifies the expression above to λ 2 0 + λ 0 = c 0 + c 1 + λ 1 + Tr(c 0 ). Substituting d = c 0 + Tr(c 0 ), the expression for λ 0 becomes:

λ 0 = (m-1)/2 i=0 (d + c 1 + λ 1 ) 2 2i = (m-1)/2 i=0   d + c 1 + (m-1)/2 j=0 c 2 2j 1   2 2i
. The expansion of the inner sum allows the interleaving of the consecutive squarings. The analysis can be split in two cases, depending on the format of the extension degree m:

λ 0 =              c 0 + ⌊m/4⌋-1 i=0 (c 16 0 + d 4 + c 4 1 + c 8 1 ) 2 4i if m ≡ 1 (mod 4) ⌊m/4⌋ i=0 (c 0 + d 4 + c 2 1 + c 4 1 ) 2 4i if m ≡ 3 (mod 4).
The value λ 1 can then be computed as λ 1 = λ 2 0 + λ 0 + d + c 1 , for a total of approximately m squarings and m/4 additions, a cost comparable to a single constant-time half-trace in the base field.

Inversion. Field inversion is implemented by two different approaches based on the Itoh-Tsuji algorithm [START_REF] Itoh | A fast algorithm for computing multiplicative inverses in GF(2 m ) using normal bases[END_REF]. This algorithm computes a -1 = a (2 m-1 -1)2 , as proposed in [START_REF] Guajardo | Itoh-Tsujii inversion in standard basis and its application in cryptography and codes[END_REF], with the cost of m -1 squarings and a number of multiplications determined by the length of an addition chain for m -1. For a variabletime implementation, the squarings for each 2 i -power involved can be converted into a multi-squaring [START_REF] Bos | ECC2K-130 on Cell CPUs[END_REF], implemented as a trade-off between space consumption and execution time. Each multi-squaring table requires the storage of 2 4 • ⌈ m 4 ⌉ field elements. A constant-time implementation must perform consecutive squarings and cannot benefit considerably from a precomputed table of field elements without introducing variance in the memory hierarchy latency potentially exploitable by an intrusive attacker.

Point addition. The last performance-critical operation to be described is the point addition in λ-affine coordinates. A formula for adding points P = (x P , y P ) and Q = (x Q , y Q ) on the curve is proposed in [START_REF] Oliveira | Two is the fastest prime: lambda coordinates for binary elliptic curves[END_REF], with associated cost of 2 inversions, 4 multiplications and 2 squarings :

x P +Q = x P • x Q (λ P + λ Q ) (x P + x Q ) 2 , λ P +Q = x Q • (x P +Q + x P ) 2 x P +Q • x P + λ P + 1.
Simple substitution of x P +Q in the computation of λ P +Q gives faster new formulas. By unifying the denominators, one field inversion can be traded for 2 multiplications in the formulas below, with associated cost of 1 inversion, 6 multiplications and 2 squarings: or ElGamal encryption (variable-base) using the constant-time, timing-attack protected scalar multiplication from [START_REF] Oliveira | Two is the fastest prime: lambda coordinates for binary elliptic curves[END_REF], and computing its Elligator Squared representation with variable-time arithmetic.

x P +Q = x P • x Q (λ P + λ Q ) 2 (x P + x Q ) 2 (λ P + λ Q ) , λ P +Q = (x P + x Q ) 2 + x Q • (λ P + λ Q ) 2 (x P + x Q ) 2 (λ P + λ Q ) + λ P + 1.

Experimental results

The implementation was realized with help from the latest version of the RELIC toolkit [START_REF] Aranha | RELIC is an Efficient LIbrary for Cryptography[END_REF]. Random number generation was implemented with the recently introduced RDRAND instruction [START_REF]Intel Digital Random Number Generator (DRNG[END_REF]. Software was compiled with a prerelease version of GCC 4.9 available in the Arch Linux distribution with flags for loop unrolling, aggressive optimization (-O3 level) and specific tuning for the Sandy/Ivy Bridge microarchitectures. Table 2 presents timings in clock cycles for field arithmetic and Elligator Squared in two different platforms -an Intel Ivy Bridge Core i5 3317U 1.7GHz and a Haswell Core i7 4770K 3.5GHz. The timings were taken as the average of 10 4 executions, with TurboBoost and HyperThreading disabled to reduce randomness in the results.

The constant-time implementation results are mostly for reference: indeed, since the Elligator Squared operation is efficiently invertible, there is no strong reason to compute it in constant time: timing information does not leak secret key data like in the case of a scalar multiplication. However, timing information could conceivably help an active distinguishing attacker; the corresponding attack scenarios are far-fetched, but the paranoid may prefer to choose constant-time arithmetic as a matter of principle.

Comparison of Elligator 2 and Elligator Squared on Prime Finite Fields

We have implemented Elligator 2 [START_REF] Daniel | Elligator: Elliptic-curve points indistinguishable from uniform random strings[END_REF] and the corresponding Elligator Squared construction on Curve25519 [START_REF] Daniel | Curve25519: New Diffie-Hellman speed records[END_REF] using the fast arithmetic provided by Bernstein et al. as part of the publicly available implementation of Curve25519 and Ed25519 [START_REF] Daniel | High-speed high-security signatures[END_REF] in SUPERCOP, in order to compare the two proposed methods on Edwards curves in large characteristic (and to see how they both perform compared to our binary implementation).

To generate a random point and compute the corresponding bitstring representation, the Elligator method requires, on average, 2 scalar multiplications, 2 tests for the existence of preimages and 1 preimage computation. On the other hand, for the same computation, Elligator Squared requires, on average, 1 scalar multiplication, 2 tests for the existence of preimages, 1 preimage computation and 2 computations of the Elligator 2 map function. As a result, compared to the Elligator approach, the Elligator Squared approach requires 1 scalar multiplication less, but 2 map function computations more. Therefore, Elligator will be faster than Elligator Squared in contexts where a scalar multiplication is cheaper than 2 map function evaluations and conversely. Elligator will thus tend to have an edge for protocols using fixed base point scalar multiplication, such as ECDH key generation or ECDSA signatures, whereas Elligator Squared will perform better for protocols using variable base point scalar multiplication, like ElGamal encryption. This is confirmed by our implementation results, as reported in Table 3, which are 35-40% in favor of Elligator in the fixed-base case (DH) but 30-35% in favor of Elligator Squared in the variable-base case (EG). Note that the variable-base scalar multiplication results are estimates based on the SUPERCOP performance numbers on haswell and hydra2. A comparison with Table 2 shows that the binary curve approach is 25% to 200% times faster than the fastest Curve25519 implementation.

1+t+t 2 2 :

 2 function SAMPLEPREIMAGE(E a,b , P = (xP , λP ))

Algorithm 5 1 :

 51 Preimages Computation by Algorithm 4 function PREIMAGESSW(E a,b , Q = (xQ, λQ), t1, t2, t3)

Table 2 .

 2 Timings for Elligator Squared and underlying field arithmetic in two Intel platforms. Results are in clock cycles and were taken as the average of 10 4 executions with random inputs. DH/EG results refer to generating a random point for ECDH (fixed-base)

	Operation	Ivy Bridge Haswell
	Field squaring	13	15
	Sparse multiplication	80	44
	Multiplication	94	48
	Inversion	959	734
	Constant-time inversion	1,783	1,610
	Half-trace	55	50
	Constant-time half-trace	1,213	1,245
	Point addition	1,500	1,026
	Constant-time point addition	2,367	2,137
	Elligator Squared	23,680	22,850
	Constant-time Elligator Squared	52,850	51,750
	DH with Elligator Squared	127,430	80,180
	EG with Elligator Squared	138,480	83,680

Table 3 .

 3 Timings for Elligator Squared and Elligator 2 on Curve25519. Results are in clock cycles and were taken as the average of 10 4 executions with random inputs. DH/EG are as in Table2.

	Operation	Ivy Bridge Haswell
	Scalar multiplication (fixed-base)	42,570	42,180
	Scalar multiplication (variable-base, est.)	182,490	162,460
	Map function	38,420	36,590
	DH with Elligator Squared	157,500	141,200
	DH with Elligator 2	114,800	100,200
	EG with Elligator Squared (est.)	297,420	261,480
	EG with Elligator 2 (est.)	394,640	340,760

We point out that using constant-time arithmetic for Elligator Squared is not required in most realistic adversarial models, but it does offer protection against very powerful distinguishing attackers, so the paranoid may prefer that option nonetheless.

This can be justified rigorously using the fact that the corresponding function field extensions are pairwise linearly disjoint, exactly as in the image size computations of[18, §4]. For simplicity, we do not include the tedious Galois extension computations involved.