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

被引:10
作者
Hashimoto, Yuji [1 ,3 ]
Nuida, Koji [3 ]
Shinagawa, Kazumasa [3 ,4 ]
Inamura, Masaki [2 ]
Hanaoka, Goichiro [3 ]
机构
[1] Tokyo Denki Univ, Tokyo, Saitama 3500394, Japan
[2] Tokyo Denki Univ, Sch Sci & Engn, Div Informat Syst & Design, Tokyo, Japan
[3] Natl Inst Adv Ind Sci & Technol, Tokyo 1350064, Japan
[4] Tokyo Inst Technol, Tokyo 1350064, Japan
来源
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | 2018年 / E101A卷 / 09期
关键词
card-based protocol; permutation without fixed points; COMPUTATIONS; SECURE;
D O I
10.1587/transfun.E101.A.1503
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
In the research area of card-based secure computation, one of the long-standing open problems is a problem proposed by Crepeau 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.
引用
收藏
页码:1503 / 1511
页数:9
相关论文
共 17 条
  • [1] [Anonymous], 1997, Enumerative combinatorics
  • [2] Birkhoff G., 1969, SURVEY MODERN ALGEBR
  • [3] Crepeau C., 1993, CRYPTO, P319, DOI DOI 10.1007/3-540-48329-2_27
  • [4] den Boer B., 1989, ADV CRYPTOLOGY, P208
  • [5] Secure Grouping Protocol Using a Deck of Cards
    Hashimoto, Yuji
    Shinagawa, Kazumasa
    Nuida, Koji
    Inamura, Masaki
    Hanaoka, Goichiro
    [J]. INFORMATION THEORETIC SECURITY, ICITS 2017, 2017, 10681 : 135 - 152
  • [6] Ibaraki T, 2016, PROCEEDINGS OF THE 3RD INTERNATIONAL CONFERENCE ON MATHEMATICS AND COMPUTERS IN SCIENCES AND IN INDUSTRY (MCSI 2016), P252, DOI [10.1109/MCSI.2016.054, 10.1109/MCSI.2016.23]
  • [7] Ishikawa Rie, 2015, Unconventional Computation and Natural Computation. 14th International Conference, UCNC 2015. Proceedings, P215, DOI 10.1007/978-3-319-21819-9_16
  • [8] Card-Based Cryptographic Protocols Using a Minimal Number of Cards
    Koch, Alexander
    Walzer, Stefan
    Haertel, Kevin
    [J]. ADVANCES IN CRYPTOLOGY - ASIACRYPT 2015, PT I, 2015, 9452 : 783 - 807
  • [9] Mizuki T, 2013, LECT NOTES COMPUT SC, V7956, P162, DOI 10.1007/978-3-642-39074-6_16
  • [10] Mizuki T, 2009, LECT NOTES COMPUT SC, V5598, P358, DOI 10.1007/978-3-642-02270-8_36