The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.9 pp.1503-1511

- Publication Date
- 2018/09/01

- Publicized

- 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)

- Category

Yuji HASHIMOTO

Tokyo Denki University,the National Institute of Advanced Industrial Science and Technology

Koji NUIDA

the National Institute of Advanced Industrial Science and Technology

Kazumasa SHINAGAWA

the National Institute of Advanced Industrial Science and Technology,Tokyo Institute of Technology

Masaki INAMURA

Tokyo Denki University

Goichiro HANAOKA

the National Institute of Advanced Industrial Science and Technology

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Yuji HASHIMOTO, Koji NUIDA, Kazumasa SHINAGAWA, Masaki INAMURA, Goichiro HANAOKA, "Toward Finite-Runtime Card-Based Protocol for Generating a Hidden Random Permutation without Fixed Points" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 9, pp. 1503-1511, September 2018, doi: 10.1587/transfun.E101.A.1503.

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

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.1503/_p

Copy

@ARTICLE{e101-a_9_1503,

author={Yuji HASHIMOTO, Koji NUIDA, Kazumasa SHINAGAWA, Masaki INAMURA, Goichiro HANAOKA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Toward Finite-Runtime Card-Based Protocol for Generating a Hidden Random Permutation without Fixed Points},

year={2018},

volume={E101-A},

number={9},

pages={1503-1511},

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 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.},

keywords={},

doi={10.1587/transfun.E101.A.1503},

ISSN={1745-1337},

month={September},}

Copy

TY - JOUR

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

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1503

EP - 1511

AU - Yuji HASHIMOTO

AU - Koji NUIDA

AU - Kazumasa SHINAGAWA

AU - Masaki INAMURA

AU - Goichiro HANAOKA

PY - 2018

DO - 10.1587/transfun.E101.A.1503

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E101-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 2018

AB - 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.

ER -