
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Toward FiniteRuntime CardBased Protocol for Generating a Hidden Random Permutation without Fixed Points
Yuji HASHIMOTO Koji NUIDA Kazumasa SHINAGAWA Masaki INAMURA Goichiro HANAOKA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E101A
No.9
pp.15031511 Publication Date: 2018/09/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E101.A.1503
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: cardbased protocol, permutation without fixed points,
Full Text: PDF(1.7MB) >>Buy this Article
Summary:
In the research area of cardbased secure computation, one of the longstanding 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 nonuniform 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 nonuniform distributions such as in the aforementioned first part of our result.

