Six-Card Finite-Runtime XOR Protocol with Only Random Cut
Kodai Toyoda, Daiki Miyahara, Takaaki Mizuki, Hideaki Sone · 2020
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.