TY - GEN
T1 - Six-Card Finite-Runtime XOR Protocol with only Random Cut
AU - Toyoda, Kodai
AU - Miyahara, Daiki
AU - Mizuki, Takaaki
AU - Sone, Hideaki
N1 - Funding Information:
We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper. We would like to thank Yuta Abe for his helpful discussions and support. This work was supported by JSPS KAKENHI Grant Numbers JP17K00001 and JP19J21153.
Publisher Copyright:
© 2020 ACM.
PY - 2020/10/5
Y1 - 2020/10/5
N2 - Executing a card-based cryptographic protocol is an attractive way to perform secure multiparty computation (MPC) with a deck of physical cards. Crèpeau and Kilian at CRYPTO 1993 proposed card-based AND and XOR protocols that can deal with a logical conjunction and exclusive-or of variables. Their protocols use a familiar shuffling action called a random cut that can be easily implemented by humans, while the numbers of required cards and shuffles are not small enough to be efficient and the protocols are Las Vegas algorithms, i.e., they are not finite-runtime. Several researchers have improved upon the protocols for a quarter of a century. Eventually, there are many AND protocols in the literature, some of which are quite efficient and practical to execute. By contrast, there are only three XOR protocols including the Crèpeau-Kilian protocol mentioned above. In this paper, we design an efficient XOR protocol using only random cuts; the numbers of required cards and shuffles are six and two (which is fixed), respectively. Our proposed XOR protocol is the first construction of a finite-runtime XOR protocol if we restrict ourselves to use only random cuts.
AB - Executing a card-based cryptographic protocol is an attractive way to perform secure multiparty computation (MPC) with a deck of physical cards. Crèpeau and Kilian at CRYPTO 1993 proposed card-based AND and XOR protocols that can deal with a logical conjunction and exclusive-or of variables. Their protocols use a familiar shuffling action called a random cut that can be easily implemented by humans, while the numbers of required cards and shuffles are not small enough to be efficient and the protocols are Las Vegas algorithms, i.e., they are not finite-runtime. Several researchers have improved upon the protocols for a quarter of a century. Eventually, there are many AND protocols in the literature, some of which are quite efficient and practical to execute. By contrast, there are only three XOR protocols including the Crèpeau-Kilian protocol mentioned above. In this paper, we design an efficient XOR protocol using only random cuts; the numbers of required cards and shuffles are six and two (which is fixed), respectively. Our proposed XOR protocol is the first construction of a finite-runtime XOR protocol if we restrict ourselves to use only random cuts.
KW - card-based cryptography
KW - deck of cards
KW - secure multiparty computation
UR - http://www.scopus.com/inward/record.url?scp=85095593780&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85095593780&partnerID=8YFLogxK
U2 - 10.1145/3384940.3388961
DO - 10.1145/3384940.3388961
M3 - Conference contribution
AN - SCOPUS:85095593780
T3 - APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020
SP - 2
EP - 8
BT - APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020
PB - Association for Computing Machinery, Inc
T2 - 7th ACM Workshop on Asia Public-Key Cryptography, APKC 2020, held in conjunction with the 15th ACM ASIA Conference on Computer and Communications Security, ACM ASIACCS 2020
Y2 - 6 October 2020
ER -