Portal de Periódicos da CAPES

Card-Based Zero-Knowledge Proof Protocol for Pancake Sorting

2023; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-031-32636-3_13

1611-3349

Yuichi Komano, Takaaki Mizuki,

Algorithms and Data Compression

Assume that, given a sequence of n integers from 1 to n arranged in random order, we want to sort them, provided that the only acceptable operation is a prefix reversal, which means to take any number of integers (sub-sequence) from the left of the sequence, reverse the order of the sub-sequence, and return them to the original sequence. This problem is called "pancake sorting," and sorting an arbitrary sequence with the minimum number of operations restricted in this way is known to be NP-hard. In this paper, we consider applying the concept of zero-knowledge proofs to the pancake sorting problem. That is, we design a physical zero-knowledge proof protocol in which a user (the prover) who knows how to sort a given sequence with $$\ell $$ operations can convince another user (the verifier) that the prover knows this information without divulging it.