Toward Finite-Runtime Card-Based Protocol for Generating a Hidden Random Permutation without Fixed Points


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.9   pp.1503-1511
Publication Date: 2018/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.1503
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
card-based protocol,  permutation without fixed points,  

Full Text: PDF(1.7MB)>>
Buy this Article

In the research area of card-based secure computation, one of the long-standing open problems is a problem proposed by Crépeau and Kilian at CRYPTO 1993. This is to develop an efficient protocol using a deck of physical cards that generates uniformly at random a permutation with no fixed points (called a derangement), where the resulting permutation must be secret against the parties in the protocol. All the existing protocols for the problem have a common issue of lacking a guarantee to halt within a finite number of steps. In this paper, we investigate feasibility and infeasibility for the problem where both a uniformly random output and a finite runtime is required. First, we propose a way of reducing the original problem, which is to sample a uniform distribution over an inefficiently large set of the derangements, to another problem of sampling a non-uniform distribution but with a significantly smaller underlying set. This result will be a base of a new approach to the problem. On the other hand, we also give (assuming the abc conjecture), under a certain formal model, an asymptotic lower bound of the number of cards for protocols solving the problem using uniform shuffles only. This result would give a supporting evidence for the necessity of dealing with non-uniform distributions such as in the aforementioned first part of our result.