Combinatorial solutions providing improved security for the generalized Russian cards problem

DOI10.1007/S10623-012-9770-7MaRDI QIDQ2248647zbMATH OpenOpenAlexFDO

Authors Colleen M. Swanson, D. R. Stinson

Publication date 27 June 2014

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

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

zbMATH Keywords

combinatorial designsprotocolsinformation-theoretic cryptographyRussian cards problem

Mathematics Subject Classification ID

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

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.

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

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 867473 (Why is no real title available?)
• scientific article; zbMATH DE number 3257050 (Why is no real title available?)
• scientific article; zbMATH DE number 2230917 (Why is no real title available?)
• A geometric protocol for cryptography with cards
• A secure additive protocol for card players
• Bounds on secret key exchange using a random deal of cards
• Computing and Combinatorics
• Model checking Russian cards
• Partitions of the 4-subsets of a 13-set into disjoint projective planes
• Public communication based on Russian cards protocol: a case study
• The Russian cards problem
• The case of the hidden hand
• Three steps
• Unconditional secure communication: a Russian cards protocol

Cited in

(17)

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

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)