The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Dans le domaine de recherche du calcul sécurisé basé sur les cartes, l'un des problèmes ouverts de longue date est un problème proposé par Crépeau et Kilian à CRYPTO 1993. Il s'agit de développer un protocole efficace utilisant un jeu de cartes physiques qui génère uniformément et aléatoirement un permutation sans points fixes (appelée dérangement), où la permutation résultante doit être secrète contre les parties au protocole. Tous les protocoles existants pour résoudre le problème ont un problème commun : l’absence de garantie de s’arrêter en un nombre fini d’étapes. Dans cet article, nous étudions la faisabilité et l’infaisabilité du problème où une sortie uniformément aléatoire et un temps d’exécution fini sont requis. Premièrement, nous proposons une manière de réduire le problème initial, qui consiste à échantillonner une distribution uniforme sur un ensemble inefficace de perturbations, à un autre problème consistant à échantillonner une distribution non uniforme mais avec un ensemble sous-jacent significativement plus petit. Ce résultat constituera la base d’une nouvelle approche du problème. D'un autre côté, nous donnons également (en supposant la conjecture abc), sous un certain modèle formel, une limite inférieure asymptotique du nombre de cartes pour les protocoles résolvant le problème en utilisant uniquement des mélanges uniformes. Ce résultat fournirait une preuve à l’appui de la nécessité de traiter des distributions non uniformes comme dans la première partie susmentionnée de notre résultat.
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.
Copier
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
Copier
@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},}
Copier
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 -