Efficient Card-Based Cryptographic Protocols for the Millionaires' Problem Using Private Input Operations

摘要

This paper proposes new efficient card-based cryptographic protocols for the millionaires' problem using private input operations. The millionaires' problem is one of the fundamental problems in cryptography. Two players, Alice and Bob, want to know which of them is richer without revealing their actual amount of asset. Many cryptographic protocols were proposed to solve the problem. Card-based cryptographic protocols were proposed to execute cryptographic protocols using physical cards instead of computers. Though some card-based cryptographic protocols for the millionaires' problem were proposed, most of them use many cards whose number depends on the size of the amount of asset. Though Nakai et al. implicitly proposed a new protocol that uses a constant number of cards using private input operations, their protocol is not efficient since the number of rounds is 2n+1, where n is the maximum number of bits of the asset. This paper shows new card-based protocols whose number of rounds is n+1. Another important feature of the proposed protocols is no-open property. No cards are opened until the end of the protocol.