In the generalized Russian cards problem, we have a card deck $X$ of $n$ cards and three participants, Alice, Bob, and Cathy, dealt $a$, $b$, and $c$ cards, respectively. Once the cards are dealt, Alice and Bob wish to privately communicate their han
ds to each other via public announcements, without the advantage of a shared secret or public key infrastructure. Cathy should remain ignorant of all but her own cards after Alice and Bob have made their announcements. Notions for Cathys ignorance in the literature range from Cathy not learning the fate of any individual card with certainty (weak $1$-security) to not gaining any probabilistic advantage in guessing the fate of some set of $delta$ cards (perfect $delta$-security). As we demonstrate, the generalized Russian cards problem has close ties to the field of combinatorial designs, on which we rely heavily, particularly for perfect security notions. Our main result establishes an equivalence between perfectly $delta$-secure strategies and $(c+delta)$-designs on $n$ points with block size $a$, when announcements are chosen uniformly at random from the set of possible announcements. We also provide construction methods and example solutions, including a construction that yields perfect $1$-security against Cathy when $c=2$. We leverage a known combinatorial design to construct a strategy with $a=8$, $b=13$, and $c=3$ that is perfectly $2$-secure. Finally, we consider a variant of the problem that yields solutions that are easy to construct and optimal with respect to both the number of announcements and level of security achieved. Moreover, this is the first method obtaining weak $delta$-security that allows Alice to hold an arbitrary number of cards and Cathy to hold a set of $c = lfloor frac{a-delta}{2} rfloor$ cards. Alternatively, the construction yields solutions for arbitrary $delta$, $c$ and any $a geq delta + 2c$.
In 1963, Shrikhande and Raghavarao published a recursive construction for designs that starts with a resolvable design (the master design) and then uses a second design (the indexing design) to take certain unions of blocks in each parallel class of
the master design. Several variations of this construction have been studied by different authors. We revisit this construction, concentrating on the case where the master design is a resolvable BIBD and the indexing design is a 3-design. We show that this construction yields a 3-design under certain circumstances. The resulting 3-designs have block size k = v/2 and they are resolvable. We also construct some previously unknown simple designs by this method.
We present the first formal mathematical presentation of the generalized Russian cards problem, and provide rigorous security definitions that capture both basic and extend
We consider user-private information retrieval (UPIR), an interesting alternative to private information retrieval (PIR) introduced by Domingo-Ferrer et al. In UPIR, the database knows which records have been retrieved, but does not know the identity
of the query issuer. The goal of UPIR is to disguise user profiles from the database. Domingo-Ferrer et al. focus on using a peer-to-peer community to construct a UPIR scheme, which we term P2P UPIR. In this paper, we establish a strengthened model for P2P UPIR and clarify the privacy goals of such schemes using standard terminology from the field of privacy research. In particular, we argue that any solution providing privacy against the database should attempt to minimize any corresponding loss of privacy against other users. We give an analysis of existing schemes, including a new attack by the database. Finally, we introduce and analyze two new protocols. Whereas previous work focuses on a special type of combinatorial design known as a configuration, our protocols make use of more general designs. This allows for flexibility in protocol set-up, allowing for a choice between having a dynamic scheme (in which users are permitted to enter and leave the system), or providing increased privacy against other users.
This work examines the critical anisotropy required for the local stability of the collinear ground states of a geometrically-frustrated triangular-lattice antiferromagnet (TLA). Using a Holstein-Primakoff expansion, we calculate the spin-wave freque
ncies for the 1, 2, 3, 4, and 8-sublattice (SL) ground states of a TLA with up to third neighbor interactions. Local stability requires that all spin-wave frequencies are real and positive. The 2, 4, and 8-SL phases break up into several regions where the critical anisotropy is a different function of the exchange parameters. We find that the critical anisotropy is a continuous function everywhere except across the 2-SL/3-SL and 3-SL/4-SL phase boundaries, where the 3-SL phase has the higher critical anisotropy.
