Committed-format AND protocol using only random cuts

In the research area of card-based cryptography, designing committed-format AND protocols that are efficient in terms of the number of required cards is a major topic. Such an AND protocol should receive two pairs of face-down (physical) cards representing two secret input bits, from which it should securely produce a pair of face-down cards representing the AND value of the two bits via a series of actions, such as shuffling and turning over cards, along with some helping cards. The number of required cards typically depends on allowed kinds of shuffling operations. This paper focuses on “RC-protocols” meaning to be able to use only the random cut (RC), which is the easiest shuffling operation to implement. The best committed-format AND RC-protocol currently known was devised by Stiglic in 2001, where eight cards are used (i.e., his protocol needs four helping cards). Since then, it has been an open question to determine whether there exists a committed-format AND RC-protocol using less than eight cards. In this study, we answer to the question: We propose a six-card committed-format AND RC-protocol (using exactly two random cuts). Therefore, we can reduce the number of required cards by two.