A formalization of card-based cryptographic protocols via abstract machine

被引:73
作者
Mizuki, Takaaki [1 ]
Shizuya, Hiroki [2 ]
机构
[1] Tohoku Univ, Cybersci Ctr, Aoba Ku, Sendai, Miyagi 9808578, Japan
[2] Tohoku Univ, Ctr Informat Technol Educ, Aoba Ku, Sendai, Miyagi 9808576, Japan
关键词
Card-based protocols; Card games; Cryptography without computers; Recreational cryptography; Secure computations; COMPUTATIONS; SECURE;
D O I
10.1007/s10207-013-0219-4
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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.
引用
收藏
页码:15 / 23
页数:9
相关论文
共 14 条
[1]   Private computation using a PEZ dispenser [J].
Balogh, J ;
Csirik, JA ;
Ishai, Y ;
Kushilevitz, E .
THEORETICAL COMPUTER SCIENCE, 2003, 306 (1-3) :69-84
[2]  
Crepeau C., 1994, Advances in Cryptology - CRYPTO '93. 13th Annual International Cryptology Conference Proceedings, P319
[3]  
DENBOER B, 1990, LECT NOTES COMPUT SC, V434, P208
[4]   Comparing information without leaking it [J].
Fagin, R ;
Naor, M ;
Winkler, P .
COMMUNICATIONS OF THE ACM, 1996, 39 (05) :77-85
[5]   Bounds on secret key exchange using a random deal of cards [J].
Fischer, MJ ;
Wright, RN .
JOURNAL OF CRYPTOLOGY, 1996, 9 (02) :71-99
[6]  
Mizuki T, 2013, LECT NOTES COMPUT SC, V7956, P162, DOI 10.1007/978-3-642-39074-6_16
[7]  
Mizuki T, 2012, LECT NOTES COMPUT SC, V7658, P598, DOI 10.1007/978-3-642-34961-4_36
[8]  
Mizuki T, 2006, AUSTRALAS J COMB, V36, P279
[9]  
Mizuki T, 2009, LECT NOTES COMPUT SC, V5598, P358, DOI 10.1007/978-3-642-02270-8_36
[10]  
Moran T, 2006, LECT NOTES COMPUT SC, V4004, P88