IEICE TRANSACTIONS on Fundamentals
Toward Finite-Runtime Card-Based Protocol for Generating a Hidden Random Permutation without Fixed Points
Summary :
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
Authors
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
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
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 -
English
