TY - GEN
T1 - Zero-Knowledge Proof Protocol for Cryptarithmetic Using Dihedral Cards
AU - Isuzugawa, Raimu
AU - Miyahara, Daiki
AU - Mizuki, Takaaki
N1 - Funding Information:
Acknowledgments. We thank the anonymous referees, whose comments have helped us improve the presentation of the paper. We would like to thank Hideaki Sone for his cooperation in preparing a Japanese draft version at an earlier stage of this work. This work was supported in part by JSPS KAKENHI Grant Numbers JP19J21153 and JP21K11881.
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - Cryptarithmetic, also known as Verbal Arithmetic or Word Addition, is a popular pencil puzzle in which the aim is to deduce which letter corresponds to which numeral, given a mathematical equation in which each numeral (from 0 to 9) has been replaced with a unique letter. The most famous instance of this puzzle is probably “SEND + MORE = MONEY", whose solution is “9567 + 1085 = 10652", i.e., S = 9, E = 5, N = 6, D = 7, M = 1, O = 0, R = 8, and Y = 2. In this study, we construct a physical zero-knowledge proof protocol for a Cryptarithmetic puzzle: That is, our protocol enables a prover who knows a solution to the puzzle to convince a verifier that he/she knows the solution without revealing any information about it. The proposed protocol uses a physical deck of “dihedral cards,” which were developed by Shinagawa in 2019.
AB - Cryptarithmetic, also known as Verbal Arithmetic or Word Addition, is a popular pencil puzzle in which the aim is to deduce which letter corresponds to which numeral, given a mathematical equation in which each numeral (from 0 to 9) has been replaced with a unique letter. The most famous instance of this puzzle is probably “SEND + MORE = MONEY", whose solution is “9567 + 1085 = 10652", i.e., S = 9, E = 5, N = 6, D = 7, M = 1, O = 0, R = 8, and Y = 2. In this study, we construct a physical zero-knowledge proof protocol for a Cryptarithmetic puzzle: That is, our protocol enables a prover who knows a solution to the puzzle to convince a verifier that he/she knows the solution without revealing any information about it. The proposed protocol uses a physical deck of “dihedral cards,” which were developed by Shinagawa in 2019.
KW - Card-based cryptography
KW - Cryptarithmetic
KW - Dihedral cards
KW - Physical zero-knowledge proof
UR - http://www.scopus.com/inward/record.url?scp=85118168438&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85118168438&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-87993-8_4
DO - 10.1007/978-3-030-87993-8_4
M3 - Conference contribution
AN - SCOPUS:85118168438
SN - 9783030879921
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 51
EP - 67
BT - Unconventional Computation and Natural Computation - 19th International Conference, UCNC 2021, Proceedings
A2 - Kostitsyna, Irina
A2 - Orponen, Pekka
PB - Springer Science and Business Media Deutschland GmbH
T2 - 19th International Conference on Unconventional Computation and Natural Computation, UCNC 2021
Y2 - 18 October 2021 through 22 October 2021
ER -