A geometric protocol for cryptography with cards

Abstract

In the generalized Russian cards problem, the three players Alice, Bob and Cath draw $a,b$ and $c$ cards, respectively, from a deck of $a+b+c$ cards. 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. For a natural number $k$, the communication is said to be $k$-safe if Cath does not learn whether or not Alice holds any given set of at most $k$ cards that are not Cath’s, a notion originally introduced as weak $k$-security by Swanson and Stinson. 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.

1 Introduction

The generalized Russian cards problem [1, 17] 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 $c$ cards, 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, 3, 17], and cryptography based on card deals is also investigated in other settings [6, 13, 14], 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 Sect. 2. This geometric protocol solves the generalized Russian cards problem in many instances that were previously unsolved. It employs a stronger notion of security than is often considered, which we call $k$-safety and is equivalent to weak $k$-security in [17]; given a set of at most $k$ cards which Cath does not hold, Cath should consider it possible that Alice holds all of them, but also consider it possible that Bob holds at least one of them (a precise definition shall be given in Sect. 3). Our main results show that, given $c,k\ge 1$, the geometric protocol is informative and $k$-safe for $(a,b,c)$ for infinitely many values of $a,b$ with $b<2a(c+1)$, with the smallest such value of $a$ being at most $2k(kc+1)$. More precisely, there must exist a prime power $p$ and $d>0$ such that $a+b+c=p^{d+1}$, $c<kp^{d}-k^2p^{d-1}$ and $\max \{c+k,ck\}\le p$.

Some general assumptions are needed to make the problem precise, which we shall formalize in Sect. 3, along with the notion of protocol. 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 eavesdropper has unlimited computational capacity. This means that solutions via encryption are not valid, provided they are vulnerable to cryptanalysis (regardless of its difficulty). Third, all strategies are public knowledge, keeping with Kerkhoffs’ principle [8].

1.1 Known solutions

Many solutions consist of two announcements. First, Alice announces a number of possible hands she may hold; then, Bob discloses Cath’s cards (or other equivalent information). Although the problem may be regarded as purely combinatorial or epistemic, it is often fruitful to import techniques from other fields such as geometry or algebra. 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 Sect. 2. The size (3,3,1) was first considered by Kirkman [9], who suggests a solution using a design, a collection of subsets of a given set that satisfies certain regulaties [15]. The design consists of seven triples—which incidentally are precisely the lines that form the projective geometric plane.

A possibly better-known solution for (3,3,1) is to number the cards $0,\ldots ,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 [11]; a very similar approach works in any case where Cath holds only one card and $a,b>2$ [3]. A protocol of three announcements for (4,4,2) is reported in [19], and a four-step protocol for $c=O(a^2)$ and $b=O(c^2)$ is presented in [4]. 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 [17]. 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 $k$ cards are considered simultaneously. They then characterize the perfect $(k-1)$-secure solutions for sizes $(a,b,a-k)$ and show that $k=a-1$ and $c=1$. These notions will be revisited in Sect. 3, but we remark that the protocol we shall present is weakly $k$-secure.

1.2 Plan of the paper

In Sect. 2 we give an informal description of the protocol. Section 3 formalizes our model of security and our notion of protocol, so that in Sect. 4 we may give a rigorous specification. The protocol depends on several parameters and is only $k$-safe and informative under certain constraints, specified in Theorem 1; Sect. 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 [10] and [5], respectively.

Throughout the paper, $p$ will denote a prime or a power of a prime, and $\mathbb F _p$ the field with $p$ elements. If $d$ is any natural number, $\mathbb F ^d_p$ denotes the vector space of dimension $d$ over $\mathbb F _p$. Given sets $U,V\subseteq \mathbb F ^d_p$ we write $\langle U\rangle$ for the span of $U$ (i.e., the set of all linear combinations of elements of $U$), and we write $U+ V$ for the set $\{u+v:u\in U \text{ and } v\in V\}$. We may write $x+ V$ instead of $\{x\}+ V$, and similarly $\langle x,U\rangle$ instead of $\langle \{x\}\cup U\rangle$. By a hyperplane we mean any set of the form $x+V$ where $V$ is a subspace of dimension $d-1$, and two hyperplanes $X,Y$ are parallel if $X\not =Y$ but there is a vector $x$ such that $X=x+Y$.

Recall that $|\mathbb F ^d_p|=p^d$, where $|X|$ denotes the cardinality of $X$. Moreover, if $U\not =V$ are hyperplanes, then $U$ has exactly $p^{d-1}$ elements, while $|U\cap V|\le p^{d-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 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.

Fig. 1

Alice holds a line in the 7-point projective plane

Why does this work? Suppose that the cards are numbered $0, 1, \ldots , 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 Fig. 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, 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 $p$ with $a=kp^{d}$ and $a+b+c=p^{d+1}$. Suppose that $(A,B,C)$ has been dealt, and that $D = A \cup B \cup C$. Alice chooses a map $f:D\rightarrow \mathbb F ^{d+1}_p$, such that $A$ is the disjoint union of $k$ parallel hyperplanes. Then, she announces the set $\mathcal A$ of all hands $X$ with $a$ elements such that $f(X)$ has this form; in other words: such that $X$ maps to the disjoint union of $k$ parallel hyperplanes.

In Sect. 4, in Definition 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 $k$ cards 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 $\mathbb F ^2_4$; the field $\mathbb F _4$ has elements $\{0,1,\alpha ,\alpha ^2\}$ where $\alpha$ is a root of $x^2+x+1$. Note that $k=2$, since Alice holds eight cards. In order to execute the geometric protocol, Alice first announces that her cards are two parallel lines in $\mathbb F ^2_4$; after this, Bob informs Alice of Cath’s cards.

Let us see why this protocol works. The deck $D$ may be any set with 16 elements. The only thing that matters is a bijection $f:D\rightarrow \mathbb F ^2_4$, where we represent $\mathbb F ^2_4$ as $\{({i},{j}) \mid i,j\in \{0,1,\alpha ,\alpha ^2\} \}$.

Fig. 2

Card deals in $\mathbb F ^2_4$

Why does this bijection inform Bob of Alice’s cards? Consider the configuration in Fig. 2 (left), where Alice’s cards are represented as $\blacksquare$, Bob’s as $\bigcirc$ and Cath’s as $\blacktriangle$. This two-dimensional plane $\mathbb F ^2_4$ consists 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=y$ is given by the set $L=\{({0},{0}),({1},{1}),({\alpha },{\alpha }),({\alpha ^2},{\alpha ^2})\}$, whereas the parallel line $({0},{\alpha ^2})+L$ is given by $\{({0},{\alpha ^2}),({1},{\alpha }),({\alpha },{1}),({\alpha ^2},{0})\}$. Just as for (3,3,1) and the seven-point 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$, $C$ are the sets of cards that Alice, Bob and Cath hold, respectively. Then, $A\cup C$ contains ten points, and thus cannot contain two different pairs of parallel lines, as the minimum set to contain different pairs of parallel lines is twelve points. In Fig. 2 (left), $A\cup C$ contains 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 $({\alpha ^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\}\subseteq A$ and that $\{x,y\}\not \subseteq A$. In other words, the protocol is 2-safe; for example, consider the pair $\{({\alpha ^2},{0}),({\alpha ^2},{\alpha })\}$. In Fig. 2 (left) these cards are held by Bob, but in Fig. 2 (center) these cards are held by Alice. From Cath’s perspective, the card deal $(A^{\prime },B^{\prime },C)$ depicted in the center, where $\{({\alpha ^2},{0}),({\alpha ^2},{\alpha })\}\subseteq A^{\prime }$, is indistinguishable from the card deal $(A,B,C)$ on the left, where $\{({\alpha ^2},{0}),({\alpha ^2},{\alpha })\}\not \subseteq A$, even though $\{({\alpha ^2},{0}),({\alpha ^2},{\alpha })\}\cap A = \varnothing$. This can be verified systematically for all pairs 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 Fig. 2 (right). Cath learns that the point $({\alpha ^2},{\alpha ^2})$ belongs to Bob, as there is no pair of parallel lines in $A\cup B$ such that one of them contains $({\alpha ^2},{\alpha ^2})$, for any such pair of lines would cross the line $x=\alpha ^2$ in 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 Alice¹ [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 $D$ is 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 $A$ is an $a$-set, $B$ a $b$-set and $C$ a $c$-set, where by “$x$-set” we mean a set of cardinality $x$. We denote the set of $x$-subsets of $Y$ by $\left( \begin{array}{l} Y\\ x\end{array}\right)$. We think of $A$ as the hand of Alice, or that Alice holds $A$; similarly, $B$ and $C$ are the hands of Bob and Cath, respectively. In general we may simply assume that $D=\{1,\ldots ,a+b+c\}$, and define $\mathrm{Deal}(a,b,c)$ to be the set of partitions of $D$ of size $(a,b,c)$. In [17] 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 $\mathcal A$ of $\left( \begin{array}{l}D\\ a\end{array}\right)$, indicating that $A\in \mathcal 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,B^{\prime },C^{\prime })$, we define $(A,B,C)\stackrel{Alice}{\sim }(A^{\prime },B^{\prime },C^{\prime })$ if and only if $A=A^{\prime }$. We may define analogous equivalence relations for Bob and Cath.

Strategies of length two are defined in [17]. These assign, to each hand that Alice may hold, a probability distribution on the set of possible announcements. If the probability distribution is uniform we will call these uniform strategies. We will work exclusively with uniform 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 1

(Protocol) Fix a size $(a,b,c)$ and let $D=\{1,\ldots ,a+b+c\}$. A protocol (for $(a,b,c)$) is a function $\pi$ assigning to each $A\in {\left( \begin{array}{l}D\\ a\end{array}\right) }$ a non-empty set $\pi (A)\subseteq \mathcal P \left( {\left( \begin{array}{l}D\\ a\end{array}\right) }\right)$ with the property that $A\in \bigcap \pi (A)$.

Protocols are non-deterministic in principle; Alice may announce any $\mathcal A \in \pi (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 2

(Informativity) Given a deal $(A,B,C)$, an announcement $\mathcal A$ is informative for $(A,B,C)$ if there is only one $X\in \mathcal A$ such that $X\subseteq A\cup C.$

A protocol for $(a,b,c)$ is informative if for every $(A,B,C)\in \mathrm{Deal}(a,b,c)$, every $\mathcal A \in \pi (A)$ is informative for $(A,B,C)$.²

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 $k$ and states that, given $X\in {\left( \begin{array}{l}D\\ k\end{array}\right) }$, it is possible from Cath’s perspective that $X\subseteq A$ and also possible that $X\not \subseteq A$. This is the notion of weak $k$-security from [17]; we simply call it $k$-safety.

Definition 3

($k$-Safety) Given a protocol $\pi$ for $(a,b,c)$ and $A\in {\left( \begin{array}{l}D\\ a\end{array}\right) }$, an announcement $\mathcal A \in \pi (A)$ is $k$-safe if for every deal $(A,B,C)$ and every non-empty set $X$ with at most $k$ elements such that $X \cap C=\varnothing$ there is a deal $(A^{\prime },B^{\prime },C)$ such that $X\subseteq A^{\prime }$ and $\mathcal A \in \pi (A^{\prime })$, as well as a deal $(A^{\prime \prime },B^{\prime \prime },C)$ such that $X\not \subseteq A^{\prime \prime }\in \mathcal A$.

The protocol $\pi$ is $k$-safe if every $\mathcal A \in \pi (A)$ is $k$-safe.

A stronger notion of security is also discussed in [17]. Let us use $\mathsf{Pr}(\cdot |\cdot )$ to denote conditional probability. Weak $k$-security is equivalent to the statement that, given a deal $(A,B,C)\in \mathrm{Deal}(a,b,c)$ and a non-empty set $X$ with at most $k$ cards such that $X\cap C=\varnothing$,

$$\begin{aligned} 0<\mathsf{Pr}(X\subseteq A|\mathcal A ,C)<1. \end{aligned}$$

This probability may, however, be very small or very large. A stronger notion of security would demand that Cath does not gain probabilistic information from the protocol, so that for every $(A,B,C)\in \mathrm{Deal}(a,b,c)$ and and every $X\not =\varnothing$ with at most $k$ cards with $X\cap C=\varnothing$,

$$\begin{aligned} \mathsf{Pr}(X\subseteq A|\mathcal A ,C)=\mathsf{Pr}(X\subseteq A|C). \end{aligned}$$

This is called perfect $k$-security and is similar to the combinatorial axiom CA4 in [2]. The protocols we shall present are not perfectly secure, but they are weakly $k$-secure for some fixed value of $k$.

4 The geometric protocol

Here we shall give a formal definition of our protocol in the sense of Definition 1 and prove that it indeed provides a $k$-safe solution to the generalized Russian cards problem.

The protocol is based on slicings:

Definition 4

(Slicing) Let $p$ be a prime power and $k,d$ be positive integers. Say a set $X\subseteq \mathbb F ^{d+1}_p$ is a $k$-slicing if there are a $d$-dimensional subspace $V$ and $x_1,\ldots ,x_k\in \mathbb F ^{d+1}_p$ such that $X=\bigcup _{i=1}^k (x_i+ V)$ and $x_i-x_j\in V$ if and only if $i=j$.

In other words, a $k$-slicing is a union of $k$ parallel hyperplanes. Note that $k$-slicings have exactly $kp^d$ elements.

Definition 5

(The geometric protocol) Fix a size $(a,b,c)$ such that there are integers $d,k$ and a prime power $p$ with $a=kp^{d}$ and $a+b+c=p^{d+1}$. For a bijection $f:D\rightarrow \mathbb F ^{d+1}_p$, define $\mathcal A _k[f]$ to be the set of all $X\subseteq D$ such that $f(X)$ is a $k$-slicing.

We then define the geometric protocol $\gamma$ for $(a,b,c)$ (with parameters $p,d,k$) to be given by $\mathcal A \in \gamma (A)$ if and only if $A\in \mathcal A$ and $\mathcal A =\mathcal A _k[f]$ for some bijection $f:D\rightarrow \mathbb F ^{d+1}_p$.

Our main objective is to show that the geometric protocol provides a $k$-safe and informative solution to the generalized Russian cards problem, but this requires for the parameters to satisfy certain conditions. Although we defer the proof, let us state our main theorem now:

Theorem 1

Assume that $a,b,c,p,d,k$ are such that $p$ is a prime power, $a=kp^{d}$, $a+b+c=p^{d+1}$ and

$$\begin{aligned}&c<kp^{d}-k^2p^{d-1},\end{aligned}$$

(1)

$$\begin{aligned}&\max \{c+k,ck\}\le p. \end{aligned}$$

(2)

Then, the geometric protocol with parameters $p,d,k$ is $k$-safe and informative for $(a,b,c)$.

Before we give a proof, we need to give some preliminary results. These will also help elucidate the purpose of (1) and (2). Note that $\max \{c+k,ck\}$ is usually equal to $ck$ except when either $k$ or $c$ is equal to one. We remark that the bounds given by Theorem 1 are sufficient but not necessary; for example, the assiduous reader will verify that the protocol is 2-safe for (10,12,3), yet the bounds we give are not satisfied.

Let us begin with a combinatorial lemma about slicings.

Lemma 1

Let $p$ be a prime power and $k\in [1,p-1]$. If $X,Y\subseteq \mathbb F ^{d+1}_p$ are two distinct $k$-slicings then

$$\begin{aligned} |X\cup Y|\ge \min \{(k+1)p^{d},2kp^{d}-k^2p^{d-1}\}. \end{aligned}$$

Proof

Write $X=\bigcup _{i=1}^kU_i$ and $Y=\bigcup _{i=1}^k W_i$ as disjoint unions of parallel hyperplanes. It may be that for certain values of $i,j$ we have that $U_i=W_j$. If this is the case, since $X\not =Y$ there must be some $U=U_{i_*}$ such that $U\not =W_j$ for any $j$. Then, since $U$ is parallel to all $W_i$, we have that $U,W_1,\ldots ,W_k$ are mutually disjoint and hence

$$\begin{aligned} (k+1)p^{d}=\left| U\cup \bigcup _{i\le k}W_i\right| \le |X\cup Y|. \end{aligned}$$

Now assume this is not the case, so that $U_i\not =W_j$ for any $i,j\le k$. Then, if $i,j\le k$ we have $|U_i\cap W_j|\le p^{d-1}$, so that

$$\begin{aligned} |X\cup Y|&= \left| \bigcup _{i=1}^k U_i\cup \bigcup _{i=1}^k W_i\right| \\&\ge \sum _{i=1}^k |U_i|+\sum _{i=1}^k |W_i|-\sum _{i,j=1}^k|U_i\cap W_j|\\&\ge kp^d+kp^d-k^2p^{d-1}. \end{aligned}$$

The result follows. $\square$

Lemma 2

Assume that $a,b,c,p,d,k$ are such that $p$ is a prime power, $a=kp^d$, $a+b+c=p^{d+1}$ and

$$\begin{aligned} c<\min \left\{ p^d,kp^d-k^2p^{d-1}\right\} . \end{aligned}$$

Then, the geometric protocol with parameters $p,d,k$ is informative for $(a,b,c)$.

Proof

We must show that, given a deal $(A,B,C)$ and a bijection $f:D\rightarrow \mathbb F ^{d+1}_p$, there can be only one $X\in \mathcal A _k[f]$ with $X\subseteq A\cup C$. More generally, we claim that there may only be one $k$-slicing contained in any set $E\subseteq \mathbb F ^{d+1}_p$ with at most $a+c$ points; for indeed, by Lemma 1, if $E$ contains two distinct $k$-slicings then

$$\begin{aligned} |E|\ge kp^d+\min \left\{ p^d,kp^d-k^2p^{d-1}\right\} >a+c. \end{aligned}$$

But this contradicts the assumption that $|E|=a+c$, and we conclude that $E$ contains only one $k$-slicing, as claimed. $\square$

Now let us turn to $k$-safety. Once again we begin with purely combinatorial preliminaries. The following is an elementary but useful fact.

Lemma 3

Suppose that $c+k\le p$ and $|C|\le c$. Let $V$ be any hyperplane of $\mathbb F ^{d+1}_p$. Then, there exist $k$ distinct hyperplanes parallel or equal to $V$ and not meeting $C$.

Proof

Each hyperplane has $p^d$ elements, and each $x\in \mathbb F ^{d+1}_p$ lies in a unique hyperplane that is parallel to $V$. It follows that there are $p$ hyperplanes parallel or equal to $V$; since $c+k\le p$, at least $k$ of them do not meet $C$. $\square$

Lemma 4

Let $E$ be any subset of $\mathbb F ^{d+1}_p$ such that $k|E|\le p$ and let $X$ be a set of at most $k$ points such that $X\cap E=\varnothing$.

Then, there is a hyperplane $V$ such that $(x+ V)\cap E=\varnothing$ for all $x\in X$.

Proof

We will prove the more general claim that if $E$ is any subset of $\mathbb F ^{d+1}_p$ such that

$$\begin{aligned} k|E|< \dfrac{p^{d-e+2}-1}{p-1} \end{aligned}$$

and $X=\{x_1,\ldots ,x_k\}$ is a set of at most $k$ points such that $X\cap E=\varnothing$, then there is an $e$-dimensional subspace $V$ of $\mathbb F ^{d+1}_p$ such that $(x_i+ V)\cap E=\varnothing$ for all $i\le k$. The lemma follows by setting $e=d$ and noting that

$$\begin{aligned} \dfrac{p^{d-d+2}-1}{p-1}=\dfrac{p^{2}-1}{p-1}=p+1. \end{aligned}$$

Suppose that $X\subseteq \{x_1,\ldots ,x_k\}$. We proceed to build $V$ by induction on $e$. The base case, when $e=0$, is trivial (just take $V=\{0\}$).

For the inductive step, assume that

$$\begin{aligned} k|E|<\dfrac{p^{d-(e+1)+2}-1}{p-1}<\dfrac{p^{d-e+2}-1}{p-1}. \end{aligned}$$

Then, by induction hypothesis there is an $e$-dimensional subspace $V^{\prime }$ such that for all $i\le k$, $(x_i+ V^{\prime })\cap E=\varnothing$. Let us construct an $e+1$-subspace $V\supseteq V^{\prime }$ with the same property.

Let $\mathcal T$ be the set of all $(e+1)$-dimensional subspaces $U$ such that $V^{\prime }\subseteq U$. Each $U$ is of the form $\langle u,V^{\prime }\rangle$ for some $u\not \in V^{\prime }$. Hence there are

$$\begin{aligned} \dfrac{p^{d+1}-p^e}{p^{e+1}-p^e}=\dfrac{p^{d-(e+1)+2}-1}{p-1} \end{aligned}$$

values that $U$ may take; this is because $u$ may take $p^d-p^e$ different values, but given $u$ we have that $u+ V^{\prime }=w+ V^{\prime }$ if and only if $w\in (u+ V^{\prime })\setminus V^{\prime }$, and there are $p^{e+1}-p^e$ such $w$.

Meanwhile, if $U\not =W\in \mathcal T$ then $U\cap W=V^{\prime }$, from which it follows that, given $i\le k$, $E$ is the disjoint union of all sets of the form $(x_i+ U)\cap E$ with $U\in \mathcal T$. We conclude that for each $i\le k$, there are at most $|E|$ values of $U\in \mathcal T$ such that $(x_i+ U)\cap E\not =\varnothing$, and hence there are at most $k|E|$ values of $U\in \mathcal T$ such that there exists $i\le k$ with $(x_i+ U)\cap E\not =\varnothing$. But

$$\begin{aligned} k|E|< \dfrac{p^{d-(e+1)+2}-1}{p-1}, \end{aligned}$$

so there is $U_*\in \mathcal T$ such that $(x_i+ U_*)\cap E=\varnothing$ for all $i\le k$ and we choose $V={U_*}$. $\square$

With this, we may prove that our protocol is safe.

Lemma 5

Assume that $a,b,c,p,d,k$ are such that $p$ is a prime power, $a=kp^d$, $a+b+c=p^{d+1}$ and further (2) holds.

Then, the geometric protocol with parameters $p,d,k$ is $k$-safe for $(a,b,c)$.

Proof

Suppose that the deal $(A,B,C)$ is given and Alice has announced $\mathcal A =\mathcal A _k[f]\in \gamma (A)$.

Choose a set $X\subseteq D$ that has at most $k$ elements with $X\cap C=\varnothing$. By Lemma 4, there is a $d$-dimensional subspace $V$ such that $(x+ V)\cap f(C)=\varnothing$ for all $x\in f(X)$. Let $A_1^{\prime },\ldots ,A_m^{\prime }$ be all sets of the form $x+ V$ with $x\in f(X)$; we know that $m\le k$, but note that it may be the case that $m< k$. However, in view of Lemma 3, there are at least $k$ different hyperplanes parallel or equal to $V$ and not meeting $f(C)$ and thus we may pick $A_{m+1}^{\prime },\ldots ,A_k^{\prime }$ parallel or equal to $V$ but distinct from $A_i^{\prime }$ for $i\le m$. Setting $A^{\prime }=\bigcup _{i=1}^kA_i^{\prime }$ we see that $A^{\prime }\in \mathcal A$ is a $k$-slicing containing $X$ and not meeting $f(C)$, so that $f^{-1}(A^{\prime })\in \mathcal A _k[f]$ and $f^{-1}(A^{\prime })\cap C=\varnothing$, as required.

Meanwhile, to find an element of $\mathcal A _k[f]$ not containing $X$ and not meeting $C$, it suffices to find a $k$-slicing $A^{\prime \prime }$ not containing any fixed $x\in f(X)$ and not meeting $f(C)$. Choose any $y\in f(C)$ and any $d$-dimensional subspace $W$ such that $x-y\in W$. Once again use Lemma 3 to pick $A^{\prime \prime }_1,\ldots ,A^{\prime \prime }_k$ parallel or equal to $W$ and not meeting $f(C)$ and set $A^{\prime \prime }=\bigcup _{i=1}^k A_i^{\prime \prime }$. Then, $A^{\prime \prime }$ is a $k$-slicing not meeting $f(C)\cup \{x\}$, which means that $f^{-1}(A^{\prime \prime })$ does not meet $C$ and does not contain $X$, as required. $\square$

Our main result is now immediate:

Proof

(Proof of Theorem 1) Suppose $a,b,c,p,d,k$ satisfy (1) and (2). Note that by (2), $c+k\le p$ and thus $c<p^d$; it follows that $c< \min \{p^d,kp^d-k^2p^{d-1}\}$. Then by Lemma 2, the geometric protocol is informative, whereas by Lemma 5 it is $k$-safe. $\square$

5 Computing parameters

Theorem 1 gives general conditions under which the geometric protocol works, but it is perhaps not obvious how to find suitable parameters or even that many exist. In this section we shall flesh out more specific consequences of this result, showcasing its usefulness in solving many new instances of the Russian cards. We remark, however, that the bounds we give here are not meant to be exhaustive; the different parameters can be chosen in many other ways to obtain solutions for deals of different sizes.

First let us give a simplified version of (1), which will be easier to work with:

Lemma 6

Given natural numbers $p,k\ge 1$ we have that $kp^d-k^2p^{d-1}> 0$ if and only if $k\in [1,p-1]$, in which case $kp^d-k^2p^{d-1}\ge p^d-p^{d-1}$.

Proof

The function $kp^d-k^2p^{d-1}$ is concave on $k$ and $kp^d-k^2p^{d-1}=0$ when $k=0$ or $k=p$. It follows that, for natural $k$, $kp^d-k^2p^{d-1}> 0$ if and only if $1\le k\le p-1$.

Now, when $k=1$ we have that $kp^d-k^2p^{d-1}=p^d-p^{d-1},$ and similarly when $k=p-1$, from which it follows once again by concavity that $kp^d-k^2p^{d-1}\ge p^d-p^{d-1}$ for all $k\in [1,p-1]$. $\square$

Before we continue, let us mention a simple number-theoretic observation which will nevertheless be very useful:

Lemma 7

Given $n\ge 1$ there exists a prime power $p$ such that $n<p \le 2n$.

Proof

Choose $\ell$ to be the unique integer such that $n<2^\ell \le 2n$ and set $p=2^\ell$. $\square$

Now for the main result of this section. In order to give a uniform bound we shall use the fact that for all $k,c\ge 1$ we have that $\max \{k+c,kc\}\le kc+1$.

Theorem 2

Given $k,c\ge 1$. Then, the geometric protocol is informative and $k$-safe for $(a,b,c)$ for infinitely many values of $a,b$ with $b<2a(c+1)$. The smallest such value of $a$ is at most $2k(kc+1)$.

Proof

As before, it suffices to check that all conditions of Theorem 1 may be satisfied for appropriately chosen parameters.

Fix $k\ge 1$ and $c>0$. Use Lemma 7 to find a prime power $p$ such that $kc+1<p\le 2(kc+1)$. Given $d\ge 1$, set $a=kp^d$ and $b=p^{d+1}-a-c$.

First we observe that if $d=1$, $a=kp\le 2k(kc+1)$. Note that $b<\frac{pa}{k}\le 2a(c+1)$ independently of $d$.

To see that condition (1) holds, it suffices in view of Lemma 6 to observe that

$$\begin{aligned} c<p-1 \le p^{d-1}(p-1)=p^d-p^{d-1}. \end{aligned}$$

Meanwhile, condition (2) holds by the way we chose $p$.

It follows from Theorem 1 that the geometric protocol is informative and $k$-safe for $(a,b,c)$, as claimed. $\square$

6 Conclusions and future work

The generalized Russian cards problem, aside from being interesting from a purely combinatorial perspective, provides a compelling case-study for information-theoretic cryptography [7, 12, 16]. Most cryptosystems used in practice are computationally secure, meaning that an algorithm for breaking them would require a very large number of operations to carry out. Here, breaking could be understood as recovering the originial message but should usually be taken to mean something weaker, such as ‘gain probabilistic information’ or, in our setting, ‘learn the ownership of any individual card’. In order to establish that a cryptosystem is computationally secure, one often requires the assumption that a certain ‘master’ problem is difficult to solve; for example, one may show that recovering a private key is as hard for Cath as a well-known $\textsc {NP}$-complete problem.

In information-theoretic cryptography one requires that encryption be unconditionally secure, i.e. that it is provably impossible for the eavesdropper to break the cryptosystem. Information-theoretic cryptography has the advantage over computationally secure cryptography that it does not depend on eavesdroppers’ computational resources or, for example, the assumption that $\textsc {P}\ne \textsc {NP}$. The drawback is that such methods tend to be less practical and are thus used more rarely. In the specific case of the protocol we present, the assumption of a secure dealing phase is a disadvantage. Nevertheless, there have been many recent advances in the Russian cards problem and these 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 [17], 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$.

Swanson and Stinson also introduce perfect security for the Russian cards. 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 [4] a method which allows Cath to have more cards than Alice, which we call the colouring protocol. It is 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.