A geometric protocol for cryptography with cards

A geometric protocol for cryptography with cards Andr´es Cord´on–Franco, Hans van Ditmarsch, David Fern´andez–Duque, and Fernando Soler–Toscano∗ October 3, 2018 Abstract In the generalized Russian cards problem, the three players Alice, Bob and Cath draw a, b and ccards, respectively, from a deck of a+b+ccards. Players only know their own cards and what the deck of cards is. Alice and Bob are then required to communicate their hand of cards to each other by way of public messages. The communication is said to be safe if Cath does not learn the ownership of any specific card; in this paper we consider a strengthened notion of safety introduced by Swanson and Stinson which we call k-safety. An elegant solution by Atkinson views the cards as points in a finite projective plane. We propose a general solution in the spirit of Atkinson’s, although based on finite vector spaces rather than projective planes, and call it the ‘geometric protocol’. Given arbitrary c, k > 0, this protocol gives an informative and k-safe solution to the generalized Russian cards problem for infinitely many values of (a, b, c) with b=O(ac). This improves on the collection of parameters for which solutions are known. In particular, it is the first solution which guarantees k-safety when Cath has more than one card. ∗Email: {acordon,hvd,dfduque,fsoler}@us.es. Affiliation: University of Sevilla, Spain. Affiliation Hans v.D.: LORIA, France, and (as research associate) IMSc, India. 1 1 Introduction The generalized Russian cards problem [1, 14] is a family of combinatorial puzzles about secure secret-sharing between card players. It is parametrized by a triple of natural numbers (a, b, c), which we call its size, and can be stated as follows: The generalized Russian cards problem Alice, Bob and Cath each draw a, b and ccards, respectively, from a deck containing a total of a+b+c. All players know which cards were in the deck and how many of them the other players drew, but may only see the cards in their own hand. Alice and Bob want to know exactly which cards the other holds. Meanwhile, they do not want for Cath to learn who holds any card whatsoever, aside of course from her own cards. However, they may only communicate by making true, clear, public announcements, so that Cath can learn all the information that they exchange. Can Alice and Bob achieve this? The solutions to this problem are given by protocols. The eavesdropper Cath is able to hear all communications, and Alice and Bob (and Cath) are aware of that. In such information-exchanging protocols between Alice and Bob, Cath typically acquires quite a bit of data, but not enough to be able to deduce any secrets. Many protocols have been proposed [1, 2, 14], and cryptography based on card deals is also investigated in other settings [5, 11, 12], yet it remains unknown exactly for which triples (a, b, c) the problem can be solved. The goal of this article is to present a new protocol based on finite linear algebra, inspired by a protocol based on projective geometry by Atkinson that was reported in [1], and that we present in Section 2. This geometric protocol solves the generalized Russian cards problem in many instances that were previously unsolved. Also, it employs a stronger notion of security than is often considered, which we call k-safety and is equivalent to weak k-security in [14]. Some general assumptions are needed to make the problem precise, which we shall formalize in Section 3, along with the notion of protocol. First, the cards are dealt beforehand in a secure phase which we treat as a black box 2 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. This means, on one hand, that solutions via encryption are not valid, provided they are vulnerable to cryptanalysis (regardless of its difficulty). It also means that we shall not be concerned with the feasibility of agents’ strategies, although this is certainly an interesting line for future inquiry. Third, all strategies are public knowledge, keeping with Kerkhoffs’ principle [6]. 1.1 Known solutions Many solutions consist of two announcements. First, Alice announcess of a number of possible hands she may hold; then, Bob discloses Cath’s cards (or other equivalent information). Atkinson’s solution is for the case (3,3,1) and consists of viewing the cards as points in a projective plane, in such a way that Alice holds a line. She then announces the seven lines of that plane, i.e., seven triples of cards. This protcol is presented in [1], along with many incidental results, and will be discussed further in Section 2. The size (3,3,1) was first considered by Kirkman [7], who suggests a solution using a design, a collection of subsets of a given set that satisfies certain regulaties [13]. The design consists of seven triples — and accidentally these are the lines that form the projective geometric plane. A possibly better-known solution for (3,3,1) is to number the cards 0,...,6, after which Alice and Bob announce the sum of their cards modulo 7 (i.e., modulo the number of cards in the pack). This was the proposed solution when the problem appeared in the Moscow Mathematics Olympiad in 2000, from which it earned its current name [9]; a very similar approach works in any case where Cath holds only one card and a, b > 2 [2]. A protocol of three announcements for (4,4,2) is reported in [16], and a four-step protocol for c=O(a2) and b=O(c2) is presented in [3]. The last two are notable because they provide solutions for c > 1 and neither can be solved with two-announcement protocols. Stronger notions of security are studied by Swanson and Stinson in [14]. There, a distinction is made between weak and perfect security; in perfectly secure protocols, Cath does not acquire any probabilistic information about the ownership of any specific card. They also introduce k-secure protocols, where tuples of at most kcards are considered simultenously. They then characterize the perfect (k−1)-secure solutions for sizes (a, b, a −k) and 3 show that k=a−1 and c= 1. These notions will be revisited in Section 3, but we remark that the protocol we shall present is weakly k-secure. 1.2 Plan of the paper In Section 2 we give an informal description of the protocol. Section 3 formalizes our model of security and our notion of protocol, so that in Section 4 we may give a rigorous specification. The protocol depends on several parameters and is only executable under certain constraints; Section 5 computes solutions to these constraints. 1.3 Finite geometry We assume some basic familiarity with finite fields and finite geometry; these are covered in texts such as [8] and [4], respectively. Throughout the paper, pwill 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. Given sets U, V ⊆Fd pwe write hUifor the span of U(i.e., the set of all linear combinations of elements of U), and we write U+Vfor the set {u+v:u∈Uand v∈V}. We may write x+V instead of {x}+V, and similarly hx, Uiinstead of h{x}∪Ui. By a hyperplane we mean any set of the form x+Vwhere Vis a subspace of dimension d−1, and two hyperplanes X, Y are parallel if X6=Ybut there is a vector xsuch that X=x+Y. Recall that |Fd p|=pd, where |X|denotes the cardinality of X. Moreover, if U6=Vare hyperplanes, then Uhas exactly pd−1elements, while |U∩V| ≤ pd−2. Parallel hyperplanes have empty intersection. 2 Motivating examples Let us begin by presenting Atkinson’s solution for the case (3,3,1). In this setting, Alice and Bob each draw three cards from a deck of seven cards, while Cath gets the remaining card. The claim is that Alice and Bob can communicate their cards to each other by way of public announcements, without informing Cath of any of their cards. First, Alice announces that her hand is a line in a projective plane consisting of seven points (cards). Or, to be precise, Alice assigns a point in the projective plane to each card in 4 such a way that her own hand forms a line, and then announces “The hand I hold is one of the following. . . ,” after which she proceeds to list every set of cards which corresponds to a line. Then, to conclude the protocol, Bob announces Cath’s card. • 0 • 1 • 2 •4 • 5 • 6 •3 Figure 1: Alice holds a line in the 7-point projective plane Why does this work? Suppose that the cards are numbered 0,1,...,6, that Alice holds the cards 0, 1 and 2, Bob holds 3, 4, and 5, and therefore Cath holds 6. Alice announces: “My cards form a line in the projective plane whose lines are 012, 034, 056, 135, 146, 236, and 245.” (See Figure 1.) Bob then announces: “Cath holds 6.” After Alice’s announcement, Cath, who holds card 6, can eliminate from the seven triples the ones containing 6: 056, 146, and 236. The remaining hands are: 012, 034, 135 and 245. Cath therefore cannot deduce that Alice has 0, because 135 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. And so on, for all possible cards of Alice. Also—and this is important—for any other deal of cards in which Alice can truthfully make this announcement we can repeat this exercise, e.g., also when Alice holds 012 and Cath 4, also when Alice holds 135 and Cath 0, and so on. Meanwhile, Bob learns Alice’s cards from her announcement, because all but 012 contain either a 3, a 4, or a 5. Again, we have to do this for all card triples xyz, not just for Bob’s actual hand 345, and also for all seven possible hands of Alice and all hands Bob can have in that case. After Alice’s announcement Bob therefore always knows Cath’s card and can announce it, 5 from which Alice also learns the entire deal of cards. Let us give an informal account of the geometric protocol to motivate the formal description later. It is similar to Atkinson’s, but there are three main differences: 1. Projective spaces are replaced by vector spaces; in fact, the original protocol is not dependent on any particular property of projective spaces that they do not share with vector spaces. 2. Rather than considering exclusively planes, we work over spaces of arbitrary dimension, so that in general Alice arranges her cards on a hyperplane. 3. Alice may have more cards than fit on a single hyperplane. Thus she shall arrange her cards on several parallel hyperplanes. The protocol works as follows. Fix a size (a, b, c) such that there are integers d, k > 0 and a prime power pwith a=kpdand a+b+c=pd+1. Suppose that (A, B, C) has been dealt, and that D=A∪B∪C. Alice chooses a map f:D→Fd+1 p, such that Ais the disjoint union of kparallel hyperplanes. Then, she announces the set Aof all hands Xwith aelements such that f(X) has this form; in other words: such that Xmaps to the disjoint union of kparallel hyperplanes. In Section 4, in Definition 3.1, we shall give a more rigorous definition of this protocol, and we then also show this protocol to be k-safe, provided the parameters satisfy certain constraints; k-safe means that for any kcards not held by Cath, she cannot learn whether Alice all holds them (i.e., if she holds all those cards or does not hold some of them). In that sense, the above projective plane solution for (3,3,1) is 1-safe. But first, let us focus on a specific instance to see the protocol in action. Consider a card deal of size (8,6,2), so that there are 16 cards, of which Alice holds eight, Bob six and Cath two. For this example we will work over F2 4; note that the field F4has elements {0,1, α, α2}where αis a root of x2+x+ 1. In order to execute the geometric protocol, Alice first announces that her cards are two parallel lines in F2 4; after this, Bob informs Alice of Cath’s cards. Let us see why this protocol works. The deck Dmay be any set with 16 elements. The only thing that matters is a bijection f:D→F2 4, where we represent F2 4as {(i, j)|i, j ∈ {0,1, α, α2}}. 6 0 1 Α Α² 0 1 Α Α² 0 1 Α Α² 0 1 Α Α² 0 1 Α Α² 0 1 Α Α² Figure 2: Card deals in F2 4 Why does this bijection inform Bob of Alice’s cards? Consider the configuration in Figure 2 (left), where Alice’s cards are represented as , Bob’s as #and Cath’s as N. This two-dimensional plane F2 4consists of 20 lines (hyperplanes), such as the four horizontal and the four vertical lines in the figure. The other three foursomes are somewhat less obvious to visualize based on this representation; for example, the line x=yis given by the set L={(0,0),(1,1),(α, α),(α2, α2)}, whereas the parallel line (0, α2) + L is given by {(0, α2),(1, α),(α, 1),(α2,0)}. Just as for (3,3,1) and the sevenpoint projective plane, Alice’s announcement rules out some possibilities for her hand, as not every set of eight points includes two parallel lines. Alice’s announcement is sufficient for Bob to determine Alice’s hand. Suppose that A,B,Care the sets of cards that Alice, Bob and Cath hold, respectively. Then, A∪Ccontains ten points, and thus cannot contain two different pairs of parallel lines, as the minimum set to contain different pairs of parellel lines is twelve points. In Figure 2 (left), A∪Ccontains three lines, namely the two verticals and the one horizontal, but only one pair of parallel lines. More generally, one can check no set of ten points contains two distinct pairs of parallel lines. On the other hand, it is not merely the case that Cath, who holds points (cards) (1,1) and (α2,1), cannot determine the ownership of a single card not in her possession, but it is even the case that for every pair {x, y}of points, Cath considers it possible that {x, y} ⊆ Aand that {x, y} 6⊆ A. In other words, the protocol is 2-safe; for example, consider the pair {(α2,0),(α2, α)}. In Figure 2 (left) these cards are held by Bob, but in Figure 2 (center) these cards are held by Alice. From Cath’s perspective, the card deal (A0, B0, C) depicted in the center, where {(α2,0),(α2, α)} ⊆ A0, is indistinguishable from the card deal (A, B, C) on the left, where {(α2,0),(α2, α)} 6⊆ A, even though {(α2,0),(α2, α)} ∩ A=∅. This can be verified systematically for all pairs 7 and indeed Cath cannot learn any of Alice’s cards, or even predict that Alice holds a card from any given pair. However, if Cath has three cards then she may learn some of Alice’s cards. Consider Figure 2 (right). Cath learns that the point (α2, α2) belongs to Bob, as there is no pair of parallel lines in A∪Bsuch that one of them contains (α2, α2), for any such pair of lines would cross the line x=α2in two different points, and Cath would hold one of them. If she has even more than three cards this only gets worse; indeed, it is known that no two-step protocol can be safe and informative when Cath holds as many as or more cards than Alice1[1]. 3 Protocols and safety Before we continue let us present the notions of protocol, informativity and safety we shall use. Throughout this paper, we will 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. We denote the set of x-subsets of Yby 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). In [14] 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, and we follow this presentation. A characteristic assumption of the problem is that there is a secure dealing phase in which the players learn no information about others’ cards, encrypted or otherwise. At the beginning of the protocol, players have knowledge of their own cards, the cards contained in D, and of the size (a, b, c) of the deal, but nothing more. 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 may define analogous equivalence relations for Bob and Cath. 1Note however that this restriction may be circumvented by using protocols of more than two steps [3]. 8 Strategies of length two are defined in [14]. These assign a probability distribution to Alice’s possible announcements. If the probability distribution is uniform these are called equitable strategies. We will work exclusively with equitable strategies, and simply call them protocols. Since probability is distributed evenly among the possible outcomes, we may dispense with probability measures and merely specify a set of possible announcements. Definition 3.1 (Protocol).Fix a size (a, b, c)and let D={1, . . . , a +b+c}. Aprotocol (for (a, b, c)) is a function πassigning to each A∈D aa nonempty set π(A)⊆ P D a with the property that A∈Tπ(A). Protocols are non-deterministic in principle; Alice may announce any A ∈ π(A). Meanwhile, a successful protocol must have two additional properties. The first is that Alice and Bob know each other’s cards (and hence the entire deal) after its execution. Note that it is sufficient for Bob to learn the deal since, once Bob knows Alice’s hand, he also knows Cath’s and may proceed to announce C. Because of this, the protocols we present are in principle two-step protocols, even though we only focus on Alice’s announcement and leave Bob’s second announcement implicit. Definition 3.2 (Informativity).Given a deal (A, B, C), an announcement A is informative for (A, B, C)if there is only one X∈ A such that X⊆A∪C. A protocol for (a, b, c)is informative if for every (A, B, C)∈Deal(a, b, c), every A ∈ π(A)is informative for (A, B, C).2 The second property we desire from a protocol is that Cath does not gain “too much information”. How much is too much depends on a parameter we shall usually call kand states that, given X∈D k, it is possible from Cath’s perspective that X⊆Aand also possible that X6⊆ A. This is the notion of weak k-security from [14]; we simply call it k-safety. Definition 3.3 (k-Safety).Given a protocol πfor (a, b, c)and A∈D a, an announcement A ∈ π(A)is k-safe if for every deal (A, B, C)and every nonempty set Xwith at most kelements such that X∩C=∅there is a deal 2Our presentation follows that given in [14]. Compare to [15, 1], where informative for (A, B, C) is defined as follows: Given a deal (A, B, C), an announcement Acontaining Ais informative for (A, B, C)if for any A0∈ A and any (A0, B0, C0), there is only one X∈ A such that X⊆A0∪C0.In principle this is stronger than the definition we give; however, this is remedied by the more general condition of being informative for (a, b, c). 9 To see that condition (1) holds, it suffices in view of Lemma 5.1 to observe that c < p −1≤pd−1(p−1) = pd−pd−1. Meanwhile, condition (2) holds by the way we chose p. It follows from Theorem 4.1 that the geometric protocol is informative and k-safe for (a, b, c), as claimed. 6 Conclusions and future work The generalized Russian cards problem, aside from being interesting from a purely combinatorial perspective, provides a prototypical case-study for information-based cryptography [10]. This alternative paradigm is based on the impossibility, rather than the improbability, of encrypted messages being intercepted. Information-based cryptography has the advantage over probability-based cryptography that it does not depend on eavesdroppers’ computational resources or, for example, the assumption that P6=NP. However, such methods are less developed, and for good reason, as the demand that protocols be unconditionally secure is rather strong. Also, they depend on a prior phase of key-distribution (‘dealing the cards’) by some central authority, that is assumed to be perfectly secure. Nevertheless, solutions to the generalized Russian cards problem could very well lead, directly or indirectly, to applications in information-theoretic methods of secure communication. In this paper we have given improved bounds for the tuple (a, b, c) to have an informative and k-safe solution. The notion of k-safety was originally considered by Stinson and Swanson in [14], where k-safe protocols are given for many cases where Cath has one card. Perhaps the main contribution of the present work is that the protocol we present gives the first k-safe solutions for c > 1. Stinson and Swanson also introduce perfect security. This strengthened notion of security may yet be extended to many new cases, for in the methods we propose (and most that are available in the literature), there is no guarantee that Cath does not learn additional probabilistic information. It may be possible to amend the geometric protocol to achieve either perfect security or, more likely, an approximate variant, where the probabilistic information that Cath learns is minimal. Finally, the authors have presented in [3] a method which allows Cath to have more cards than Alice, which we call the colouring protocol. It is 16 known that such a protocol must have more than two steps; ours has four. In principle, the present geometric protocol may be combined with the colouring protocol to give k-safe solutions when Cath has many more cards than Alice, although the combinatorial analysis is likely to be rather challenging. These are possible avenues to explore in future work; however, the Russian cards problem allows for a large degree of freedom and it may very well be that entirely new and better methods shall be developed to obtain more efficient and secure protocols. 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–176, 2012. [3] A. Cord´on-Franco, H. van Ditmarsch, D. Fern´andez-Duque, and F. Soler-Toscano. A colouring protocol for the generalized Russian cards problem. ArXiv, 1207.5216 [cs.IT], 2012. [4] P. Dembowski. Finite Geometries (reprint). Springer, 1997. [5] M.J. Fischer and R.N. Wright. Bounds on secret key exchange using a random deal of cards. Journal of Cryptology, 9(2):71–99, 1996. [6] A. Kerckhoffs. La cryptographie militaire. Journal des sciences militaires, IX:5–38 and 161–191, 1883. [7] T. Kirkman. On a problem in combinations. Cambridge and Dublin Mathematics Journal, 2:191–204, 1847. [8] R. Lidl. Finite Fields. Cambridge University Press, 1997. [9] K.S. Makarychev and Yu.S. Makarychev. The importance of being formal. Mathematical Intelligencer, 23(1):41–42, 2001. 17 [10] 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. [11] 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. [12] A. Stiglic. Computations with a deck of cards. Theoretical Computer Science, 259(1–2):671–678, 2001. [13] D.R. Stinson. Combinatorial Designs – Constructions and Analysis. Springer, 2004. [14] C. M. Swanson and D. R. Stinson. Combinatorial solutions providing improved security for the generalized Russian cards problem. ArXiv, 1207.1336 [math.CO], 2012. [15] H. van Ditmarsch. The Russian cards problem. Studia Logica, 75:31–62, 2003. [16] 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. 18