Toward finite-runtime card-based protocol for generating a hidden random permutation without fixed points

Yuji Hashimoto, Koji Nuida, Kazumasa Shinagawa, Masaki Inamura, Goichiro Hanaoka

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


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 atCRYPTO1993. 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 newapproach 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.

Original languageEnglish
Pages (from-to)1503-1511
Number of pages9
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number9
Publication statusPublished - Sept 2018
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Toward finite-runtime card-based protocol for generating a hidden random permutation without fixed points'. Together they form a unique fingerprint.

Cite this