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

zbMATH Open1408.94965arXiv1401.1526MaRDI QIDQ406700FDOQ406700

Authors: Colleen M. Swanson, D. R. Stinson 

Publication date: 9 September 2014

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

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$.

Full work available at URL: https://arxiv.org/abs/1401.1526

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

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

zbMATH Keywords

combinatorial designsprotocolsinformation-theoretic cryptographyRussian cards problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

• Secure aggregation of distributed information: how a team of agents can safely share secrets in front of a spy
• 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
• Combinatorial solutions providing improved security for the generalized Russian cards problem
• Information Exchange in the Russian Cards Problem
• Crossing hands in the Russian cards problem
• Model checking Russian cards
• Who holds the best card? Secure communication of optimal secret bits
• A case study in almost-perfect security for unconditionally secure communication
• Title not available (Why is that?)

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)