TY - GEN
T1 - Interactive Physical Zero-Knowledge Proof for Norinori
AU - Dumas, Jean Guillaume
AU - Lafourcade, Pascal
AU - Miyahara, Daiki
AU - Mizuki, Takaaki
AU - Sasaki, Tatsuya
AU - Sone, Hideaki
N1 - Funding Information:
Acknowledgement. We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper. This work was supported by JSPS KAKENHI Grant Number JP17K00001 and partly by the OpenDreamKit Horizon 2020 European Research Infrastructures project (#676541) and the Cyber@Alps French National Research Agency program (ANR-15-IDEX-02).
Funding Information:
We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper. This work was supported by JSPS KAKENHI Grant Number JP17K00001 and partly by the OpenDreamKit Horizon 2020 European Research Infrastructures project (#676541) and the Cyber@Alps French National Research Agency program (ANR-15-IDEX-02).
Publisher Copyright:
© Springer Nature Switzerland AG 2019.
PY - 2019
Y1 - 2019
N2 - Norinori is a logic game similar to Sudoku. In Norinori, a grid of cells has to be filled with either black or white cells so that the given areas contain exactly two black cells, and every black cell shares an edge with exactly one other black cell. We propose a secure interactive physical algorithm, relying only on cards, to realize a zero-knowledge proof of knowledge for Norinori. It allows a player to show that he or she knows a solution without revealing it. For this, we show in particular that it is possible to physically prove that a particular element is present in a list, without revealing any other value in the list, and without revealing the actual position of that element in the list.
AB - Norinori is a logic game similar to Sudoku. In Norinori, a grid of cells has to be filled with either black or white cells so that the given areas contain exactly two black cells, and every black cell shares an edge with exactly one other black cell. We propose a secure interactive physical algorithm, relying only on cards, to realize a zero-knowledge proof of knowledge for Norinori. It allows a player to show that he or she knows a solution without revealing it. For this, we show in particular that it is possible to physically prove that a particular element is present in a list, without revealing any other value in the list, and without revealing the actual position of that element in the list.
KW - Card-based secure two-party protocols
KW - Norinori
KW - Puzzle
KW - Zero-knowledge proofs
UR - http://www.scopus.com/inward/record.url?scp=85070210093&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85070210093&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-26176-4_14
DO - 10.1007/978-3-030-26176-4_14
M3 - Conference contribution
AN - SCOPUS:85070210093
SN - 9783030261757
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 166
EP - 177
BT - Computing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings
A2 - Du, Ding-Zhu
A2 - Duan, Zhenhua
A2 - Tian, Cong
PB - Springer Verlag
T2 - 25th International Computing and Combinatorics Conference, COCOON 2019
Y2 - 29 July 2019 through 31 July 2019
ER -