研究成果

In March 2023, ChatGPT generated a new puzzle, Sumplete. Sumplete consists of an n x n grid, each whose cell has an integer. In addition, each row and column of the grid has an integer, which we call a target value. The goal of Sumplete is to make the sum of integers in each row and column equal to the target value by deleting some integers of the cells. In this paper, we prove that Sumplete is NP-complete and propose a physical zero-knowledge proof for Sumplete. To show the NP-completeness, we give a polynomial reduction from the subset sum problem to Sumplete. In our physical zero-knowledge proof protocol, we use a card protocol that realizes the addition of negative and positive integers using cyclic permutation on a sequence of cards. To keep the solution secret, we use a technique named decoy technique.

Research in the area of secure multi-party computation with an unconventional method of using a physical deck of playing cards began in 1989 when den Boar proposed a protocol to compute the logical AND function using five cards. Since then, the area has gained interest from many researchers and several card-based protocols to compute various functions have been developed. In this paper, we propose a card-based protocol called the overwriting protocol that can securely compute the k-candidate n-variable equality function f: {0,1,…,k−1}^{n} \to {0,1}. We also apply the technique used in this protocol to compute other similar functions.