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
Dalam bidang penyelidikan pengiraan selamat berasaskan kad, salah satu masalah terbuka yang telah lama wujud ialah masalah yang dicadangkan oleh Crépeau dan Kilian di CRYPTO 1993. Ini adalah untuk membangunkan protokol yang cekap menggunakan dek kad fizikal yang menjana seragam secara rawak pilih atur tanpa titik tetap (dipanggil kekacauan), di mana pilih atur yang terhasil mestilah rahsia terhadap pihak dalam protokol. Semua protokol sedia ada untuk masalah itu mempunyai isu biasa iaitu kekurangan jaminan untuk dihentikan dalam beberapa langkah yang terhad. Dalam kertas kerja ini, kami menyiasat kebolehlaksanaan dan ketidakupayaan untuk masalah di mana kedua-dua output rawak seragam dan masa jalan terhingga diperlukan. Mula-mula, kami mencadangkan satu cara untuk mengurangkan masalah asal, iaitu mengambil sampel taburan seragam ke atas set penyimpangan yang tidak cekap besar, kepada masalah lain untuk mensampel taburan tidak seragam tetapi dengan set asas yang jauh lebih kecil. Keputusan ini akan menjadi asas kepada pendekatan baharu kepada masalah tersebut. Sebaliknya, kami juga memberikan (dengan mengandaikan sangkaan abc), di bawah model formal tertentu, batas bawah asimptotik bilangan kad untuk protokol menyelesaikan masalah menggunakan kocok seragam sahaja. Keputusan ini akan memberikan bukti sokongan untuk keperluan menangani pengagihan tidak seragam seperti dalam bahagian pertama keputusan kami yang disebutkan di atas.
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.
Salinan
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
Salinan
@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},}
Salinan
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 -