A colouring protocol for the generalized Russian cards problem

DOI10.1016/J.TCS.2013.05.010MaRDI QIDQ391146zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Andrés Cordón-Franco, David Fernández-Duque, Fernando Soler-Toscano, Hans van Ditmarsch

Publication date 10 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

cryptographygeneralized Russian cards probleminformation protocolsecret exchange

Mathematics Subject Classification ID

Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62)

Abstract: In the generalized Russian cards problem, Alice, Bob and Cath draw $a$, $b$ and $c$ cards, respectively, from a deck of size $a+b+c$. Alice and Bob must then communicate their entire hand to each other, without Cath learning the owner of a single card she does not hold. Unlike many traditional problems in cryptography, however, they are not allowed to encode or hide the messages they exchange from Cath. The problem is then to find methods through which they can achieve this. We propose a general four-step solution based on finite vector spaces, and call it the "colouring protocol", as it involves colourings of lines. Our main results show that the colouring protocol may be used to solve the generalized Russian cards problem in cases where $a$ is a power of a prime, $c=O(a^2)$ and $b=O(c^2)$. This improves substantially on the set of parameters for which solutions are known to exist; in particular, it had not been shown previously that the problem could be solved in cases where the eavesdropper has more cards than one of the communicating players.

Recommendations

• A geometric protocol for cryptography with cards
• Information Exchange in the Russian Cards Problem
• Combinatorial solutions providing improved security for the generalized Russian cards problem
• Generalized Russian Cards Problem
• Crossing hands in the Russian cards problem

Cites work

• 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 1925555 (Why is no real title available?)
• scientific article; zbMATH DE number 1418286 (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 secure additive protocol for card players
• Bounds on secret key exchange using a random deal of cards
• Combinatorial Designs
• Combinatorial solutions providing improved security for the generalized Russian cards problem
• Computations with a deck of cards
• Model checking Russian cards
• On Cryptosystems Based on Polynomials and Finite Fields
• The Russian cards problem
• Three steps
• Unconditional secure communication: a Russian cards protocol

Cited in

(17)

• Combinatorial solutions providing improved security for the generalized Russian cards problem
• Information Exchange in the 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
• Model checking Russian cards
• scientific article; zbMATH DE number 7471709 (Why is no real title available?)
• Who holds the best card? Secure communication of optimal secret bits
• Perfectly secure data aggregation via shifted projections
• The undecidability of quantified announcements
• 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
• 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
• Positive announcements

This page was built for publication: A colouring protocol 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 Q391146)