Secure multiparty computations using the 15 puzzle (Extended abstract)

被引：0
作者：
Mizuki, Takaaki [1 ]
Kugimoto, Yoshinori [2 ,3 ]
Sone, Hideaki [1 ]
机构：
[1] Tohoku Univ, Aoba Ku, Infomat Synergy Ctr, Aramaki Aza Aoba 6-3, Sendai, Miyagi 9808578, Japan
[2] Tohoku Univ, Infomat Synergy Ctr, Aoba Ku, Sendai, Miyagi 9808578, Japan
[3] Tohoku Univ, Grad Sch Informat Sci, Sone Lab, Sendai, Miyagi, Japan
来源：
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PROCEEDINGS | 2007年 / 4616卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
This paper first considers the use of the "15 puzzle," which is one of the most famous sliding-block puzzles, to provide secure multiparty computations. That is, we design a class of 15-puzzle-based protocols for securely computing Boolean functions. Specifically, we show that any function of 4 variables (or less) and any symmetric function of 14 variables (or less) can be securely computed by a 15-puzzle-based protocol; furthermore, we present a 5-variable function and a 15-variable symmetric function, both of which cannot be securely computed by any protocol in the class.
引用
收藏
页码：255 / +
页数：2
相关论文
共 50 条
[21]   Efficient Multiparty Interactive Coding for Insertions, Deletions, and Substitutions [Extended Abstract] [J].
Gelles, Ran ;
Kalai, Yael Tauman ;
Ramnarayan, Govind .
PROCEEDINGS OF THE 2019 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC '19), 2019, :137-146
[22]   Towards Round-Optimal Secure Multiparty Computations: Multikey FHE Without a CRS [J].
Kim, Eunkyung ;
Lee, Hyang-Sook ;
Park, Jeongeun .
INFORMATION SECURITY AND PRIVACY, 2018, 10946 :101-113
[23]   Towards Round-Optimal Secure Multiparty Computations: Multikey FHE Without a CRS [J].
Kim, Eunkyung ;
Lee, Hyang-Sook ;
Park, Jeongeun .
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2020, 31 (02) :157-174
[24]   Symmetric cryptographic solution to Yao's millionaires' problem and an evaluation of secure multiparty computations [J].
Shundong, Li ;
Daoshun, Wang ;
Yiqi, Dai ;
Ping, Luo .
INFORMATION SCIENCES, 2008, 178 (01) :244-255
[25]   Communication complexity and lower bounds on multilective computations (Extended abstract) [J].
Hromkovic, J .
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1998, 1998, 1450 :789-797
[26]   A common algebraic description for probabilistic and quantum computations (Extended abstract) [J].
Beaudry, M ;
Fernandez, JM ;
Holzer, M .
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004, PROCEEDINGS, 2004, 3153 :851-862
[27]   Decidable call by need computations in term rewriting (extended abstract) [J].
Durand, I ;
Middeldorp, A .
AUTOMATED DEDUCTION - CADE-14, 1997, 1249 :4-18
[28]   The language X:: Circuits, computations and classical logic (Extended abstract) [J].
van Bakel, S ;
Lengrand, S ;
Lescanne, P .
THEORETICAL COMPUTER SCIENCE, PROCEEDINGS, 2005, 3701 :81-96
[29]   Secure Error Correction Using Multiparty Computation [J].
Raeini, Mohammad G. ;
Nojoumian, Mehrdad .
2018 IEEE 8TH ANNUAL COMPUTING AND COMMUNICATION WORKSHOP AND CONFERENCE (CCWC), 2018, :468-473
[30]   On the Security of the EMV Secure Messaging API (Extended Abstract) [J].
Adida, Ben ;
Bond, Mike ;
Clulow, Jolyon ;
Lin, Amerson ;
Anderson, Ross ;
Rivest, Ronald L. .
SECURITY PROTOCOLS, 2010, 5964 :147-149
12345