Batching Techniques Using Generalized Pile-Scramble Shuffles and Branching Shuffles

Card-based cryptography is a research field for realizing secure computation using physical cards. In card-based protocols, the efficiency of a protocol is mainly measured by the number of cards and the number of shuffles. Shinagawa and Nuida proposed a batching technique, which is a technique for reducing the number of pile-scramble shuffles (PSS) by combining multiple PSSs into a single PSS. In this paper, we propose three new methods for the batching technique. The first method uses a new shuffle called a generalized PSS; unlike a PSS, this allows the number of cards in each pile to be uneven. The second method uses a shuffle called a branching PSS, which is a PSS for a sequence including face-up cards. The third method uses a shuffle called a branching generalized PSS, which is a generalized PSS for a sequence including face-up cards. Our methods are efficient in terms of the number of cards and shuffles compared to the existing batching technique. As applications, we use our methods to reduce the number of shuffles for AND protocols and XOR protocols.