Abstract
Consider a face-down card lying on the table such that we do not know whether its suit color is black or red. Then, how do we make identical copies of the card while keeping its color secret? A partial solution has been devised: using a number of additional black and red cards, Niemi and Renvall proposed an excellent protocol which can copy a face-down card while allowing only a small probability of revealing its color. In contrast, this paper shows the nonexistence of a perfect solution, namely, the impossibility of copying a face-down card with perfect secrecy. To prove such an impossibility result, we construct a rigorous mathematical model of card-based cryptographic protocols; giving this general computational model is the main result of this paper.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Balogh, J., Csirik, J.A., Ishai, Y., Kushilevitz, E.: Private computation using a PEZ dispenser. Theor. Comput. Sci. 306, 69–84 (2003)
Crépeau, C., Kilian, J.: Discreet solitary games. In: Proceedings of the CRYPTO ’93, Lecture Notes in Computer Science, vol. 773, pp. 319–330, Springer, Berlin (1994)
den Boer, B.: More efficient match-making and satisfiability: the five card trick. In: Proceedings of the EUROCRYPT ’89, Lecture Notes in Computer Science, vol. 434, pp. 208–217, Springer, Berlin (1990)
Fagin, R., Naor, M., Winkler, P.: Comparing information without leaking it. Commun. ACM 39(5), 77–85 (1996)
Fischer, M.J., Wright, R.N.: Bounds on secret key exchange using a random deal of cards. J. Cryptol. 9(2), 71–99 (1996)
Mizuki, T., Asiedu, I.K., Sone, H.: Voting with a logarithmic number of cards. In: Proceedings of the UCNC 2013, Lecture Notes in Computer Science, vol. 7956, pp. 162–173. Springer, Berlin (2013)
Mizuki, T., Kumamoto, M., Sone, H.: The five-card trick can be done with four cards. In: Proceedings of the ASIACRYPT 2012, Lecture Notes in Computer Science, vol. 7658, pp. 598–606. Springer, Berlin (2012)
Mizuki, T., Sone, H.: Six-card secure AND and four-card secure XOR. In: Proceedings of the Frontiers in Algorithmics (FAW 2009), Lecture Notes in Computer Science, vol. 5598, pp. 358–369, Springer, Berlin (2009)
Mizuki, T., Uchiike, F., Sone, H.: Securely computing XOR with 10 cards. Australas. J. Comb. 36, 279–293 (2006)
Moran, T., Naor, M.: Polling with physical envelopes: a rigorous analysis of a human-centric protocol. In: Proceedings of the EUROCRYPT 2006, Lecture Notes in Computer Science, vol. 4004, pp. 88–108. Springer, Berlin (2006)
Niemi, V., Renvall, A.: Secure multiparty computations without computers. Theor. Comput. Sci. 191, 173–183 (1998)
Stamer, H.: Efficient electronic gambling: an extended implementation of the toolbox for mental card games. In: Proceedings of the Western European Workshop on Research in Cryptology (WEWoRC 2005), Lecture Notes in Informatics,vol. P-74, pp. 1–12 (2005)
Stiglic, A.: Computations with a deck of cards. Theor. Comput. Sci. 259, 671–678 (2001)
Turing, A.M.: On computable numbers with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc. 42, 230–265 (1936)
Acknowledgments
This work was supported by JSPS KAKENHI Grant Number 23700007.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mizuki, T., Shizuya, H. A formalization of card-based cryptographic protocols via abstract machine. Int. J. Inf. Secur. 13, 15–23 (2014). https://doi.org/10.1007/s10207-013-0219-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10207-013-0219-4