## Abstract

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 language | English |
---|---|

Pages (from-to) | 1503-1511 |

Number of pages | 9 |

Journal | IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences |

Volume | E101A |

Issue number | 9 |

DOIs | |

Publication status | Published - Sept 2018 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

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