Efficient Card-Based Cryptographic Protocols for Millionaires' Problem Utilizing Private Permutations

We propose several efficient card-based cryptographic protocols for the millionaires' problem by introducing a new operation called Private Permutation (PP) instead of the shuffle used in existing card-based cryptographic protocols. Shuffles are useful randomization techniques for designing card-based cryptographic protocols for logical gates, and this approach seems to be almost optimal. This fact, however, implies that there is room for improvements if we do not use logical gates as building blocks for secure computing, and we show that such an improvement is actually possible for the millionaires' problem. Our key technique, PP, is a natural randomization operation for permuting a set of cards behind the player's back, and hence, a shuffle can be decomposed into two PPs with one communication between them. Thus PP not only allows us to transform Yao's seminal protocol into a card-based cryptographic protocol, but also enables us to propose entirely novel and efficient protocols by securely updating bitwise comparisons between two numbers. Furthermore, it is interesting to remark that one of the proposed protocols has a remarkably deep connection to the well-known logical puzzle known as "The fork in the road".