A secure additive protocol for card players

AUSTRALASIAN JOURNAL OF COMBINATORICS Volume 54 (2012), Pages 163–175 A secure additive protocol for card players Andr´ es Cord´ on-Franco Dpto. de Ciencias de la Computaci´on e Inteligencia Artificial Universidad de Sevilla, 41012 Sevilla Spain [email protected] Hans van Ditmarsch∗ Dpto. Filosof´ıa, L´ogica y Filosof´ıa de la Ciencia Universidad de Sevilla, 41018 Sevilla Spain [email protected] David Fern´ andez-Duque Dpto. de Ciencias de la Computaci´on e Inteligencia Artificial Universidad de Sevilla, 41012 Sevilla Spain [email protected] Joost J. Joosten Dept. L`ogica, Hist`oria i Filosofia de la Ci`encia Universitat de Barcelona, 08001 Barcelona Spain [email protected] Fernando Soler-Toscano Dpto. Filosof´ıa, L´ogica y Filosof´ıa de la Ciencia Universidad de Sevilla, 41018 Sevilla Spain [email protected] ∗Hans van Ditmarsch is affiliated to IMSC (the Institute of Mathematical Sciences Chennai), India, as a research associate. Corresponding author. 164 A. CORD ´ ON-FRANCO ET AL. Abstract Consider three players Alice, Bob and Cath who hold a,band ccards, respectively, from a deck of d=a+b+ccards. The cards are all different and players only know their own cards. Suppose Alice and Bob wish to communicate their cards to each other without Cath learning whether Alice or Bob holds a specific card. Considering the cards as consecutive natural numbers 0,1,...,we investigate general conditions for when Alice or Bob can safely announce the sum of the cards they hold modulo an appropriately chosen integer. We demonstrate that this holds whenever a, b > 2andc= 1. Because Cath holds a single card, this also implies that Alice and Bob will learn the card deal from the other player’s announcement. 1 Introduction Consider players Alice and Bob each drawing three cards from a deck of seven cards numbered 0, 1, ..., 6, while Cath, a third player acting as the eavesdropper, gets the remaining card. One way for Alice and Bob to communicate their cards to each other by way of public announcements, without informing Cath of any of their cards, is when both announce the sum modulo 7 of their cards. For example, suppose Alice holds cards 0, 1, and 2, and Bob cards 3, 4, and 5 (so that Cath holds card 6). Alice would then announce “3” and Bob would announce “5”. There are five different hands of cards compatible with Alice’s announcement, namely 012, 046, 136, 145, and 235. From those, Cath, who holds 6, can eliminate 046 and 136. Cath cannot deduce that Alice has 0, because 145 is a possible hand of Alice. She also cannot deduce that Alice does not have 0, because Alice’s actual hand 012 is also a possible hand. Bob’s announcement that the sum of his cards modulo 7 is 5, does not provide additional information. But this is informative for Alice, namely in order to learn Bob’s cards, Cath already knows Bob’s sum after Alice’s announcement, because she can derive that from: the sum of all cards, her own card, and the sum of Alice’s cards. This solution consisting of two modulo-sum announcements is an instance of what we will later introduce as the 7-ModSum protocol. The modulo-sum solution for this problem was among the answers to a Moscow Mathematics Olympiad problem [7]. In that version, after Alice’s modulo sum announcement, Bob announces Cath’s card. This answer can easily be shown to have the same information content as a consecutive modulo sum announcement by Bob. The problem itself is much older and originates with Kirkman [6]. There, the solution takes the form of a design, a collection of subsets of a given set that satisfies certain regularities [11]. The five alternative hands of Alice solving the problem above are not a design. But, for the same card deal as above, Alice’s announcement could also have been that she holds one of seven triples 012,034,056,135,146,236,245. We note that each card occurs three times in this announcement and each pair of cards once. It is a design. Instead of 3, 3, and 1 cards, players Alice, Bob and Cath may hold a, b, c cards. Some general patterns and special cases of card deal sizes (a, b, c)for A SECURE ADDITIVE PROTOCOL 165 which Alice and Bob can communicate their hands of cards to each other are found in [1]. A complete characterization is not known. The methods employed in that publication are not numerical (they do not involve modulo sum announcements). There is also a relation to the bit exchange problem: is it possible for Alice and Bob to share a secret bit by public communication? A secret bit is the value of a proposition commonly known by them, but not know by the ‘eavesdropper’ Cath. For example, let ibe a card held by Alice, then after the execution of the above protocol Alice and Bob share the value of the secret bit ‘Alice holds card i’. The seminal publication for card exchange and bit exchange protocols is [5], and additional contributions include [8]. A (single) bit exchange is easier to accomplish: it suffices to keep the ownership of one card a secret, not necessarily the ownership of all cards. E.g., if Alice were to announce ‘I have one of 012, 034, 056’, then afterwards Alice and Bob share the value of the proposition ‘Alice holds 1’. But, of course, it is now known to all that Alice holds card 0. The crucial difference between our approach and the ones cited above is that we begin by assigning an algebraic structure to the set {0,...,d−1}.Thisallowsusto describe protocols in a compact fashion and draw on known combinatorial results, namely, a conjecture of Erd¨os and Heilbronn [4] giving lower bounds of the number of distinct sums of n-subsets of Z/(d) (later proven by Dias da Silva and Hamidourne [3]), and Bertrand’s postulate [10], as well as a theorem of Nagura [9], which show that one can always find a prime number relatively close to a given integer. Below we will formulate these results in full detail. Referring to the agents as ‘card players’ is suggestive, because the scenarios we model are not meant to model any specific game, and the condition of Alice and Bob’s full knowledge together with Cath’s total ignorance would not be too appropriate, say, for poker. Rather, the interest of the Russian cards problem is that it gives unconditionally safe information exchange protocols, as opposed to conditionally safe cryptography which depends on the assumption that certain problems are of untractably high complexity, such as prime decomposition. In such protocols, Alice and Bob would be the principals involved in the exchange of information, and Cath the spy or eavesdropper (also known as Eve) intercepting their communications. The authors believe that their work could lead to new methods of secure information exchange. In this paper we give general conditions on a, b, c that guarantee that Alice can safely announce the sum of her cards modulo the smallest prime greater than or equal to d=a+b+c(that is, without Cath learning whether Alice or Bob holds any given card). In particular, they hold whenever a, b > 2andc= 1, except for the cases (3,4,1) and (4,3,1). If c= 1 this announcement is also informative, i.e., Alice and Bob will learn the card deal from the sum announcement of the other player. In §4 we consider the case where the sum dof all cards is already prime, and in §5 we consider composite d. The exceptional cases (3,4,1) and (4,3,1) are treated separately in §6. This is then followed by the main theorem which incorporates all of these partial results. 166 A. CORD ´ ON-FRANCO ET AL. 2 Secure and informative protocols Consider a deck Dof dcards. We will identify the cards with the natural numbers 0,1,...,d−1. We say that a deal of acards for Alice, bfor Bob and cfor Cath, with a, b, c ≥1anda+b+c=dhas card deal size (a, b, c). A,Band Crepresent each player’s hand, i.e., the cards that they hold. We can represent the card deal by the collection (A, B, C). Consider the domain consisting of all card deals of a certain size (a, b, c), i.e., of all (A, B, C)withA, B, C ⊆D,andA, B, C pairwise disjoint. The property that players initially only know their own cards induces a partition on this domain. The card deals in the same equivalence class for a player are indistinguishable for that player. A protocol consists of a finite sequence of announcements by Alice and Bob. These announcements are supposed to be truthful. An announcement by, e.g., Alice corresponds to a collection of possible hands of cards Aincluding her actual hand, and the effect of her announcement is the restriction of the domain of card deals to all deals wherein she has one of those hands. Subsequent announcements induce successive such restrictions on the domain of card deals. Given a deal of cards and a sequence of announcements, a player Xknows that a player Yholds a card z,ifand only if Yholds zin all card deals indistinguishable for player X. A player knows the card deal if she knows the ownership of all cards. E.g., before Alice’s announcement 012 034 056 135 246 above, Bob, who holds {3,4,5}, does not know that Alice holds 0, because he considers hands {0,1,2}and {1,2,6}(among more) possible for Alice. But after the announcement, Bob knows that Alice holds 0. Before announcements, all players know the cards in their own hand. In this work we restrict ourselves to protocols consisting of two announcements. An announcement by Alice is informative if, whenever Alice can make the announcement, Bob knows the card deal afterwards. An announcement by Alice is secure if, whenever Alice can make the announcement, Cath does not know any of Alice or Bob’s cards afterwards. Similarly for informative and secure announcements by Bob. 3 The modulo-sum announcement For n≥dand X⊆D,nXdenotes the sum of the elements of Xseen as elements of Z/(n). Definition 1 (n-ModSum)Let n≥dbe an integer. We define the n-modulo-sum (n-ModSum) protocol to be that where Alice and Bob successively announce the sum of their respective cards modulo n. Because they announce a sum, we call it an additive protocol. Proposition 2 (Information) The n-ModSum protocol is informative if c=1. Proof: We have that nA+nB+nC=nD. Once Alice announces nA, Bob can compute the term nCfrom the three other terms in this equation. In A SECURE ADDITIVE PROTOCOL 167 case that Cis a singleton, this immediately gives him the value of Cath’s card. Similarly, nBallows Alice to figure out Cath’s card as well, giving both Alice and Bob knowledge of the entire deal.  The order in which the announcements are made is unimportant, since both agents announce information that was true at the beginning and that remains true after the announcement by the other agent. Although obvious in this case, it is a remarkably characteristic of a protocol: the order of announcements in a protocol can typically not be altered. E.g., in the protocol where Bob’s response to Alice’s sum announcement is to announce Cath’s card, the order of announcements cannot be swapped. From Cath’s perspective, it does not matter whether she learns nAor nB, since she can use one to compute the other. In that sense she does not learn anything new in the second announcement. Suppose Alice is first, then Cath already knows what Bob will announce after Alice, before he is doing so. She cannot eliminate card deals given Bob’s announcement. But in another sense she still learns something from Bob’s announcement: after that, Cath knows that Alice knows the card deal. If c>1, the announcement is typically not informative. For example, if Alice, Bob and Cath each hold two cards respectively, namely {0,1},{2,5},and{3,4}, then Alice announcing that 6A= 1 does not result in Bob learning Alice’s cards, as they may also be {3,4}. Although the n-ModSum protocol is informative for c= 1, it is not always secure. For a trivial example, if Alice, Bob and Cath each hold one card, then Cath learns the entire deal from Alice’s announcement of her card. The following proposition is a special case of a similar proposition in [1]. Proposition 3 (Reduction) For n≥d, if the announcement of nAis secure for deals of size (a, b, c), then the announcement of nAis also secure for deals of size (a, b, c)with c≤c. Proof: If for some card deal of size (a, b, c), after the announcement of nA,Cath knows some of Alice or Bob’s cards, then this would be also the case for the card deal of size (a, b, c) in which Cath additionally holds c−c(new) cards (a+b+c),(a+b+c+1),...,(a+b+c−1) and where it is publicly known that she holds these additional cards.  4 The number-of-cards modulo-sum announcement The case of the n-ModSum protocol where n=d, i.e., the total number of cards, we give a special name. Definition 4 (DModSum)The number-of-cards modulo-sum (DModSum)protocol is that where Alice and Bob announce the sum of their respective cards modulo d. 168 A. CORD ´ ON-FRANCO ET AL. With the following lemmas, we will work our way towards the main result of this section that for card deals of size (a, b, 1) with a+b+ 1 prime, announcing dAis secure for a, b > 2 (Corollary 9). (Given these results, they dually hold for dBas well.) Lemma 5 Let t, d be natural numbers with 0<t<d−2and x∈Z/(d).Then, there exists T⊆Z/(d)with |T|=tand T=x. Proof: There are at least d−4 2pairs of the form {c, −c}with c=−cand c=±x (where −cstands for d−c). The reason for this is that the only elements that do not belong to one such pair are 0, x,−xand, if dis even, d/2. Let c1,−c1,... be an enumeration of all these pairs. Then, if tis odd we can take Tt={x}∪ci,−ci:i≤t−1 2 where we note that t−1 2≤d−4 2because t<d−2, and that |Tt|=t, indeed. Otherwise (if tis even), take Tt=Tt−1∪{0}. Proposition 6 Announcing dA(or, equivalently, dB) is secure for all deals of size (a, b, c)if and only if, for any value of 0≤x<dand any set S⊂Dof a+b−1 cards, there are A, B ⊂Ssuch that |A|=a,|B|=band dA=dB=x. Proof: First let us prove the ‘if’ direction, and assume the right-hand condition holds. Suppose that Alice announces dAand zis any card that Cath does not hold. We must show that Cath cannot determine whether Alice or Bob holds z. Consider the set S=D\(C∪{z}). This set has a+b−1 elements. Now, pick A⊂Ssuch that dA=dAand |A|=a. In the deal where Alice holds A, she does not hold zyet the sum of her cards is still dA, so Cath cannot distinguish between this scenario and the current one. Therefore Cath cannot correctly conclude that Alice holds z. Similarly, we can pick B⊂Swith |B|=band and dB=dB. Again Cath cannot distinguish between this deal and the original deal (since the sum of Alice’s cards does not change either), and Bob does not hold zin this new deal. Hence, Cath cannot correctly conclude that Bob holds z. For the other direction, suppose that there is 0 ≤x<dand a particular set Sof a+b−1 cards such that there does not exist A⊂Swith |A|=aand dA=x.We must show that announcing dAis not always secure. (The situation is symmetric if the condition fails for binstead of a, so we only treat this case.) For such an Sthere exists a minimal subset T⊂D\Ssuch that there is A⊂S∪T with |A|=aand dA=x(Lemma 5 guarantees that at least one such set exists, and therefore there is a minimal one). Observe that |S∪T|≥a+bas Tis not empty and necessarily T⊆A, because of the minimality of T. Then, consider any A SECURE ADDITIVE PROTOCOL 169 deal (A, B, C) where Bis an arbitrary subset of S∪T\Aand Cis the rest of the cards. In that deal, if Alice announces that dA=xthen Cath knows that all the cards in Tbelong to Abecause all the cards that Cath does not hold are in S∪T and the only way of forming a set of acards with sum xis by using all the cards in T(this by minimality). Therefore the announcement of dAis not secure, since Cath would learn at least one of Alice’s cards. If the corresponding condition for bfails, then by the same argument Cath would learn one of Bob’s cards. In either case we conclude that the announcement of dAis not secure.  To obtain our main result, Theorem 8, we now combine this proposition with a combinatorial theorem, conjectured by Erd¨os and Heilbronn in [4] and proven by Dias da Silva and Hamidoune in [3]: Proposition 7 ([3]) Let dbe a prime. For a set A⊆Z/(d),denotebySn(A)the set of all sums x1+···+xnof ndistinct elements of A.Then, |Sn(A)|≥min{d, n|A|−n2+1}. Theorem 8 (Security) If a+b+cis prime, then announcing dA(or dB)is secure for all deals of size (a, b, c)if and only if ab −2a−b−c+1 ≥0and ab −2b−a−c+1 ≥0 Proof: By Proposition 6 we need that any set Xof a+b−1 cards has subsets of size aand bwhich sum up to all the possible values from 0 to d−1. This condition holds for awhenever |Sa(X)|=d, which in turn holds whenever a|X|−a2+1≥d, that is, when a(a+b−1) −a2+1≥a+b+c. Some simplification takes this inequality to the form displayed above. Note that the bound is tight because the inequality in Proposition 7 is also tight; we have that |Sa({1,2,...,a+b−1})|=a(a+b−1) −a2+1, so if the latter is less than dwe have that the announcement of dAis not always secure (by the ‘only if’ direction of Proposition 6). A similar analysis shows that the second inequality is equivalent to Cath always being ignorant of Bob’s cards.  170 A. CORD ´ ON-FRANCO ET AL. Corollary 9 In deals of size (a, b, 1) with a+b+1 prime, announcing dAis secure if and only if a, b > 2. Proof: When c= 1, the requisites in Theorem 8 are satisfied if and only if a, b > 2.  This gives us a full characterization for when the DModSum protocol works when c=1anddis prime. In the following section we will show how one can deal with non-prime values of d. 5 The least-prime modulo-sum announcement The least-prime modulo-sum protocol is the n-ModSum protocol for nthe least prime greaterthanorequaltod. In this section we show that for c=1anda, b ≥3 except for a=4,b=3anda=3,b= 4 the least-prime modulo-sum protocol is secure. Consider a card deal with size parameters (a, b, c). Definition 10 (LPModSum)The LPModSum (‘least-prime modulo-sum’) protocol is as follows: Alice and Bob announce the sum of their cards modulo p,wherepis the least prime greater than or equal to a+b+c. We are now ready to obtain our result for the LPModSum protocol for (a, b, 1). The idea is to find some appropriate c≥1 such that a+b+cis prime and (a, b, c)satisfies the conditions of the Security Theorem 8, then apply the Reduction Proposition 3. First we need the following properties on the distribution of primes: Proposition 11 (Bertrand’s postulate, [10]) For each n>3, there is always a prime psuch that n<p<2n−2. Proposition 12 (Nagura’s theorem, [9]) For each n>24, there is always a prime psuch that n<p<6 5n. Theorem 13 For all a, b ≥3except for a=4,b =3and a=3,b =4,the LPModSum protocol is secure for size (a, b, 1). Proof: We may assume that a≥b, as security for (a, b, c) entails security for (b, a, c). Case 1:b>3. Case 1.1:a+b+ 1 is prime. Then, the DModSum and the LPModSum protocols coincide and so the security of the protocol follows from Corollary 9. Case 1.2:a+b+1isnotprime. Let pbe the least prime number greater than a+b+ 1 and put c=p−(a+b). By Bertrand’s postulate for n=a+bwegetthatthereisaprimeqsuch that A SECURE ADDITIVE PROTOCOL 171 a+b<q<2(a+b)−2 and hence p≤2(a+b)−3. Then, a+b+cis prime and it is easy to check that (a, b, c) satisfies the conditions of the Security Theorem 8 (observe that we only need to verify the first condition since we are assuming a≥b). Namely, ab −2a−b−c+1 = ab −2a−b−(p−(a+b)) + 1 =ab −a−p+1 ≥ab −a−(2(a+b)−3) + 1 =ab −3a−2b+4. Case A:b≥5. Then, we have (recall that a≥b): ab −3a−2b+4≥ab −3a−2a+4=ab −5a+4≥5a−5a+4=4≥0. Case B:b=4. Then, we have (recall that a≥b=4): ab −3a−2b+4=4a−3a−8+4=a−4≥0. So, it follows from the Security Theorem 8 that the modulo-sum protocol is secure for size (a, b, p −(a+b)) and then the least-prime modulo-sum protocol for size (a, b, 1) is also secure by the Reduction Proposition 3. Case 2:b=3. Case 2.1:a+ 4 is prime. Then, the DModSum and the LPModSum protocols coincide and so the security of the protocol follows from Corollary 9. Case 2.2:a+4isnotprime. Let pbe the least prime number greater than a+4 and put c=p−(a+3). Reasoning as in case 1.2, it follows from Bertrand’s postulate that p≤2a+ 3. Nevertheless, now this upper bound for pdoes not allow us to verify that the conditions of the Security Theorem 8 hold for size (a, 3,c). Namely, ab −2a−b−c+1 = 3a−2a−3−(p−(a+3))+1 =2a−p+1 ≥2a−(2a+3)+1 = −2. However, observe that in order to obtain a value greater than or equal to 0 in the calculation above it would suffice to improve our upper bound on the prime pto p≤2a+ 1. We will be able to do this by using Nagura’s theorem for a>21 and by inspection for 4 <a≤20.