Additional constructions to solve the generalized Russian cards problem using combinatorial designs

MaRDI QIDQ406700zbMATH OpenFDO

Authors Colleen M. Swanson, D. R. Stinson

Publication date 9 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.1526, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p29

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

combinatorial designsprotocolsinformation-theoretic cryptographyRussian cards problem

Mathematics Subject Classification ID

Cryptography (94A60) Combinatorial aspects of block designs (05B05)

Abstract: 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 hands 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 Cathy's 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=lfloorfraca-delta2floor$ cards. Alternatively, the construction yields solutions for arbitrary $delta$, $c$ and any $ageqdelta+2c$.

Recommendations

• Generalized Russian Cards Problem
• A colouring protocol for the generalized Russian cards problem
• Combinatorial solutions providing improved security for the generalized Russian cards problem
• A study of a generalization of a card problem
• The Russian cards problem
• Combinatorial Designs
• A construction for resolvable designs and its generalizations
• scientific article; zbMATH DE number 782055
• Large sets of \(t\)-designs and a Ramsey-type problem
• Combinatorial designs and related computational constructions

Cites work

• scientific article; zbMATH DE number 437574 (Why is no real title available?)
• scientific article; zbMATH DE number 4191563 (Why is no real title available?)
• scientific article; zbMATH DE number 5575521 (Why is no real title available?)
• scientific article; zbMATH DE number 176546 (Why is no real title available?)
• scientific article; zbMATH DE number 549855 (Why is no real title available?)
• scientific article; zbMATH DE number 1925555 (Why is no real title available?)
• scientific article; zbMATH DE number 2230917 (Why is no real title available?)
• A colouring protocol for the generalized Russian cards problem
• A new look at an old construction: constructing (simple) 3-designs from resolvable 2-designs
• A secure additive protocol for card players
• Bounds on secret key exchange using a random deal of cards
• Combinatorial Designs
• Computing and Combinatorics
• Covering all triples on n marks by disjoint Steiner systems
• Model checking Russian cards
• Partitions of sets of designs on seven, eight and nine points
• Public communication based on Russian cards protocol: a case study
• The CRC handbook of combinatorial designs
• The Russian cards problem
• The case of the hidden hand
• Three steps
• Unconditional secure communication: a Russian cards protocol

Cited in

(11)

• Combinatorial solutions providing improved security for the generalized Russian cards problem
• Information Exchange in the Russian Cards Problem
• Secure aggregation of distributed information: how a team of agents can safely share secrets in front of a spy
• Model checking Russian cards
• Who holds the best card? Secure communication of optimal secret bits
• Perfectly secure data aggregation via shifted projections
• A distributed computing perspective of unconditionally secure information transmission in Russian cards problems
• A distributed computing perspective of unconditionally secure information transmission in Russian cards problems
• scientific article; zbMATH DE number 2230917 (Why is no real title available?)
• A case study in almost-perfect security for unconditionally secure communication
• Crossing hands in the Russian cards problem

This page was built for publication: Additional constructions to solve the generalized Russian cards problem using combinatorial designs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q406700)