Combinatorial solutions providing improved security for the generalized Russian cards problem

DOI10.1007/S10623-012-9770-7zbMATH Open1293.05021arXiv1207.1336OpenAlexW2141368734MaRDI QIDQ2248647FDOQ2248647

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

Publication date: 27 June 2014

Published in: Designs, Codes and Cryptography (Search for Journal in Brave)

Abstract: We present the first formal mathematical presentation of the generalized Russian cards problem, and provide rigorous security definitions that capture both basic and extended versions of weak and perfect security notions. In the generalized Russian cards problem, three players, Alice, Bob, and Cathy, are dealt a deck of $n$ cards, each given $a$, $b$, and $c$ cards, respectively. The goal is for Alice and Bob to learn each other's hands via public communication, without Cathy learning the fate of any particular card. The basic idea is that Alice announces a set of possible hands she might hold, and Bob, using knowledge of his own hand, should be able to learn Alice's cards from this announcement, but Cathy should not. Using a combinatorial approach, we are able to give a nice characterization of informative strategies (i.e., strategies allowing Bob to learn Alice's hand), having optimal communication complexity, namely the set of possible hands Alice announces must be equivalent to a large set of $t-(n,a,1)$-designs, where $t=a-c$. We also provide some interesting necessary conditions for certain types of deals to be simultaneously informative and secure. That is, for deals satisfying $c=a-d$ for some $dgeq2$, where $bgeqd-1$ and the strategy is assumed to satisfy a strong version of security (namely perfect $(d-1)$-security), we show that $a=d+1$ and hence $c=1$. We also give a precise characterization of informative and perfectly $(d-1)$-secure deals of the form $(d+1,b,1)$ satisfying $bgeqd-1$ involving $d-(n,d+1,1)$-designs.

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

Recommendations

• Additional constructions to solve the generalized Russian cards problem using combinatorial designs
• Generalized Russian Cards Problem
• A geometric protocol for cryptography with cards
• A colouring protocol for the generalized Russian cards problem
• A case study in almost-perfect security for unconditionally secure communication

zbMATH Keywords

combinatorial designsprotocolsinformation-theoretic cryptographyRussian cards problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Partitions of the 4-subsets of a 13-set into disjoint projective planes
• 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
• 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
• A geometric protocol for cryptography with cards

Cited In (17)

• Secure aggregation of distributed information: how a team of agents can safely share secrets in front of a spy
• Additional constructions to solve the generalized Russian cards problem using combinatorial designs
• Coloured and directed designs
• 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
• Efficient card-based protocols for generating a hidden random permutation without fixed points
• A colouring protocol for the generalized Russian cards problem
• Information Exchange in the Russian Cards Problem
• Crossing hands in the Russian cards problem
• All solutions to the immobilizer problem
• A geometric protocol for cryptography with cards
• Large sets with multiplicity
• Who holds the best card? Secure communication of optimal secret bits
• Generalized Russian Cards Problem
• A case study in almost-perfect security for unconditionally secure communication
• Title not available (Why is that?)

This page was built for publication: Combinatorial solutions providing improved security for the generalized Russian cards problem

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