TY - GEN
T1 - Secure multiparty computations using the 15 puzzle
AU - Mizuki, Takaaki
AU - Kugimoto, Yoshinori
AU - Sone, Hideaki
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=38149030959&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38149030959&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-73556-4_28
DO - 10.1007/978-3-540-73556-4_28
M3 - Conference contribution
AN - SCOPUS:38149030959
SN - 9783540735557
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 255
EP - 266
BT - Combinatorial Optimization and Applications - First International Conference, COCOA 2007, Proceedings
PB - Springer Verlag
T2 - 1st International Conference on Combinatorial Optimization and Applications, COCOA 2007
Y2 - 14 August 2007 through 16 August 2007
ER -