A colouring protocol for the generalized Russian cards problem

A colouring protocol for the generalized Russian cards problem Andr´es Cord´on–Franco, Hans van Ditmarsch, David Fern´andez–Duque, and Fernando Soler–Toscano∗ March 27, 2014 Abstract In the generalized Russian cards problem, Alice, Bob and Cath draw a,band ccards, respectively, from a deck of size a+b+c. Alice and Bob must then communicate their entire hand to each other, without Cath learning the owner of a single card she does not hold. Unlike many traditional problems in cryptography, however, they are not allowed to codify or hide the messages they exchange from Cath. The problem is then to find methods through which they can achieve this. We propose a general four-step solution based on finite vector spaces, and call it the “colouring protocol”, as it involves colourings of lines. Our main results show that the colouring protocol provides a solution to the generalized Russian cards problem in cases where ais a power of a prime, c=O(a2) and b=O(c2). This improves substantially on the collection of parameters for which solutions are known. In particular, it is the first solution which allows the eavesdropper to have more cards than one of the communicating players. ∗Emails and affiliations: {acordon,hvd,dfduque,fsoler}@us.es, University of Sevilla, Spain. Hans van Ditmarsch is also affiliated to IMSc, Chennai, India, as a research associate. 1 arXiv:1207.5216v4 [cs.IT] 26 Mar 2014 1 Introduction The goal of this article is to provide a solution to the generalized Russian cards problem [1] based on finite vector spaces. The problem is parametrized by the triple (a, b, c), which we will often call its size and may be stated as follows: The generalized Russian cards problem Alice, Bob and Cath each draw a, b and ccards, respectively, from a deck of a+b+c. All players know which cards were in the deck and how many of them the other players drew, but each player may only see the cards in their own hand. Alice and Bob, however, want to know exactly which cards the other holds. Moreover, they do not want for Cath to learn who holds any card whatsoever, aside of course from her own cards. However, they may only do so by making unencrypted public announcements, so that Cath can learn all the information that they exchange. Can Alice and Bob achieve this? Some general assumptions are needed to make the problem precise, which we shall formalize in Section 2. First, the cards are dealt beforehand in a secure phase which we treat as a black box and gives the players no information about others’ cards. The agents have no communication before this phase and cannot share secrets (such as private keys). Second, the agents have unlimited computational capacity.1This means, on one hand, that solutions via encryption are not valid, provided they are vulnerable to cryptanalisis (independently of its computational cost). It also means that we shall not be concerned with the feasibility of agents’ strategies, although this is certainly an important line for future inquiry. Third, all strategies are public knowledge, in keeping with Kerckhoffs’ principle [4]. These assumptions turn the problem into a challenging combinatorial puzzle. 1This assumption is unusual in traditional cryptography but is standard in informationtheoretic approaches where unconditional rather than probabilistic security is sought [8]. 2 A (possible) solution to the generalized Russian cards problem is a protocol; these shall also be discussed formally in Section 2. The solution we propose is, to the best of our knowledge, the first solution to the generalized Russian cards problem which works in cases where Cath holds more cards than Alice. The Russian cards problem itself originates with Kirkman [5]. There, the solution takes the form of a design, a collection of subsets of a given set that satisfies certain regulaties [11]. The design consists of seven triples. Cryptography based on card deals is also investigated in various other (not necessarily related) publications, such as [9, 10]. Many instances of the generalized Russian cards problem have been studied. We remark that all of these protocols obtain a notion of security called weak 1-security by Swanson and Stinson [12], the notion we are concerned with in this paper. A stronger and more general notion of perfect k-security is also considered by them but we shall not treat it here. The known solutions are as follows. 1. The original (3,3,1) case has been extensively studied and has many solutions [5, 7]. 2. The case (4,4,2) has a three-step solution given in [13], where it is also shown that there is no two-step solution. 3. All cases (a, 2,1) provided a≡0,4 (mod 6) have been solved in [1]. 4. All cases (a, b, 1) with both a, b > 2 have been solved in [2]. 5. If c+ 1 < a then there is a solution for b=O(a2) [1]. The case (a, b, 1) with a, b > 2 subsumes the case (3, b, 1) for b≥3, also covered previously in [1]; [12] demonstrates that, for the stronger notion of perfect 1-security, every announcement in a (3, b, 1) solution is a Steiner triple. They have yet another characterization result for perfect k-security. Our main contribution is to provide solutions for infinitely many cases where b=O(c2) and either c=O(a3 /2) or c=O(a2), the first known solutions for c > a. We remark that all but one of the previously known protocols are two-step protocols, whereas our protocol is in four steps. In [1] it is shown that there can be no two-step solution if c≥a−1. As we provide solutions with c>a, the protocol we propose is longer. We do not know if a shorter, three-step variant is possible. 3 The plan of the paper is as follows. Section 2 formalizes our model of security and our notion of protocol. Section 3 gives an informal description of the protocol, in order to motivate the more specific description given in Definition 3.6. This protocol depends on certain parameters which do not exist for all values of (a, b, c). The conditions under which such parameters exist are treated in Section 4. Finally, Section 5 computes explicit bounds on the parameters for which the protocol is executable. 2 Protocols and security In this section we shall present the notion of protocol we shall use. Throughout this paper, we assume that Dis a fixed, finite set of “cards”. A card deal is a partition (A, B, C) of D; the deal has size (a, b, c) if Ais an a-set, Bab-set and Cac-set, where by “x-set” we mean a set of cardinality x. The set of x-subsets of Yis written Y x. We think of Aas the hand of Alice, or that Alice holds A; similarly, Band Care the hands of Bob and Cath, respectively. In general we may simply assume that D={1, . . . , a +b+c}, and define Deal(a, b, c) to be the set of partitions of Dof size (a, b, c). Central to this text is the notion of protocol. Roughly, a protocol is a family of rules or instructions that Alice and Bob must follow in order to send out a sequence of public announcements. Protocols are in principle nondeterministic, assigning only a probability measure to the announcements that an agent may make. In [12] and other papers, an announcement has been modelled as a set of hands that one of the agents may hold. Thus Alice would announce a subset Aof D a, indicating that A∈ A. More specifically, an announcement is a pair (i, A), where iis the agent making the announcement (either Alice or Bob). But for our proposed solution, agents’ announcements are not in one-one correspondence to subsets of D a. Because of this, it will be simpler to model announcements as elements of a countable or finite set, say N; a similar setup is proposed in [12], where Alice enumerates all subsets of D a by A0,A1,...,Anand merely announces the appropriate subindex. Thus we let Ann = {Alice, Bob}×Jbe the set of announcements, where J⊆N. A sequence of announcements ~α = (i0, φ0),(i1, φ1),...,(in, φn) is a run. We shall write Run for the set of runs, including the empty sequence. An (unusual) assumption of the problem is that there is a secure dealing phase which we treat as a black box. Initially, a card deal is selected 4 randomly and players have knowledge of their own cards and of the size (a, b, c) of the deal, but know nothing more about others’ cards. Thus they are not able to distinguish between different deals where they hold the same hand. We model this by equivalence relations between deals; since from Alice’s perspective, (A, B, C) is indistinguishable from (A, B0, C0), we define (A, B, C)Alice ∼(A0, B0, C0) if and only if A=A0. We also define analogous equivalence relations for Bob and Cath. In [12], Swanson and Stinson define strategies of length two as assigning a probability distribution to Alice’s possible announcements (after which Bob announces Cath’s hand), and consider n-equitable strategies as a special case where Alice always has npossible announcements each with probability 1 /n. We will work with equitable strategies (and merely call them protocols), where probability is distributed evenly among the possible outcomes but the number of outcomes is left unspecified. This will allow us to dispense with probability measures and only determine a set of possible announcements at each stage of the protocol. On the other hand, we consider protocols which may have more than two steps, making our definition more elaborate than Swanson and Stinson’s. Definition 2.1 (Protocol).Let Deal = Deal(a, b, c). Aprotocol (with (a, b, c)as parameters) is a pair of functions (j, π)assigning to every deal δ∈Deal and every run ~α ∈Run an agent j(~α)∈ {Alice, Bob}and a finite set π(δ, ~α)⊆Nsuch that if δ0j(~α) ∼δ, then π(δ0, ~α) = π(δ, ~α). Thus once a deal has been given, a protocol assigns to each run a player who is to make the next announcement and a set of possible announcements for the player to make. These announcements are determined exclusively by the information an agent has access to, which is assumed to be only (i) their hand, (ii) the parameters a, b, c, (iii) the announcements that have been made previously and (iv) the protocol being executed. Protocols are non-deterministic in principle and hence may be executed in many ways; an execution of a protocol is a pair (δ, ~α), where δis a deal, ~α = (i0, φ0),...,(in, φn) a run and, for all k < n,ik+1 =j(i0, φ0),...,(ik, φk) and φk+1 ∈πδ, (i0, φ0),...,(ik, φk). The first property that a protocol needs to have in order to be successful is for its set of executions to be non-empty. This observation seems trivial but it will occupy a large portion of the paper. 5 Definition 2.2 (Executability).Given a natural number N, a protocol is N- executable if for every deal δthere is an execution (δ, ~α)where αhas length N. We may omit the parameter Nand let it be given by context; the protocol we propose has four steps so we take N= 4. The second property that a protocol must have to be successful is that Alice and Bob know each other’s cards (and hence the entire deal) after its execution: Definition 2.3 (Informativity).An execution ((A, B, C), ~α)is informative for Alice if there is no execution ((A, B0, C0), ~α)with C06=C. Similarly, an execution ((A, B, C), ~α)is informative for Bob if there is no execution ((A0, B, C0), ~α)with C06=C. A protocol is informative if there exists Nsuch that the protocol is N- executable and every execution of length Nis informative both for Alice and for Bob. The third property is that, given a card xwhich Cath does not hold, she should consider it possible that either Alice holds it or Bob holds it: Definition 2.4 (Safety).An execution ((A, B, C), ~α)of a protocol (j, π)is safe if for every x6∈ Cthere is 1. a deal δ0= (A0, B0, C)such that x∈A0and (δ0, ~α)is also an execution of (j, π), as well as 2. a deal δ00 = (A00, B00, C)such that x∈B00 and (δ00, ~α)is also an execution of (j, π). The protocol (j, π)is safe if every execution of (j, π)is safe. Safety is equivalent to weak 1-security as defined by Swanson and Stinson [12], but this is not the only notion of security they discuss. Weak security is equivalent to the statement that for all C,x6∈ Cand every execution ~α of the protocol, 0<Pr(x∈A|C, ~α)<1 (where Pr(X|Y) denotes conditional probability). Stronger notions of security would demand that Cath does not gain probabilistic information, so that Pr(x∈A|C, ~α) = a a+b 6 (perfect 1-security in [12]). In this paper we will only be concerned with weak security. 3 The protocol In this section we shall describe the general colouring protocol, the central focus of this article. Before we do so, let us briefly describe some of the notation we shall use. We will use pto denote a prime or a power of a prime, and Fpthe field with pelements. If dis any natural number, Fd pdenotes the vector space of dimension dover Fp. For a line `=x+λy, we say yis a directing vector of `. We denote by Ld pthe set of all lines in Fd p. The theory of finite fields and finite geometries has been extensively studied; see, for example, [6, 3]. For natural numbers d, n we define σd(n) to be the sum nd−1+nd−2+ . . . +n0. We know from basic algebra that σd(n) = (nd−1)/(n−1).This will be a very useful quantity to keep in mind; for example, Lemma 3.1. Given x∈Fd p, there are σd(p)distinct lines passing through x. Let pbe a prime or a prime power and d≥2. Assume that Alice holds as many cards as points in a line of Fd p(i.e. a=p) and that Alice, Bob and Cath together hold as many cards as points in the whole space (i.e. a+b+c=pd). Let Kbe a set of kcolours, identified with the numbers 1, . . . , k. Colourings will be a crucial element in our protocol: Definition 3.1 (Colouring).Ak–colouring is a function ξ:Ld p→K. That is, ξassigns a colour from {1, . . . k}to each line in Fd p. Let us now give an informal account of the protocol; Definition 3.6 will give a formal version and Section 4 will study its executability. It consists of the following four steps: 1. Alice maps all the cards into Fd pin such a way that her cards form a line and announces the mapping. 2. Bob announces a suitably chosen k-colouring ξ. 3. Alice announces the colour of her hand according to ξ. 4. Bob announces Cath’s cards. 7 Of course, we have yet to specify what a suitable colouring is. This will be the focus of the rest of this section. In order to guarantee that the protocol is informative (Alice and Bob can deduce the card deal after the protocol’s execution), the colouring must be distinguished, as defined below. For it to be safe (Cath cannot learn any of Alice or Bob’s cards), the colouring should also be rich. However, colourings which are merely rich and distinguished may give Cath too much information, and thus we will have to replace the condition of being distinguished by the stronger version of being very distinguished. Once we have defined these notions the next question is for which a, b, c and ksuch colourings exist, i.e., when the protocol is executable; this shall be the topic of later sections. First let us focus on making the protocol be informative. Given a card deal (A, B, C), we should design ξin such a way that only Aitself can be the line entirely contained in A∪Cof whichever colour Alice announces. In this way, Bob can unequivocally identify A. But there may be many such spaces contained in A∪C, and at the beginning of the protocol Bob has no way of telling them apart. Thus we arrive at the following: Definition 3.2 (Distinguished colouring).We say that a k–colouring ξis distinguished for a set E⊆Fd pif no two distinct lines contained entirely in Ehave the same colour. 0 1 2 0 1 2 0 1 2 0 1 2 Figure 1: A simple 2-colouring. Example 3.1. Figure 1 illustrates the possible effects of a distinguished colouring. The left picture shows a 2-colouring that Bob announces after Alice maps the cards into F2 3. Throughout the examples we will continue to use black squares for Alice’s cards, white circles for Bob’s and black triangles 8 for Cath’s, so that cards held by Alice or Cath are black-filled shapes. Alice’s cards Aform the line {00,01,02}. Cath’s cards Care {12,22}. The set A∪Calso contains the line {02,12,22}. In order to enable Alice, by her later response, to distinguish between the lines, Bob announces the 2-colouring in the the left picture. It has two ‘colours’: solid lines and dashed lines. Ellipses in the figure are lines as well, e.g. {02,10,21}is a dashed line. Suppose Alice announces that her line is solid. Then, Bob will learn Alice’s cards and he can announce Cath’s cards. But the colouring that Bob announces is not safe. After Alice announces that her cards are a solid line, Cath discards all solid lines that meet some of her points. The right picture in Figure 1 shows the only two lines that Cath cannot discard. This makes Cath learn that Alice has 02 and that Bob has 10 and 21. Hence, colourings that are merely distinguished will make the colouring protocol informative but not necessarily safe. To remedy this, we must have enough colours, and the colouring must be rich enough, so that for every card that Cath does not hold she should consider it possible both that Alice holds it and that Alice does not hold it. Definition 3.3 (Rich colouring).Ak–colouring ξis rich (or c–rich) if for any c-set C, colour i, and point x6∈ C, there is an i-coloured line Acontaining xthat avoids Cand there also is an i-coloured line A0not containing x that avoids C. Rich and distinguished colourings are almost suitable, but we shall need an extra condition. Notice that Cath knows that Bob is to design the colouring so that it turns out to be informative. Thus, the colouring not only should be distinguished for the actual set of cards A∪Cbut also for every set of cards that Bob wants Cath to consider as possible. These will be the sets with the same hue as A∪C: Definition 3.4 (Hue).Let ξbe a k-colouring. Given E, F ⊆Fd p, we write E≈ξ 1Fif there are lines `, h of the same colour such that `⊆E,h∩(E\`) = ∅and F= (E\`)∪h. We will say E, F are one swap apart. We then let ≈ξbe the reflexive and transitive closure of ≈ξ 1, and define a hue to be an equivalence class under ≈ξ. 9 The above considerations suggest that critical colourings are very distinguished, and indeed this will turn out to be the case. Before we show this, let us make a simple observation: Lemma 4.3. If ξis a critical k–colouring for Eand `⊆E, then `is a ξ–critical line for E, independently of how the other critical lines are chosen. Proof. Let L={`∗ 1, . . . , `∗ n}be ξ-critical lines for E. Notice that since they are lines of different colours, we have n≤k. If `is not ξ–critical then for every i≤n,`∩`∗ iis either empty or a singleton. It therefore follows that   (`∩E)\[L  =     `\[ i≤n `∗ i     ≥p−n≥p−k, which contradicts the definition of a critical k–colouring. Now we will check that critical colourings are very distinguished. For this, it suffices to show that they are distinguished and that a critical colouring for Eis critical for the entire hue of E; the former is straightforward, the latter rather involved. Lemma 4.4. Every critical k–colouring for Eis distinguished for E. Proof. From Lemma 4.3 it follows that if `⊆Ethen it is critical; but there is at most one critical line of each colour so there cannot be h6=`of the same colour both contained in E. Lemma 4.5. Suppose ξis a critical k-colouring for Ewith k < p and Fhas the same hue as E. Then, ξis also a critical colouring for F. Proof. We shall prove this by induction on the number of swaps between E and F. The base case (F=E) is vacuous. For the inductive step, suppose F= (G\λ1)∪λ2with ξ(λ1) = ξ(λ2) = jand Gone swap closer to E than Fis, so that by induction we may assume that there are ξ-critical lines `∗ 1, . . . , `∗ nfor Gwith n≤k. Observe that `∗ j=λ1; indeed, λ1⊆G, so that by Lemma 4.3, λ1=`∗ ifor some i. But ξ(λ1) = j, and therefore i=j. Our goal is to show that ξis also critical for F; we will do this by proving that the lines h∗ 1, . . . , h∗ ndefined by h∗ i=`∗ ifor i6=jand h∗ j=λ2are critical. For this it will suffice to check that if `is any line, (`∩F)\[ i≤n h∗ i⊆(`∩G)\[ i≤n `∗ i; (1) 16 this inclusion would then imply that      (`∩F)\[ i≤n h∗ i     ≤     (`∩G)\[ i≤n `∗ i      < p −k, showing that h∗ 1, . . . , h∗ n(and hence ξ) are critical for F. To establish (1), pick x∈(`∩F)\Si≤nh∗ i. It is obvious that x∈`∩G, except perhaps in the case that x∈λ2. But λ2=h∗ j, so this cannot be, and therefore we always have x∈`∩G. Next, we need to check that x6∈ `∗ ifor any i≤k. This is obvious if i6=j, since `∗ i=h∗ i. Thus it remains to rule out that x∈`∗ j. If we had x∈`∗ j=λ1, we would also have that x∈λ1\h∗ j=λ1\λ2. But Fdoes not intersect this set, so this is impossible. We conclude that (1) holds, and thus ξis critical for F, as desired. As promised, we now have the following: Lemma 4.6. Every critical colouring is very distinguished. Proof. If ξis critical for E, then by Lemma 4.5, it is also critical for every set of the same hue as E; thus, by Lemma 4.4, it is also distinguished for every such set. We have seen that in order to construct very distinguished colourings, it suffices to construct critical colourings. This has the advantage that the notion of being critical depends only on a set Eand not on the entire hue of E. However, it is still not entirely obvious when exactly critical colourings exist or how one is to go about building one. This is where perfect colourings come into play. Although perfect colourings are not perfect for their entire hue, they are very easy to identify, and every perfect colouring is automatically critical. Definition 4.3 (Perfect k–colouring).Given E⊆Fd p, let Lm(E)denote the set of all lines `such that |`∩E| ≥ m. We say that a k-colouring ξis perfect for Eif different elements of Lp−k(E)have different colours. Perfect colourings, when they exist, are quite easy to identify and construct, yet they are always very distinguished: 17 Proposition 4.1. If ξis a perfect colouring for E, then ξis very distinguished for E. Proof. First we note that ξis critical, since we can take all of Lp−k(E) as critical lines, given that they are all of different colour. Then, by Lemma 4.6, we have that ξis very distinguished, as required. Now for the main result of this section: Theorem 4.1. Assume that a, b, c, d, k satisfy the following conditions: 1. ais a prime or a prime power, 2. a+b+c=ad, 3. k < a, 4. for every S⊆Fd awith |S| ≤ a+c, we have |La−k(S)| ≤ k; 5. σd(a)≥k(c+ 3). Then, the colouring protocol is executable. Proof. Assume that Alice has announced fand for this proof let A, B, C denote the images of each player’s hand under f. By assumption, |La−k(A∪ C)| ≤ k, so Bob can enumerate La−k(A∪C) by ~ `=h`1, . . . , `ni, with n≤ k. Then, by Lemma 4.2, there exists a colouring ξwith density c+ 2 and such that ξ(`i) = i, which by construction is perfect for A∪C, so that by Proposition 4.1, it is also very distinguished. Further, by Lemma 4.1, we see that ξis rich, as needed. The above proof should be seen as a theoretical argument that very distinguished colourings exist under the above conditions – but never as an algorithm for constructing them. It is essential for our protocol that Bob choose randomly among all possible colourings. We leave the specification of feasible algorithms for doing so for future work. 18 5 Finding suitable parameters The conditions given by Theorem 4.1, while rather general, remain somewhat implicit. In this subsection we shall compute some explicit bounds on the parameters which guarantee that these conditions are met. The computations we will make are a bit rough, but will nevertheless give us a large family of parameters for which the protocol is guaranteed to work. They are based on the following counting lemma: Lemma 5.1. If a set E⊆Fd pis such that |E|<(k+ 1)(p−k)−k(k+ 1) 2, then |Lp−k(E)| ≤ k. Proof. We argue by contrapositive, assuming that |Lp−k(E)|> k. Let `1, . . . , `k+1 be distinct lines such that |E∩`i| ≥ p−k. Then, we have |E| ≥  Si≤k+1(`i∩E)  ≥Pi≤k+1 |`i∩E|−Pi<j≤k+1 |`i∩`j| ≥(k+ 1)(p−k)−1 2k(k+ 1). Thus in view of Theorem 4.1, in order to find suitable parameters, it suffices to solve the system of inequalities 1. a+c < (k+ 1)(a−k)−1 2k(k+ 1), 2. ad−1 a−1≥k(c+ 3) or, simplifying a bit, 1. c < ak −3 2k(k+ 1), 2. ad> k(a−1)(c+ 3). From this we immediately obtain the following asymptotic result: Theorem 5.1. If ais a large enough prime power, the colouring protocol is executable with 19 1. c<O(a3 /2)and d= 3 or 2. c<O(a2)and d= 4. Proof. In view of Theorem 4.1 and Lemma 5.1, it suffices to show that the above inequalities hold. For the first result, set k≈√aand c≈a3 /2 /2. Then, we have that ak−3k(k+1) /2=a3 /2+O(a),which for large ais greater than a3 /2 /2. Meanwhile, k(a−1)(c+ 3) = a3 /2+O(a2),which for large ais bounded by a3. The second is similar; here, set k≈a /2and c≈a2 /9. A nice conclusion we obtain from the above result is that indeed ccan be larger than aby any order of magnitude we desire, provided ais large enough: Corollary 5.1. Given any natural number N, there exist a, c such that c /a> Nand the colouring protocol is executable, sound and informative for (a, a3− a−c, c). Proof. If aN2then a3 /2= (a1 /2)aNa and, by Theorem 5.1.1, the required inequalities hold and the protocol is executable. Note that we may use Theorem 5.1.1 or Theorem 5.1.2 depending on whether we wish to keep brelatively small with respect to aor arelatively small with respect to c. In either case, b=O(c2). 6 Conclusions and further research The colouring protocol we have presented gives a new and flexible solution to the generalized Russian cards problem. Our protocol solves the problem in many cases where the eavesdropper has more cards than one of the players, and is the first known solution to achieve this. If the generalized Russian cards problem is to be understood as Find triples (a, b, c)for which a safe and informative protocol of any length exists, then the current work is a giant stride over what had been previously achieved. There are many variations that could be analyzed and might yield important results. Alice may have more than one line, there may be more players, Cath may be allowed to learn a few of the cards, etc. Along these lines, a particularly promising direction would be to replace lines by other algebraic 20 curves. This could, potentially, reduce the size of the whole space (and hence Bob’s hand) without compromising the existence of suitable colourings. A different direction to pursue involves cases where either aor a+b+care not prime powers. There are already standard techniques to deal with these; one finds a prime which is not much larger than the desired parameter and works with that instead. Such techniques have already been used to extend a different protocol to many new triples in [2] but have not been worked out in our context. Meanwhile, the generalized Russian cards problem may have a recreational flavour to it, but it has potential for serious applications in secure communication. These protocols have an advantage over most traditional encryption methods in that they are “unconditionally secure”, meaning that an eavesdropper is unable to decipher messages even when granted unlimited computational capacity. The presupposition of a “dealing stage” is not so different to authentication systems using security tokens, where the user receives a physical device that generates one-time passwords. A possible application is the development of challenge-response authentication systems. The user Bob is authenticated against the server Alice by running a Russian cards protocol. If Alice checks that Bob’s responses are coherent with the key he should have (Bob’s hand) then the authentication succeeds. Real-world implementation of these protocols would also require an additional computational and probabilistic analysis. What is the complexity of running the colouring protocol? Are there good algorithms for finding suitable colourings? Even if Cath does not learn any cards, how do we minimize the probability that she guesses them correctly? To summarize, there is much to be done indeed! Acknowledgements This research was supported by the project Logics for Unconditionally Safe Protocols, Excellence Research Project of the Junta de Andaluc´ıa P08-HUM- 04159. 21 References [1] M.H. Albert, R.E.L. Aldred, M.D. Atkinson, H. van Ditmarsch, and C.C. Handley. Safe communication for card players by combinatorial designs for two-step protocols. Australasian Journal of Combinatorics, 33:33–46, 2005. [2] A. Cord´on-Franco, H. van Ditmarsch, D. Fern´andez-Duque, J.J. Joosten, and F. Soler-Toscano. A secure additive protocol for card players. Australasian Journal of Combinatorics., 54:163–175, 2012. [3] P. Dembowski. Finite Geometries (reprint). Springer, 1997. [4] A. Kerckhoffs. La cryptographie militaire. Journal des sciences militaires, IX:5–38 and 161–191, 1883. [5] T. Kirkman. On a problem in combinations. Camb. and Dublin Math. J., 2:191–204, 1847. [6] R. Lidl. Finite Fields. Cambridge University Press, 1997. [7] K.S. Makarychev and Yu.S. Makarychev. The importance of being formal. Mathematical Intelligencer, 23(1):41–42, 2001. [8] U. Maurer. Information-theoretic cryptography. In M. Wiener, editor, Advances in Cryptology — CRYPTO ’99, volume 1666 of Lecture Notes in Computer Science, pages 47–64. Springer-Verlag, August 1999. [9] T. Mizuki, H. Shizuya, and T. Nishizeki. A complete characterization of a family of key exchange protocols. International Journal of Information Security, 1:131–142, 2002. [10] A. Stiglic. Computations with a deck of cards. Theoretical Computer Science, 259(1–2):671–678, 2001. [11] D.R. Stinson. Combinatorial Designs – Constructions and Analysis. Springer, 2004. [12] C. M. Swanson and D. R. Stinson. Combinatorial solutions providing improved security for the generalized russian cards problem. arXiv, 1207.1336 [math.CO], 2012. 22 [13] H. van Ditmarsch and F. Soler-Toscano. Three steps. In J. Leite, P. Torroni, T. ˚ Agotnes, G. Boella, and L. van der Torre, editors, Computational Logic in Multi-Agent Systems - 12th International Workshop, CLIMA XII. Proceedings, pages 41–57. Springer, 2011. LNCS 6814. 23