Unconditional secure communication: a Russian Cards protocol | Journal of Combinatorial Optimization Skip to main content
Log in

Unconditional secure communication: a Russian Cards protocol

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

This paper investigates Russian Cards problem for the purpose of unconditional secure communication. First, a picking rule and deleting rule as well as safe communication condition are given to deal with the problem with 3 players and 7 cards. Further, the problem is generalized to tackle n players and n(n−1)+1 cards. A new picking rule for constructing the announcement is presented, and a new deleting rule for players to determine each other’s cards is formalized. Moreover, the safe communication condition is proved. In addition, to illustrate the approach, an example for 5 players and 21 cards is presented in detail.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Similar content being viewed by others

References

  • Albert MH, Aldred REL, Atkinson MD, van Ditmarsch HP, Handley CC (2005) Safe communication for card players by combinatorial designs for two-step protocols. Australasian J Comb 33:33–46

    MATH  Google Scholar 

  • Atkinson MD, van Ditmarsch HP, Roehling S (2007) Avoiding bias in cards cryptography. CoRR. cs/0702097

  • Cyriac A, Krishnan KM (2008) Lower Bound for the Communication Complexity of the Russian Cards Problem. CoRR. 0805.1974

  • Cong T, Zhenhua D (2007) Model checking propositional projection temporal logic based on SPIN. In: Proceedings of ICFEM07. Lecture Notes in Computer Science, vol 4789. Springer, Berlin, pp 246–265

    Google Scholar 

  • Fischer MJ, Wright RN (1996) Bounds on secret key exchange using a random deal of cards. J Cryptol 9(2):71–99

    Article  MATH  MathSciNet  Google Scholar 

  • Holzmann GJ (2003) The spin model checker: Primer and reference manual. Addison-Wesley, Berlin

    Google Scholar 

  • Koichi K, Takaaki M, Takao N (2004) Necessary and sufficient numbers of cards for the transformation protocol. Lecture Notes in Computer Science, vol 3106. Springer, Berlin, pp 92–101

    Google Scholar 

  • Ramanujam R, Suresh SP (2001) Information based reasoning about security protocols. Electron Notes Theor Comput Sci 55(1):89–104

    Google Scholar 

  • Rivest R, Shamir A, Adleman L (1978) A method for obtaining digital signatures and public-key cryptosystems. Commun ACM 21(2):120–126

    Article  MATH  MathSciNet  Google Scholar 

  • Roehling S (2005) Cards and cryptography. Report in partial fulfilment of MSc in Computer Science, University of Otago

  • Makarychev K (2001) Logicheskie voprosy peredachi informacii (logical issues of information transmission). Master’s thesis, Moscow State University, Diplomnaja rabota, Part 1

  • Stiglic A (2001) Computations with a deck of cards. Theor Comput Sci 259(1–2):671–678

    Article  MATH  MathSciNet  Google Scholar 

  • van Ditmarsch HP (2003) The Russian Cards problem. Stud Log 75:31–62

    Article  MATH  Google Scholar 

  • van Ditmarsch HP (2005) The case of the hidden hand. J Appl Non-Class Log 15(4):437–452

    Article  MATH  Google Scholar 

  • van Ditmarsch HP, van der Hoek W, van der Meyden R, Ruan J (2006) Model checking Russian Cards. Electron Notes Theor Comput Sci 149:105–123

    Article  Google Scholar 

  • Vasilenko O (2006) Number-theoretic algorithms in cryptography. American Mathematical Society, Boston. (Translations of Mathematical Monographs)

    Google Scholar 

  • Zhenhua D, Koutny M (2004) A framed temporal logic programming language. J Comput Sci Technol 19:333–344

    Google Scholar 

  • Zhenhua D, Cong T, Li Z (2008a) A decision procedure for propositional projection temporal logic with infinite models. Acta Inform 45(1):43–78

    Article  MATH  MathSciNet  Google Scholar 

  • Zhenhua D, Xiaoxiao Y, Koutny M (2008b) Framed temporal logic programming. Sci Comput Program 70:31–61

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Zhenhua Duan.

Additional information

This research is supported by the NSFC Grant Nos. 60433010, and 60873018.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Duan, Z., Yang, C. Unconditional secure communication: a Russian Cards protocol. J Comb Optim 19, 501–530 (2010). https://doi.org/10.1007/s10878-009-9252-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-009-9252-7

Keywords

Navigation