Efficient Card-Based Millionaires' Protocols via Non-binary Input Encoding

被引:2
作者
Nuida, Koji [1 ,2 ]
机构
[1] Kyushu Univ, Inst Math Ind IMI, Fukuoka, Japan
[2] Natl Inst Adv Ind Sci & Technol, Tokyo, Japan
来源
ADVANCES IN INFORMATION AND COMPUTER SECURITY, IWSEC 2023 | 2023年 / 14128卷
关键词
Card-based protocols; integer comparison; Millionaires' Problem; SECURE;
D O I
10.1007/978-3-031-41326-1_13
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
Comparison of integers, a traditional topic in secure multiparty computation since Yao's pioneering work on "Millionaires' Problem" (FOCS 1982), is also well studied in card-based cryptography. For the problem, Miyahara et al. (Theoretical Computer Science, 2020) proposed a protocol using binary cards (i.e., cards with two kinds of symbols) that is highly efficient in terms of numbers of cards and shuffles, and its extension to number cards (i.e., cards with distinct symbols). In this paper, with a different design strategy which we name "Tug-of-War Technique", we propose new protocols based on binary cards and on number cards. For binary cards, our protocol improves the previous protocol asymptotically (in bit lengths of input integers) in terms of numbers of cards and shuffles when adopting ternary encoding of input integers. For number cards, at the cost of increasing the number of cards, our protocol improves the number of shuffles of the previous protocol even with binary encoding, and more with q-ary encoding where q > 2.
引用
收藏
页码:237 / 254
页数:18
相关论文
共 12 条
[1]  
Crepeau C., 1994, Advances in Cryptology - CRYPTO '93. 13th Annual International Cryptology Conference Proceedings, P319
[2]  
Ishikawa Rie, 2015, Unconventional Computation and Natural Computation. 14th International Conference, UCNC 2015. Proceedings, P215, DOI 10.1007/978-3-319-21819-9_16
[3]   Practical card-based implementations of Yao's millionaire protocol [J].
Miyahara, Daiki ;
Hayashi, Yu-ichi ;
Mizuki, Takaaki ;
Sone, Hideaki .
THEORETICAL COMPUTER SCIENCE, 2020, 803 :207-221
[4]   Efficient and Secure Multiparty Computations Using a Standard Deck of Playing Cards [J].
Mizuki, Takaaki .
CRYPTOLOGY AND NETWORK SECURITY, CANS 2016, 2016, 10052 :484-499
[5]   A formalization of card-based cryptographic protocols via abstract machine [J].
Mizuki, Takaaki ;
Shizuya, Hiroki .
INTERNATIONAL JOURNAL OF INFORMATION SECURITY, 2014, 13 (01) :15-23
[6]  
Mizuki T, 2009, LECT NOTES COMPUT SC, V5598, P358, DOI 10.1007/978-3-642-02270-8_36
[7]   Efficient Card-Based Cryptographic Protocols for Millionaires' Problem Utilizing Private Permutations [J].
Nakai, Takeshi ;
Tokushige, Yuuki ;
Misawa, Yuto ;
Iwamoto, Mitsugu ;
Ohta, Kazuo .
CRYPTOLOGY AND NETWORK SECURITY, CANS 2016, 2016, 10052 :500-517
[8]  
Niemi V., 1999, Fundamenta Informaticae, V38, P181
[9]  
Ono T., 2023, P 2023 S CRYPTOGRAPH
[10]   A single shuffle is enough for secure card-based computation of any Boolean circuit [J].
Shinagawa, Kazumasa ;
Nuida, Koji .
DISCRETE APPLIED MATHEMATICS, 2021, 289 :248-261